본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 9251 LCS - 동적프로그래밍 [문제] https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] 최장 공통 부분 수열이란 연속되어 있지 않아도 되는 공통된 문자열을 의미한다. 예를 들어, ACAYKP와 CAPCAK의 경우 ACAK가 연속되지는 않아도 공통된 문자열로 포함되어 있는 LCS다. LCS는 문자열 a,b가 있다고 했을 때, a를 기준으로 b 문자열을 비교해 나가면서 같은 문자인 경우 카운트해줘야 하므로 이전까지의 LCS ..
[boj] 백준 2293 동전1 - 동적프로그래밍 [문제] https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 동적 프로그래밍 문제이다. coin 배열에 동전의 가치들을 저장해두고 dp[a] = b에 대해 a원을 만들 수 있는 경우의 수 b로 두고 접근한다. 0원을 만드는 경우의 수도 1가지이므로 dp[0] = 1로 둔다. 동전의 가치가 1, 2, 5가 있고 10을 만들 수 있는 경우의 수를 구한다고 하자. 동전 1에 대해서 1을 만들 수 있는 경우의 수는 0을 만들 수 있는 경우의 수와 ..
[boj] 백준 2023 신기한 소수 - DFS [문제] https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net [풀이] dfs로 풀 수 있다. 왼쪽에서 1번째, 2번째 ... n번째 자리까지의 수가 모두 소수여야 하므로 처음 올 수 있는 수는 소수인 2, 3, 5, 7 밖에 없다. 이 수들에 대해서 짝수는 소수가 아니므로 홀수를 대상으로만 수를 덧붙여 소수 판별을 해주고, 소수인 수들에 대해서 n자리가 될 때까지 반복한다. [코드] #include #include #include #in..
[boj] 백준 1916 최소비용 구하기 - 다익스트라 [문제] https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [풀이] 다익스트라 알고리즘. 우선순위 큐를 이용해 풀이하였다. [코드] // Created by strit on 2022-02-23. gold5 1916 최소비용 구하기 - 다익스트라 #include #include #include #include #define INF 987654321 using namespace::std; int n, m; int d..
[boj] 백준 1461 도서관 - 그리디 [문제] https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net [풀이] 그리디 알고리즘. 책을 원래자리에 돌려놓기 위해서는 어차피 원점을 지나야 하므로 음수, 양수를 따로 나눠서 계산해준다. m권을 한꺼번에 옮길 수 있다면 왕복값은 m권 중 더 큰 값의 왕복값으로 계산해준다. 그 후, 양 극단에 있는 값 중 더 큰 값에 대해서, 갖다 놓기만 하면 되므로 편도로 계산해주기 위해 값을 빼준다. 예를 들어, -39 -37 -29 -28 -6 2 11 에 대해서..
[boj] 백준 1759 암호 만들기 - DFS [문제] https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net [풀이] dfs를 이용해서 풀 수 있다. 증가하는 순서의 배열로만 암호가 만들어지므로 알파벳을 정렬 후 사용한다. depth가 암호의 길이가 되었을 때 모음과 자음의 개수를 확인해주고 조건에 일치하면 출력한다. [코드] // Created by strit on 2022-02-17. gold5 1759 암호 만들기 - dfs #include #include #include using namesp..
[boj] 백준 1527 금민수의 개수 - 재귀&브루트포스 [문제] https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 범위 내에 존재하는 4와 7로만 이루어진 숫자를 재귀로 전부 탐색한다. [코드] // Created by strit on 2022-02-16. silver1 1527 금민수의 개수 - 브루트 포스 & 재귀 #include #include #include using namespace::std; long long a, b; int cnt; void solve(long long nu..
[boj] 백준 1946 신입 사원 - 그리디 [문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 그리디 알고리즘. 서류 심사 순위로 정렬을 하고 나면 면접 순위가 현재 최대 면접 순위보다 더 높아야만(숫자가 더 작아야만) 합격할 수 있다. 이 경우 최대 면접 순위를 갱신해주면서 합격자 숫자를 구한다. [코드] #include #include #include using namespace::std; int main() { //선발할 수 있는 신입사원의 최대..

티스토리툴바