DP 문제는 수식을 생각해 줘야하는데 어려운 문제에서는 그게 참 어렵다. 책의 실전 문제에서는 아직 엄청나게 어려운 문제는 없었다. 1로 만들기 주어진 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제였다. 연산 종류 X%5 == 0 이면 5로 나누기 X%3 == 0 이면 3으로 나누기 X%2 ==0 이면 2로 나누기 X - 1 하기 DP 문제를 풀 때는 초깃값을 설정할 수 있는 것은 설정하고, 나머지는 가장 큰 값으로 채우거나 비워놓아야 한다. 이 문제에서는 1,2,3,5 index의 값을 1로 설정할 수 있다. 문제의 수식은 4번째 값을 구할 때 찾아낼 수 있다. dp[4] = min(dp[4-1]+1 , dp[4/2]+1) 연산을 할 수 있다면 dp[연산 결과]+1을 비교해 최솟값을 찾아내는 ..
이진 탐색 문제는 left, right를 정하고 mid값을 비교해가며 풀면 된다. 이진 탐색 문제를 풀 때 배열은 항상 정렬되어 있어야 한다. 부품 찾기 배열 N 에서 배열 M의 값들을 찾는 문제였다. 배열 N의 값들을 오름차순으로 정렬한 후 M의 값들을 차례대로 이진탐색한 결과를 출력했다. 또, 찾아야 하는 값을 findNum으로 두고 초기 left와 right 값은 각각 0과 N 배열의 최댓값의 index인 N-1로 정했다. 이진탐색을 할 때 총 4가지 경우가 있다. narr[mid] 값이 findNum 보다 클 경우 → 왼쪽 범위를 탐색해야 함 (right 값을 mid-1로 바꿔줌) narr[mid] 값이 findNum 보다 작을 경우 → 오른쪽 범위를 탐색해야 함 (left 값을 mid+1 로 바..
실전 문제는 굉장히 쉬웠다. 위에서 아래로 단순히 내림차순 정렬하는 문제였다. c++의 sort 함수는 오름차순 정렬이 기본으로 설정되어 있다. 내림차순 정렬을 하고 싶을 때에는 compair 함수를 생성해서 sort의 세 번째 인자로 넣어주면 된다. int compair(int a, int b) { return a > b; } int main() { int N; int i; int num[501]; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &num[i]); } sort(num, num + N, compair); for (i = 0; i < N; i++) { printf("%d ", num[i]); } } /* 3 15 27 12 */ 성적이 낮은..
DFS BFS 문제는 dx, dy로 위치 이동을 해가며 stack이나 queue에 넣고빼기를 하면 되는 문제라 다른 문제들보다는 괜찮은 것 같다. 음료수 얼려 먹기 전체 맵에서 아이스크림 개수를 구하는 문제였다. 맵은 0과 1로 이루어져 있고 0이 길(뚫려 있는 부분), 1이 벽(칸막이)이었다. dx와 dy로 방향을 정하고 dfs 재귀함수에서 4방향 중 한 번도 방문하지 않았고 길이면 다시 dfs로 탐색한다. 이때 아이스크림 개수를 찾는 문제이기 때문에 맵 전체를 탐색해야 한다. for문으로 전체 맵에서 방문하지 않았고 길인 곳에서 dfs 함수를 호출하면 최종적으로 아이스크림 총 개수를 구할 수 있다. int g[1001][1001]; int N, M; int dx[4] = { 1,-1,0,0 }; in..
구현 문제는 어려운 문제는 너무 어렵다.. 모든 문제가 그렇지만 구현과 dp는 어려우면 생각도 못하겠다. 휴 계속 연습해야지.... 상하좌우 NxN 크기의 맵에서 LRUD 로 이동하는 문제였는데, 맵의 x와 y를 당연히 좌표와 똑같을 줄 알았지만 달라서 당황했다. 문제에서는 x와 y가 바뀌어 있고 (오른쪽으로 3칸 아래로 2칸이 (2,3)) y 좌표는 반대로 되어 있다 (U는 -1, D는 +1) 이 점만 제외하면 쉽게 풀 수 있는 문제였다. 너무 오랜만에 풀어서 좌표 문제를 푸는 방법을 까먹어서 배열에 값을 미리 담아서 사용하지 않고 그냥 풀어서 좀 지저분하지만 어쩔 수 없다. 다음부터는 잊지 말고 풀어야지! #define _CRT_SECURE_NO_WARNINGS #include #include #in..
최근에는.. 할 일이 너무 많아서 우선순위에서 밀려나는 바람에 문제를 많이 안풀었다.. 다시 차근차근 코테 준비를 해볼까 한다.. (2022-2 알고리즘 때 구현하기는 했음, 이것도 정리해서 올릴 예정) 다시금 감을 잡기 위해 이코테 책을 앞에서부터 다 풀기로 했다. 큰 수의 법칙 배열의 주어진 수를 M번 더해 가장 큰 수를 만드는 문제로 이때 특정 인덱스의 수는 연속으로 K번을 초과해 더할 수 없다. 처음 이 문제를 풀 때는 [가장 큰 수를 K번, 그 다음으로 큰 수 1번]을 반복해서 가장 큰 수를 구했다. 하지만 이는 비효율적인 방법이었고 알맞은 수식을 찾아내서 한 번에 해결할 수 있었다. #define _CRT_SECURE_NO_WARNINGS #include #include #include usi..
