개발자 지망생의 끄적끄적 개발기록

백준 12865 : 평범한 배낭 등급 : Gold V 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : Vector 고전적인 다이나믹 프로그래밍 문제, 0-1 배낭(Knapsack) 문제이다. 배낭 하나에 가치가 최대가 되도록 물건을 넣는 문제. 배열에 물건의 무게와 가치를 저장하고, 그에 따른 DP테이블을 생성한다. 0번 인..

백준 1083 : 소트 등급 : Gold IV 1083번: 소트 (acmicpc.net) 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 사용 알고리즘 : Greedy 사용 자료구조 : Vector 버블 소트(Bubble Sort)의 원리와, 이를 그리디적으로 활용하는 문제였다. 위와 같은 배열에 17번까지 SWAP이 가능하다고 해 보자. 이때, 17번 안에 10을 버블 소트로 가장 앞까지 가져올 수 있으므로 이를 진행해준다. 진행 하면서 버블 소트는 총 9번이 일어났으며, 1이 있던 위치에 10이 들어간..

백준 16946 : 벽 부수고 이동하기 4 등급 : Gold II 16946번: 벽 부수고 이동하기 4 (acmicpc.net) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 사용 알고리즘 : DFS 사용 자료구조 : Vector 벽의 위치에서 벽을 부수고 이동할 수 있는 공간을 구하는 문제. 주어진 그래프가 있을 때, 영역 별 크기의 합을 미리 구하고, 벽과 인접한 영역들의 값을 더해주는 방법으로 풀이 가능. 이때 인접한 곳은 상하좌우로 확인하는데, 그림과 같이 중복되는 경우에 두 번 ..

에라토스테네스의 체 Sieve of Eratosthenes 소수를 판정하기 위한 기본적인 정수론 알고리즘이다. 2부터 90까지의 수 중 소수를 구한다고 해 보자. (1은 소수가 될 수 없으므로 제외) 2를 확인하였을 때, 2는 소수이므로 이후 2의 배수는 모두 소수가 아닌 것으로 처리해준다. 3을 확인하였을 때, 3은 소수이므로 이후 3의 배수는 모두 소수가 아닌 것으로 처리해준다. 4를 확인하였을 때, 4는 이미 소수가 아닌 것으로 표시가 되어있으므로, 건너뛰고 5를 확인. 5를 확인하였을 때, 5는 소수이므로 이후 5의 배수는 모두 소수가 아닌 것으로 처리해준다. 모두 진행하게 되면 이와 같이 소수만 남게 된다. 이에 대한 코드는 아래와 같다. bool prime[101] = {false}; // 1..

백준 9252 : LCS 2 등급 : Gold IV 9252번: LCS 2 (acmicpc.net) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : - 다이나믹 프로그래밍으로 풀 수 있는 고전적인 문제이다. 배열의 가장 첫 부분을 비우고, 두 글자가 같은 부분이 나오면, 이전까지 같은 부분이 있었는지 확인해 + 1을 해준다. → str1[i] == str2[j]이면, dp[i][j] = dp..