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

백준 2565번 문제를 Dynamic Programming(DP, 동적계획법)으로 풀어보았습니다. 백준 2565번: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해 주..

백준 11053번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 11053번: https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다...

백준 2156번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 2156번: https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 ..

백준 1463번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 1473번: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 내용은 아래와 같습니다. 사실 이전에 업로드한 모든 DP 문제들의 경우, 이 문제에서 막혀 DP에 대해 공부를 시작하면서 풀었던 문제입니다. 이 문제를 접할 당시만 해도 DP에 대한 지식이 없어, 고민을 정말 많이 했는데도 답이 나오지 않던 중, DP로 접근해서 풀어야 하는 문제임을 깨닫고, 더 쉬운 DP 문제부터 시작하여 다시 여기까지 와서 풀게 되었습니다. DP 개념을 모를 경우 풀기..

백준 1149번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 1149번: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력이 더 준비되어 있으니, 위 링크를 통해 확인하시기 바랍니다. 이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 ..

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

백준 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) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 ..