핀란드 교환학생의 개발일지

백준 2579번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 문제 내용이 길어 따로 캡쳐본을 첨부하지 않았으니, 링크를 참고하면서 봐주시면 됩니다. 백준 2579번: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제 역시 이전에 업로드한 피보나치 수열과 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 ..

백준 2748번 문제를 Dynamic Programming (DP, 동적 계획법)의 두 가지 접근 방법인 Top Down 방식과 Bottom Up 방식으로풀어보았습니다. 백준에 제출 시에는 실행 횟수를 절감할 수 있는 Bottom Up 방식만 제출했으니 참고해주시기 바랍니다. 백준 2748번: https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 내용은 아래와 같습니다. 우선 피보나치 수열은 첫번째, 두번째 ..

백준 2751번 문제를 Merge Sort로 풀어보았습니다. 처음에는 Quick Sort로 풀이했으나, 계속 정답처리 되지 않아 찾아보니 Quick Sort는 거꾸로 정렬되어 있을 경우 O(N^2)의 시간복잡도가 발생하기 때문에 시간초과로 인한 오답이라는 정보를 얻게 되었습니다. 따라서 이를 보완하고자 Merge Sort로 풀이하여 최종적으로 정답처리될 수 있었습니다. 백준 2751번: https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net..

백준 1436번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 백준 1436번 : https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 우선 해당 문제를 해결하기 위해 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 ..

백준 1018번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 백준 1018번: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 우선 해당 문제를 풀기 위한 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 ..

본격적으로 자료구조 공부를 시작하기 전 첫 번째로 구현했던 코드입니다. 백준 1914번 '하노이탑' 문제와도 연관이 있을 수 있으나, 백준에 맞춰 작성한 것은 아니므로 그대로 넣을 시 백준에서 오답처리됩니다. 이 코드를 기반으로 백준도 풀어보았으니, 기회가 된다면 업로드하도록 하겠습니다. 문제를 먼저 소개해본다면, 3개의 rods가 있고, n개의 disks가 있을 때, 다음과 같은 조건을 충족하면서 첫 번째 rod에 있는 모든 disk들을 세 번째 rod로 옮기는 것이 해결해야 할 문제입니다. [조건 1] 한 번에 한 개의 disk만 옮길 수 있다. [조건 2] '움직인다'라는 것은 선택한 rod의 가장 상단에 있는 disk를 옮기는 것을 말한다 [조건 3] 더 큰 disk를 더 작은 disk 위에 위치..