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

백준 9461번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 9461번: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 처음 접해보기 때문에 다양한 글들을 꼼꼼..

백준 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..

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