Let's Begin Programming

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이 문제 또한 전형적인 다이나믹 프로그래밍(DP) 문제이다. 다이나믹 프로그래밍 문제는 n =1 일 때, n = 2 일 때 .. 이렇게 직접 세보면서 풀리는 경우도 꽤 있는 것 같다. 이 문제를 보고나서 종이에 직접 경우의 수를 구해보았다. 문제에 나와있는 예시는 n = 1, 2, 4 인 경우가 나와 있기 때문에 3, 5, 6 까지 해보니까 확실한 규칙이 보였다. n = 3 인 경우, 먼저 모두 0 인 경우는 존재하..

개발 공부 (알고리즘) 2021. 3. 11. 02:43

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 다이나믹 프로그래밍 문제로 주어진 조건을 그대로 구현하면 실행 시간이 굉장히 오래 걸린다. 이럴 때 사용하는 것이 메모이제이션(Memoization) 기법이다. 캐싱(Caching)이라고도 부르는 이 기법은 중복된 연산을 피하고자 하는 다이나믹 프로그래밍을 위해서 기존에 계산한 결과를 저장해놓고 만약 다시 그 값이 필요하다면 곧바로 이미 저장되어있는 값을 반환하는 기법이다. 이 문제에서 입력으로 들어가는 변수는 a..

개발 공부 (알고리즘) 2021. 3. 8. 00:35

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 증가하는 수열의 길이를 구하는 문제이다. 입력의 크기가 100만이기 때문에 수열을 완전 탐색하면서 길이를 셀 수 없다. 이번 문제를 해결하면서 밑에 블로그를 참고했다. [참고]suri78.tistory.com/199 [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python https://www.acmicpc.net/..

개발 공부 (알고리즘) 2021. 2. 23. 08:05

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이 문제도 파라메트릭 서치 유형의 이분 탐색 문제이다. 이 문제도 해결 방법이 쉽게 떠오르지 않아 다른 사람들의 설명을 많이 참고했다. 해설을 들어도 바로 이해가 되지 않아서 예시를 하나 하나 따라가보면서 이해하려고 노력했다. 이해하고 코드를 작성하고 보니 문제의 길이만큼 코드의 길이도 짧았다. 하지만 만약 코딩테스트나 시험에서 이 문제를 만났다면 쉽게 이분 탐색을 생각하지 못했을..

개발 공부 (알고리즘) 2021. 2. 23. 06:15

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제는 바로 해결 방법이 떠오르지 않아서 다른 분의 해결 방법을 참고했다. blog.naver.com/kks227/220444432628 [2110번] 공유기 설치 https://www.acmicpc.net/problem/21102110번: 공유기 설치www.acmic... blog.naver.com 사실 이전의 파라메트릭 서치 유형의 문제이고 크게 다르지..

개발 공부 (알고리즘) 2021. 2. 23. 03:45

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 직전에 풀었던 랜선 자르기 문제와 거의 동일한 문제이다. 문제의 내용이나 숫자는 다르지만 결국 푸는 방식은 같고 중간값으로 나누지 않고 뺀다는 것이 다르다. 파라메트릭 서치 유형으로 결정을 하는 방식으로 문제를 해결할 수 있다. 절단기의 최대 높이를 구하는 문제이지만 h 높이로 잘랐을 때 필요한 나무 길이가 나오는 지를 결정하는 문제로 바꾸어 해결할 수 있다. 나무를 자를..

개발 공부 (알고리즘) 2021. 2. 23. 03:29

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 앞선 문제들은 기본적인 이분 탐색 코드를 어느 정도 외우고 있으면 풀 수 있는 간단한 문제들이었다. 1654번: 랜선자르기 문제부터는 파라메트릭 서치 (Parametric Search) 유형의 문제들이 나왔다. 파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 범위 내의 가장 큰 값, 작은 값을 찾는 문제들이 주로 이 유형에 해당하며, 보통 코딩테스트에서는 이러..

개발 공부 (알고리즘) 2021. 2. 23. 02:49

www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두 가지 조건을 이용해 정렬하는 문제이다. 이전 문제들과 다른 점은 두 조건의 자료형이 다르다는 점이었다. 좌표 정렬 문제에서는 x와 y모두 정수로 주어졌고, 단어 정렬 문제에서는 문자열만 주어졌다. 이번 문제에서는 입력 받는 한 쌍이 (숫자, 문자열)로 이루어져 있다. 먼저 나이 순으로 정렬하는 조건을 위해서 sort()함수의 key 파라미터에 현재 리스트의 첫 번째 원소, 나이(숫자)를 전달한다. 만약에 나이가 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:16