복습노트 복습노트

문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이와 창영이가 주어진 n개의 돌을 서로 번갈아 돌아가면 1개 또는 3개의 돌을 가져올 수 있는데 마지막으로 돌을 가져가는 사람이 이기는 게임입니다. 여기서 돌의 갯수 n이 주어졌을 때 이기는 사람을 구하는 문제입니다. 선공은 항상 상근이가 합니다. dp로 접근하였습니다. dp[x] : 돌이 x개 있는 게임판에서 선공이 이긴다면 true, 아니라면 false를 저장합니다. 초기 조건은 dp[1] = true, dp[2] = false, dp[3] = true로 잡아줍니다. dp[x-1]이 false이거나 dp[x-3]이 false이면 dp[x]는 true이고, 아니라면 dp[..

문제 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net n개의 도시들이 주어지고 도시와 도시간의 이동비용을 알려주고 임의의 시작점에서 모든 도시들을 순회하는데 최소의 금액으로 순회하는 비용을 출력하는 문제입니다. 도시와 도시간의 이동은 쌍방향이고 1번도시에서 2번도시로 갈때의 비용과 2번도시에서 1번도시로 갈때의 비용은 서로 다릅니다. 또한 한번 방문한 도시는 다시 방문할 수 없고 마지막으로 방문했던 도시는 맨 처음 도시로 돌아와야 합니다. 먼저 n의 범위가 최대 16으로 ..

비트 연산은 메모리를 절약할 수 있다는 장점이 있습니다. 비트 연산을 할 때 주의해야할 점은 부호 입니다. unsigned char a = 131; //1000 0011 char b = -125; //1000 0011 unsigned char aa; char bb; aa = a >> 5; bb = b >> 5; cout 5 = 4(0000 0100) 입니다. char -125 (1000 0011) >> 5 = -4 (1111 1100) signed 숫자에서 bit를 옮길때 비는 공간은 그 수의 부호로 채웁니다. 따라서 남은 bit들은 다 1로 채웠습니다. 컴퓨터는 음수를 표현할 때 2's complement 방식을 사용하므로 1111 1100 -> 0000 0011 -> 0000 0100(4) 가 나오고..

문제 5934번: Visiting Cows After many weeks of hard work, Bessie is finally getting a vacation! Being the most social cow in the herd, she wishes to visit her N (1 HTML 삽입 미리보기할 수 없는 소스 main 함수에서 dfs(1, 0)이 실행된 상태 입니다. 첫번쨰 인자로는 현재 방문한 노드 번호가 들어가고 두번째 인자로는 현재 선택된 노드의 부모 노드가 들어갑니다. 따라서 지금 1번 노드 부터 살펴보는 것입니다. 2번째 줄을 보면 dp[x][1] = 1로 초기화 해줍니다. 왜냐하면 [1]은 자기 자신을 무조건 방문하기 때문입니다. 6번째 줄을 보면 dp[x][0] += max(..

문제 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 최상단 루트 노드가 주어지고 트리의 연결 정보가 주어졌을 때 노드의 번호를 입력하면 입력된 노드 번호를 포함한 subtree의 갯수를 출력하는 문제입니다. 예를 들어 루트 노드가 5이고 입력된 노드가 5, 4, 8 이라면 답은 각각 9, 4, 1 이 됩니다. 먼저 트리의 정보를 백터의 인접리스트 형태로 저장해줍니다. HTML 삽입 미리보기할 수 없는 소스 이제 각 노드마다 subtree의 갯수 정..

probability dp(확률 dp) 확률과 기댓값은 다르다. ex) 1. 정육면체 주사위를 던질 때 1이 나올 확률? 1/6 2. 정육면체 주사위를 던질 때 1이 나올 때까지 던지는 횟수의 기댓값은? = 6 1번 던졌을 때 1이 나올 확률(1/6) + 2번 던졌을 때 1이 나올 확률(5/6(1이 처음에 안나올 확률) * 1/6(1이 그다음에 나올 확률) * 2) + 3번 던졌을 때 1이 나올 확률 (5/6(1이 처음에 안나올 확률) * 5/6(1이 두번째 던졌을때도 안나올 확률) * 1/6(1이 나올 확률) * 3) + ...... 다음과 같은 식으로 표현할 수 있다. 3. 정육면제 주사위를 던질 때 나온 수의 기댓값은? (1/6 * 1) + (1/6 * 2) + (1/6 * 3) + (1/6 * 4..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열이 주어지면 증가하는 부분수열중 길이가 가장 긴 길이를 구하는 문제입니다. 예를들어 {10, 20, 10, 30, 20, 50} 에서 가장 길이가 긴 수열은 {10, 20, 10, 30, 20, 50} 으로 총 길이가 4입니다. 수열 {10, 20, 10, 30, 20, 50} 에서 case를 나누어서 생각해보겠습니다. 1) 먼저 가장 첫번째 수열만 보면 그냥 그대로 '10' ..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집에 빨간색이나 초록, 파란색으로 칠할 수 있는데 서로 붙어 있는 집은 같은 색을 칠하면 안됩니다. 먼저 각각 집에 대해서 가격을 저장해야 합니다. 1 = 빨간, 2 = 초록, 3 = 파랑 price[n][1] = n번째 집을 빨간으로 칠하는데 드는 비용입니다. HTML 삽입 미리보기할 수 없는 소스 이제 점화식을 세우겠습니다. 우리는 총 3가지의 경우의 수를 세울 수 있습니다. 처음에 집의 색을 선택하는 경우가 3가지 이기 때문입니다..