구현 문제는 어려운 문제는 너무 어렵다.. 모든 문제가 그렇지만 구현과 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..
문제 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 사이에 'X' 혹은 '+'를 넣어 만들 수 있는 가장 큰 수 구하기 모든 연산은 왼쪽부터 이뤄진다고 가정 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어짐 (1
문제 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 함 만들 수 있는 모험가 그룹의 최대 개수 구하기 입력 조건 첫째 줄에 모험가의 수 N이 주어짐 (1 값 갱신해주기 (count는 0으로, answer ++) #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int n[100001]; int main() { int N; int i; int answer = 0; int count = 0; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &n[i]); } sort(n, n + N); for (i = 0; i < N; i++) { coun..
다익스트라 알고리즘 최소 비용을 구해야 할 때 사용 가능 한 지점에서 다른 특정 지점까지의 최단 경로 구해야 할 경우에 사용 가능 음의 간선이 없을 때 정상 동작함 (현실에는 음의 간선의 길이 없어서 GPS의 기본 알고리즘으로 사용됨) 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택해 과정을 반복함 동작 원리 dist[] 에 비용 저장, INF로 초기화 되어 있음 출발 노드 설정, 최단 거리 초기화 (dist[] INF로 초기화) 출발 노드를 방문한 노드로 체크하기 출발 노드와 연결되어 있고 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택, 방문했다고 체크 이 노드에서 다른 노드로 가는 비용을 계산해 dist[] 갱신 3,4 과정을 반복 구현 방법 동작 원리대로 구현하기 - 시간 복잡..
dp[i] = dp[i - 1] +1; dp[i] = dp[i - 1]++; dp[i] = ++dp[i - 1]; 위의 세 연산 값이 전부 다르게 나옴 ++,--는 간단한 변수 값 변화에만 사용하기!! 첫 번째 값 : 제대로 나옴 두 번째 값: dp[i]에 dp[i-1] 값만 계속 넣고 dp[i-1]++ (의미 없음) 을 해서 값이 0만 저장됨 세 번째 값: dp[i]에 ++dp[i] 값을 넣은 후 dp[i-1](의미 없음)을 해서 값이 더 저장됨
동적 계획법 (Dynamic Programming) 하나의 문제는 한번만 풀게 하는 알고리즘 메모리 공간을 약간 더 써서 연산 속도를 비약적으로 증가 시킬 수 있음 메모이제이션 - DP를 구현하는 방법 중 하나 - 메모리(배열)에 한 번 구한 결과를 메모해두고 같은 식을 호출하면 그대로 가져옴 (캐싱) 분할 정복과 다른점 : DP는 분할한 문제들이 서로 영향을 미침 DP 구현 방법 탑다운(하향식) 방식 : 재귀를 이용해 DP 푸는 방법 (큰 문제 해결 위해 작은 문제 호출) 보텀업(상향식) 방식 : 반복문 이용해 DP 푸는 방법 (작은 문제부터 답을 도출함) 1. 점화식 찾기 2. dp 값이 정해져 있다면 넣고 시작하기, dp 초깃값은 큰 값 혹은 작은 값 넣기 3. 모든 dp의 값을 (점화식으로 구한 ..
이분 탐색 배열이 정렬되어 있어야 사용 가능 반으로 쪼개면서 탐색함 시간 복잡도 O(logN) (순차 탐색은 O(N)) 시작점, 중간점, 끝점을 가리키는 변수를 가짐 재귀, 반복문으로 구현 가능 1. 시작점, 중간점, 끝점 (left, mid, right) 정하기 2. 중간점과 찾는 값 비교 후 작으면 right를 mid-1로, 크면 left를 mid+1로 한 후 mid 값 다시 정하기 3. 2번을 반복 Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 이분 탐색으로 결정 문제를 해결하면서 범위를 줄여 최솟값, 최댓값을 찾음 결정 문제인지 아닌지의 차이 (이분탐색과) 1. left, mid, right를 정한 후 mid가 조건을 만족하는지 확인 2. 만족하지 않으면 mid 이전의 ..
