1. 문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 2. recursive 일단 문제를 중복되는 작은 부분 문제들로 분할을 해보자 각 부분문제를 해결하는 함수를 다음과 같이 정의할 수 있다. dp(count, idx) = count개의 색상이 선택되었고 idx 부터 색을 적절히 선택하여 n-1번 인덱스까지 K개를 선택할 수 있는 경우의 수 이 함수는 idx 색상을 선택하는 것과 선택하지 않는것 두가지 부분문제를 생성한다. 따라서 점화식으로 나타내면 다음과 같다..

1. 문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 2. 완전탐색 이 문제에서 구슬을 비교하는 추의 개수와 종류는 전부 동일하다. 따라서 주어진 추를 사용해서 만들 수 있는 모든 경우의 무게를 만들고나면 구슬의 무게를 확인할 수 있다. 추는 한번만 사용할 수 있으므로 각각의 추에대해서 3가지 선택을 해야한다 1. 추를 구슬쪽에 올릴 경우 (w - weight[idx]) 2. 추를 올리지 않는 경우 (w) 3. 추를 반대편에 올릴 경우 (w..

1. 문제 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 2. 풀이 트리의 리프노드는 부모 노드말고 연결점이 없다. 따라서 처음 트리를 인접리스트 형태로 데이터를 받은 후 리프노드를 set에 담은 뒤 재귀적으로 제거하는 노드에 딸린것들을 모두 제거하고 제거하는 노드 중 리프 노드인것을 set 에 지워버리면 남은 리프 노드의 개수를 알아낼 수 있다. (제거하는 노드의 부모가 리프 노드가 될 수 있으므로 예외처리 해줘야한다.) 12345678910111213141..

1. problem leetcode.com/problems/reverse-integer/ Given integer and return this integer with its digits reverse (if reversing integer out of range "int", then return 0) 2. sol if x is minus => abs(x) if x == max, min => return 0 push => x%10 pop => x/10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int reverse(int x) { int ret = 0, xx =x; if(x == INT32_MIN ..

1. 문제 1115번: 순열 (acmicpc.net) 1115번: 순열 0부터 N-1까지 모든 정수를 한 번씩 포함하고 있는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A를 이용해서 A와 길이가 같은 자식 배열 B을 아래와 같은 방법으로 구할 수 있다. B[0] = 0 B[i] = A[B[i-1]] (1 ≤ www.acmicpc.net 완벽한 순열 == 순열이 해당 규칙에의해 모든 정점을 방문하는 순환형태 P와 Q의 차이 == P[i] 와 Q[i]의 값이 다른 i 의 개수 이 문제에서 주어진 규칙에 의해 주어진 순열은 한 정점당 한 엣지를 가지는 방향그래프로 생각할 수 있으며, 이는 곧 그래프 문제로 변형하여 문제를 해결 할 수 있음을 의미한다. 2. 차이가 가장 작은 완벽한 순열 찾..

1. 문제 코딩테스트 연습 - 내적 | 프로그래머스 (programmers.co.kr) 2. 풀이 1 2 3 4 5 6 7 8 9 10 11 #include #include #include #include using namespace std; int solution(vector a, vector b) { transform(a.begin(), a.end(), b.begin(), a.begin(), multiplies()); return accumulate(a.begin(), a.end(), 0); } Colored by Color Scripter cs accumulate : 주어진 배열을 합쳐준다. (numeric) transform: 두개의 배열에 특정한 연산을 4번째 인수에 output : algori..