취업 준비 및 일상

https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 풀이 dp[i][j][k][n]을 '처음 주사위를 3번 던져 나온 눈이 i, j, k이고, 던질 수 있는 기회가 n번 남았을 때의 기댓값'이라고 정의합니다. 그러면 dp[i][j][k][n] = max((주사위를 한 번 더 던지고, 기회가 n-1번 남았을 때의 기댓값), (i, j, k일 때의 점수))가 됩니다. 자세한 풀이는 에디토리얼를 참고하세요 코드 1 2 3 4 5 6 7 8 9 10 11 1..

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 그 유명한 '습격자 초라기' 문제입니다. DP 문제라는건 예전에 들어서 알았는데도 풀이 접근조차 못하겠더라고요. 그래서 casterian님의 풀이를 봤습니다. 이 분 글 퀄리티가 좋습니다. cf) 안 되는 풀이 처음에 풀이 아이디어를 대충 본 후, '1~N열에서 최솟값, 2~N열 + 1열에서 최솟값을 구하여 두 값의 최솟값이 정답이 되지 않나?' 라고 ..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 풀이 다들 2차원 배열로 잘 풀던데, 저는 머리가 그렇게는 안 돌아가서 3차원 배열을 만들었습니다. 1~N번째 수열의 값을 각각 arr[i]에 담아둡니다. 3차원 int 배열 dp[i][j][k]: 1~i번째 수를 j개의 구간을 이용하여 합하였을 때 최대값(k==0: i번째 수 미포함, k==1: i번째 수 포함) 그러면, dp[i][j][0] = max(dp[i-1][j..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 일반적인 구간 DP 문제입니다. dp[i][j]를 'i번째 파일부터 j번째 파일까지 합치는 최소 비용'이라고 하면, dp[i][i+k] = min(dp[i][i+j]+ dp[i+j+1][i+k] + 'i번째 파일부터 j번째 파일의 용량')(for j in range(1, k))이 됩니다. 여기서 'i번째 파일부터 j번째 파일의 용량'은 누적합을 구하여 처리하면 됩니다. 배운 점 당연..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 dp[i]를 'N을 i번 사용하여 만들 수 있는 숫자들의 집합'이라고 정의합니다. 일단, 보기처럼 N=5일 경우, 5, 55, 555, ... , 55555555와 같이 '붙여 만드는 값'은 사칙연산으로 만들어지지 않기에 대응되는 dp[i]에 넣어줍니다. dp[i] = (j는 1부터 i-1까지) (dp[j]의 원소)와 (dp[i-j]의 원소)의 사칙연산으로 모든 원소를 만들 수 있습니다. i = 2부터 8까지 반복문을 돌면서 차근차근히 모든 원소를 찾아줍니다. 이후 numbers가 있는 가장 작은 set을 찾아 해당 set의 index..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다. DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 ..