ProblemSolve

문제 바로 가기 > 2225번: 합분해 다이나믹 프로그래밍을 풀 수 있는 문제이다.알고리즘 풀이만약 입력에 예제처럼 6, 4가 주어졌다면6= 0(3번 더해서 0이 되는 경우) + 66= 1 (3번 더해서 1이 되는 경우) + 56= 2 (3번 더해서 2가 되는 경우) + 46= 3 (3번 더해서 3이 되는 경우) + 36= 4 (3번 더해서 4가 되는 경우) + 26= 5 (3번 더해서 5가 되는 경우) + 16= 6 (3번 더해서 6이 되는 경우) + 0 따라서 dp[K][N]: N이하의 정수를 K번 더해서 합이 N이 되는 경우의 수라고 한다면 위의 경우에는 다음과 같이 표현할 수 있다. dp[4][6]=dp[3][0]+dp[3][1]+dp[3][2]+dp[3][3]+dp[3][4]+dp[3][5]+d..

문제 바로 가기 > 4384번: 공평하게 팀 나누기0/1 냅색 알고리즘으로, DP로 풀 수 있다.이 문제는 '부분집합의 합' 문제의 변형으로 볼 수 있다. 우리의 목표는 전체 무게의 절반에 가장 가까운 부분집합을 찾는 것이다.2차원 boolean 배열 dp를 사용합니다.dp[i][j]는 i명의 사람을 선택하여 정확히 j 무게를 만들 수 있는지 여부를 나타낸다 (true/false)알고리즘1. dp 배열 초기화: dp[0][0] = true (0명으로 0kg을 만들 수 있음)2. 각 참가자에 대해:1명부터 전체 인원의 절반까지 선택하는 경우를 고려가능한 모든 무게 조합을 계산하여 dp 배열 갱신for(int i=0; i0; j--){ for(int k=totalWeight; k>=weights..

문제 바로가기> 11000번: 강의실 배정 그리디 알고리즘으로, 우선순위 큐를 이용해서 풀 수 있다. 1 ≤ N ≤ 200,000이므로 브루트포스를 돌리면 당연히 시간초과가 난다. 따라서 정렬을 이용한 우선순위 큐를 이용해 그리디 알고리즘으로 풀어야 한다.  정렬 기준그렇다면 어떤 기준으로 정렬을 해야할까?처음에 필자는 종료시각을 기준으로 (빨리 끝나는 시각 순으로 오름차순) 정렬을 해서 틀렸다...시작 시각으로 정렬을 해야 앞에서부터 차곡 차곡 강의 간의 텀을 짧게 해 배정이 가능한 것이었다. 종료 시간을 우선순위 큐에 넣고 비교정렬 자체는 시작 시각을 기준으로 하였지만, 결국 어떤 강의가 들어갈 자리를 찾기 위해서는 종료시각과 비교를 해야 한다.따라서 그러기 위해서는 종료 시각을 담는 우선순위 큐가 ..

문제 바로가기 > 20055번: 컨베이어 벨트 위의 로봇 단계마다 이동을 할 때 각 단계마다 다음 두 조건을 반드시 지켜야 한다.1. 로봇은 1번칸인 올리는 위치에서만 올릴 수 있다.2. 로봇은 N번칸인 내리는 위치에 도달하면 언제든지 내려야 한다. 각 단계마다 함수로 구현해준다. Step 1 . 벨트와 로봇 회전각 칸을 이동시켜준다로봇을 이동시켜준다이때, 위에 언급한 조건때문에 robot[N-1] (N칸) 위치와 robot[0] (1번째 칸) 위치를 false로 시켜줘야 한다.robot[N-1]=false: 내리는 위치에 도달하면 언제든 내려야 한다.robot[0]=false: 로봇은 올리는 위치에서 3번째 Step에서만 올릴 수 있지, 로봇이 2N칸에서 1칸으로 이동하면 안된다. public st..

문제 바로가기 > 2602번: 돌다리 건너기 완전탐색하면 시간초과가 나므로 dp를 사용해야 한다. 문제 설정두 개의 다리 angleBridge와 devilBridge가 있으며, 원하는 값 answer 대로 발판을 밟아 가며 끝까지 건너야 한다. 이때, 다리를 건너널 때는 두 개의 다리를 번갈아가면서 건너야 한다.DP 배열 설정dp[bridge][i][j]bridge: 현재 위치한 다리를 나타내며, 0은 악마의 돌다리, 1은 천사의 돌다리i: answer에서 현재까지 진행한 문자의 인덱스.j: 각 다리에서 현재 확인하고 있는 발판의 인덱스.초기화dp[0][0][n] 및 dp[1][0][n]은 각 다리의 시작점에서 아직 어떤 문자도 밟지 않은 상태를 나타내므로 1로 초기화DP 점화식일치: 만약 현재 다리의 ..

문제 바로가기 > 1629번: 곱셈 모듈러 성질과 분할 정복을 이용해 풀 수 있다. 분할 정복아래와 같이 계속해서 지수를 2로 나누어서 분할정복을 계속해서 해나간다.   이때, 지수가 홀수일 때는 마지막에 밑을 곱해주면 된다.    그럼 예제의 A = 10, B = 11 을 위 처럼 적용해보면 이렇다. 위 과정에서 지수는 절반으로 나누기 때문에 각 레벨에서 나뉜 두 지수를 모두 탐색할 필요없이 한 번만 구하면 된다.이를 코드로 옮겨보면 이렇게 짤 수 있다. 아래의 모듈러 공식을 이용해서 long이 오버플로우가 되지 않도록 계속해서 C의 나머지를 구해야 한다.   전체 코드import java.util.Scanner;public class _1629 { public static void main(St..

문제 바로가기 > 1202번: 보석도둑 얼핏보면 냅색 알고리즘이여서 DP를 이용해야 할것 같지만 가방에는 최대 한 개의 보석만 넣을 수 있다는 조건이 있다.그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있는 문제이다. 모든 가방에 대해 모든 보석을 검사하면 위 문제를 해결할 수 있으나, N과 K는 최대 30만이기때문에 O(9 x 10^10)으로 시간 초과가 난다. 따라서 O(N^2)보다 줄이기 위해서 우선순위 큐 자료구조를 이용해야 한다.보석은 무게에 대해 오름차순 정렬하되, 무게가 같을 경우 가격에 대해 내림차순 정렬한다.가방은 오름차순 정렬한다.모든 가방에 대해서 반복문을 수행한다.특정 가방의 무게보다 작은 보석의 가격을 모두 우선순위 큐에 집어넣는다. (이때, 우선순위 큐는 가격에 대해 내림차순 ..

문제 바로가기 > 12865번: 평범한 배낭 전형적인 0/1 냅색 알고리즘으로, DP로 풀 수 있다. 1. 초기화최대 무게 K를 수용할 수 있는 dp 배열을 선언하고, 크기를 K + 1로 설정하여 모든 인덱스를 0으로 초기화dp[j]는 무게 j일 때의 최대 가치를 저장2. 동적 프로그래밍을 통한 최대 가치 계산각 물건에 대해 반복을 수행, 물건의 무게를 weight, 가치를 valuedp 배열을 역순으로 갱신: 이는 각 물건을 한 번만 고려하도록 하여 중복을 방지dp[j] (무게 j에서의 최대 가치)는 dp[j] (현재 가치)와 dp[j - weight] + value (현재 물건을 추가했을 때의 가치) 중 더 큰 값으로 갱신j는 K부터 weight까지 감소하면서 계산3. 결과 출력dp[K]에 저장된 값..

https://www.codetree.ai/training-field/search/problems/series-of-bombs-detonating/description?utm_source=clipboard&utm_medium=text&page=9&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai  완전탐색, 시뮬레이션 문제이다. 1. 입력 받기: 폭탄의 개수와 각 폭탄의 위치를 입력 받는다.이때, 폭탄의 위치 인덱스를 배열에 저장하는데 이유는 폭탄의 위치 N이 최대 1,000,000,000까지이므로 예를 들어 boolean[] isBom..

문제 바로 가기 > 백준 20366번: 같이 눈사람 만들래? 정렬을 이용해 푸는 문제이다. 처음에는 아래와 같이 4중 for문을 이용해 풀려고 했으나 이렇게 풀면 N(4 ≤N≤ 600) 이여서 시간 초과가 난다.엘사가 만든 눈사람의 몸통 선택 → O(N)엘사가 만든 눈사람의 머리 선택 → O(N)안나가 만든 눈사람의 몸통 선택 → O(N)안나가 만든 눈사람의 머리 선택 → O(N)엘사가 만든 눈사람과 안나가 만든 눈사람의 키차이를 구하고 최소 비교➡️ 해당 풀이법의 시간 복잡도 : O(N4) → 시간 초과 그래서 몸통+머리를 합쳐서 눈사람을 우선 만들어서 정렬한 후에 이 눈사람의 뒷값과 비교를 한다.핵심은 정렬을 했기 때문에 현재 눈사람과의 차이가 가장 작은 눈사람은 내 바로 뒤의 인덱스에 있는 눈사람이..