프로그래밍 공부 노트

https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 설명의 편의를 위해 마름모 버튼을 caps lock, 별 버튼을 shift라고 부르자. 문자열을 인접한 대문자 혹은 소문자끼리 묶는다면 아래와 같다. i L ove INHA 위 상황에서, 두 번째 글자인 L을 입력하기 위해 caps lock을 누르게 되면, 다음 글자인 o를 입력하기 위해 다시 caps lock 혹은 shift를 눌러야 하므로 비효율적이다. 즉 길이가 1인 그룹을 입력하기 위해서는 ..

https://www.acmicpc.net/problem/5847 5847번: Milk Scheduling Farmer John's N cows (1

https://www.acmicpc.net/problem/23358 23358번: Quack Strikes Back (Easy) Two years ago the IPSC contestants had a hard time to understand a piece of code written in PostScript. Last year wasn't any better as we introduced a queue-based programming language. If you didn't participate last year (and even if you did :), this pract www.acmicpc.net 굳이 따지자면 큐를 쓰는 문제이긴 하지만, 알고리즘 문제라기 보단 CS 문제에 가깝다. 큐와 레..

https://www.acmicpc.net/problem/2201 2201번: 이친수 찾기 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 첫 번째 이친수부터 하나하나 차례로 찾아나가다 보면, K자리의 이친수의 개수는 피보나치 수열의 K번째 값과 같다는 것을 알 수 있다. 즉 값이 2^(n - 1)승인 이친수는 n번째 이친수이다. 또한 모든 이친수를 값이 2^k인 이친수의 합 꼴로 나타내면, k의 합이 곧 해당 이친수의 순서임을 알 수 있다. 따라서 이를 이용하면 K번째 이친수의 값을 빠르게 알 수 있다. #inclu..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 칸과 칸 사이를 이동할 때 현재 칸보다 낮은 높이로만 이동하므로, 한 번 방문했던 칸을 다시 방문하려면 낮은 칸에서 높은 칸으로 이동해야 하므로 모순이 되어 같은 칸을 두 번 이상 방문할 수 없다. 또한 한 칸에 도달하려면 인접한 칸에서 현재 칸으로 이동해야 하므로, 현재 칸으로 이동하는 경우의 수는 인접한 칸 중 현재 칸보다 높이가 높은 칸으로 이동하는 경우의 수의 합과 같다. 즉 각 칸을 노..

가장 긴 증가하는 부분 수열은 이분 탐색을 응용하는 문제인데, 부분 수열을 만들면서 수를 추가할 때 이분 탐색을 활용하기 때문이다. 수열 A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다 전에 나온 값이 Ai 이후에 위치하므로 부분 수열의 규칙을 무시하지만, 대다수의 문제에서 수열 자체가 아닌 수열의 길이를 요구하고 또 길이 자체가 변하는 방법은 아니므로 사용 가능하다. https://th..

배낭 문제는 고유한 무게와 가치를 가진 N개의 물건에 대해 무게를 최소화하면서 가치를 최대화하는 방법을 찾는 문제로, 일반적으로는 DP를 이용해 풀 수 있다. 가방 안에 들어가는 무게를 인덱스로, 해당 무게에서 저장할 수 있는 가장 큰 무게를 값으로 가지는 배열을 선언한다고 하자. 또 무게가 1이고 가치가 0인 가상의 물건을 무한정 사용할 수 있다고 하고, 초기 상태에는 이 물건을 가들 채워넣었다고 하자. 각 무게 w에 비용이 w_k인 k번째 물건을 추가했을 때, 무게 w + w_k에서의 기존 최대 가치를 갱신 가능하다면 가상의 물건을 w_k개만큼 뺀 뒤 k번째 물건을 추가해 가치의 최댓값을 늘릴 수 있다. 이 과정을 최대 무게부터 w_k까지, 각 물건에 대해 차례로 반복한다면 배낭 문제를 해결할 수 있..

다이나믹 프로그래밍이란, 이전 값을 이용해 구할 수 있는 현재 값 f(n)을 구할 때 메모이제이션(memoization) 기법을 이용해 저장한 이전 값을 활용하는 것을 의미한다. 주로 1차원 / 2차원 배열에 계산 결과를 저장해 O(1) 시간에 계산 결과를 가져온다. https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 ..

https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 두 비밀번호의 각 자리를 2중 for문으로 비교한다고 하자. A의 i번째 자리까지와 B의 j번째 자리까지의 가장 긴 부분 문자열을 str[i][j]라고 했을 때, A[i]가 B[j]라면 str[i][j]는 str[i - 1][j - 1]의 맨 뒤에 A[i]를 추가한 것과 같다. 만일 같지 않다면 이 때의 최장 공통 문자열은 A를 한 자리 줄이거나 B를 한 자리 줄였을 때의 최장 공통 부분 문..

https://www.acmicpc.net/problem/16456 16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ 첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요! www.acmicpc.net 섬을 이동할 수 있는 방향이 +1, +2, -1이고 한 번 방문한 섬을 다시 방문할 수는 없다. 따라서 i번째 섬에서 i + 2번째 섬으로 이동했다면 +1 혹은 +2 방향으로 이동했을 때 i + 1번째 섬을 다시 방문할 수 없으므로 다음 방향은 -1이고, i + 2번째 섬을 이미 방문했으므로 다음 방향은 +2가 되어야 한다. 즉, i번째 섬에서 i + 3번째 섬으로..