📙 Algorithm Solving

알고리즘 문제) BOJ 1613. 역사 링크 : https://www.acmicpc.net/problem/1613문제 요약알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계를 찾아라시간 제한1초입력사건의 개수 N, 알고 있는 전후 관계 개수 KN : 400이하 자연수K : 4만 이하 자연수K개 줄에 사건의 전후 관계를 알고 있는 두 사건 번호가 주어짐a ba는 보다 먼저 발생사건의 전후 관계를 알고 싶은 사건 쌍의 수 SS : 5만 이하 자연수S개 줄에 서로 다른 두 사건 번호가 주어짐출력S개 줄에 걸쳐앞에 있는 번호의 사건이 먼저 일어났으면 -1뒤에 있는 번호의 사건이 먼저 일어났으면 1유추할 수 없으면 0을 출력접근법처음에 위상정렬로 풀려고 했는데, 생각해보니 나중에 알고 ..

알고리즘 문제) BOJ 10958. Ice Hockey World Championship 링크 : https://www.acmicpc.net/problem/10958문제 요약각 경기의 티켓 가격이 주어질때예산을 초과하지 않고 경기를 관람할 수 있는 방법의 수는?한 경기라도 다르게 관람하면 다른 케이스로 간주시간 제한1초입력두 개의 양의 정수 N과 M1 ≤ N ≤ 40, 1 ≤ M ≤ 10^18경기를 관람할 수 있는 경기 수와 예산N개의 양의 정수가 각각 공백을 두고 주어짐(각 경기의 비용)10^15이하출력경기를 관람할 수 있는 방법의 수최대 2^40가지접근법N이 최대 40까지 가능하므로, 여기서 경기를 볼 수 있는 모든 케이스를 살핀다면 최악의 경우 2^40까지 가능해진다.따라서 N을 2개의 그룹으로 나..

알고리즘 문제) BOJ 1450. 냅색문제 링크 : https://www.acmicpc.net/problem/1450문제 요약N개의 물건이 존재하며,최대 C만큼 넣을 수 있는 가방 존재이때, N개의 물건을 가방에 넣는 방법의 수는?시간 제한1초입력N CN : 1 ~ 30C : 0 ~ 10억물건의 무게가 차례대로 한줄에 주어짐무게 : 1 ~ 10억출력가방에 넣는 방법의 수는?접근법완전탐색으로 먼저 접근하기가방은 선택O or 선택 X 두 케이스로 나뉜다.백트랙킹을 통해, 가리키는 가방을 선택하는 경우, 선택하지 않는 경우로 나눠서 재귀 호출 ⇒ 이때, 무게 합이 C보다 큰 경우는 가지치기문제점 : 완탐으로 할 경우 최악의 경우 케이스가 2의 30승까지 가능하므로 시간초과그렇다고 dp로 접근한다면 메모이제이션..

알고리즘 문제) BOJ 13398. 연속합 2 링크 : https://www.acmicpc.net/problem/13398문제 요약n개의 정수로 이루어진 임의의 수열이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다수는 한 개 이상 선택해야 한다수열에서 수를 하나 제거할 수 있다시간 제한2초입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수출력첫째 줄에 답을 출력접근법부분 연속 수열의 합 중 가장 큰 값을 구하는 문제이때, 중간에 하나 제거가 가능함매개변수 start, end를 통해 부분 연속 수열이 시작됐는지, 끝나는지 체크하도록 했다0 :..

알고리즘 문제) BOJ 1727. 커플 만들기 링크 : https://www.acmicpc.net/problem/1727문제 요약여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명각 사람의 성격은 어떤 정수로 표시최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하자시간 제한2초입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)다음 줄에는 n명의 남자들의 성격그 다음 줄에는 m명의 여자들의 성격성격은 1,000,000이하의 자연수출력성격의 차이의 합의 최솟값을 출력접근법그리디 + dp로 풀어야 한다.최대한의 커플을 만들면서, 커플들의 성격차 합이 최소가 되게 해야함최대한의 커플을 만든다 == min(남학우 수, 여학우 수)만큼 만들어져야 함또한, 각 성별의..

알고리즘 문제) BOJ 1637. 날카로운 눈 링크 : https://www.acmicpc.net/problem/1637문제 요약정수가 여러 개 모여있는 정수더미특정 정수 하나만 홀수개 존재 & 나머지 정수는 짝수개 존재이때 정수 더미에서 홀수개 존재하는 정수를 찾기시간 제한2초입력입력의 개수 N1 ≤ N ≤ 20000N개의 줄에 정수 A, C, B가 주어지는데,A, A+B, A+2B, …, A+kB (A+kB ≤ C) 정수들이 더미안에 존재함을 의미A, B, C는 1~ 2,147,483,647이하 정수N개의 입력이 나타내는 정수를 모두 포함출력홀수개 존재하는 정수와, 해당 정수가 몇 개 들어있는지 출력홀수개 존재하는 정수가 없다면 NOTHING접근법완전탐색으로 먼저 생각해보장..각 정수를 일일이 구하고..

알고리즘 문제) BOJ 1043. 거짓말 링크 : https://www.acmicpc.net/problem/1043문제 요약지연이는 거짓말하는 걸 좋아한다.파티에가서 거짓말을 하기 위해서는, 진실을 아는 사람이 있으면 안되고, 진실을 아는 사람과 같은 파티였던 사람이 있는 곳도 안된다.이때, 거짓말을 할 수 있는 파티 개수는?시간 제한2초입력사람 수 N, 파티 수 MN과 M은 50이하 자연수진실을 아는 사람 수와 사람의 번호가 주어짐사람의 번호는 1~N진실을 아는 사람 수는 0이상 50이하 정수M개의 줄에는 각 파티마다 오는 사람 수와 사람 번호가 차례로 주어진다.각 파티에 오는 사람 수는 1이상 50이하 정수출력거짓말을 할 수 있는 파티 개수접근법UNION & FIND로 풀었다,같은 파티에 참석한 경우..

알고리즘 문제) BOJ 10227. 삶의 질 링크 : https://www.acmicpc.net/problem/10227문제 요약R*C 격자의 도시가 존재이때 각 칸에는 퀄리티 랭크가 표시되어있는데, 범위는 1~R*C내에서 표현된다.퀄리티랭크가 작을수록 질이 높은 것이고, 클수록 질이 낮은 것이다.이때, 도시 안에서 H*W(H홀수, W홀수)크기의 영역을 돌며 퀄리티랭크의 중간값 중 가장 질이 높은(수가 가장 작은)값을 찾으려 한다.영역안에서 중간값보다 작은 랭크 수와 큰 랭크수가 같을 경우 중간값이라 정의이때 H*W영역 중 퀄리티랭크의 중간값중 가장 질이 높은 값을 찾아라시간 제한5초입력4개의 정수 R,C,H,WR과 C는 도시 크기이며, 가능한 범위는 1~3000H와 W는 영역의 크기이며 항상 홀수이고,..

알고리즘 문제) BOJ 4179. 불! 링크 : https://www.acmicpc.net/problem/4179문제 요약지훈이가 불에서 타기 전에 얼마나 빨리 탈출할 수 있는지 판단하기불은 매 분마다 한칸씩 수평, 수직으로 이동(네방향 확산)지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다지훈이와 불은 벽을 통과할 수 없다시간 제한1초입력R C1 ≤ R,C ≤ 1000행, 열R개의 줄에 맵이 주어짐‘#’ : 벽‘.’ : 빈칸‘J’ : 지훈이 초기 위치‘F’ : 블이 난 공간J는 입력에서 하나만 주어진다.출력지훈이가 미로를 탈출 할 수 없다면 IMPOSSIBLE가능하다면, 가장 빠른 탈출 시간 출력접근법bfs 알고리즘 사용우선 지훈이가 이동 가능한 경우는 여러 케이스가 있다큐에 bfs를 돌며 이동..

알고리즘 문제) BOJ 5913. 준규와 사과 링크 : https://www.acmicpc.net/problem/5913문제 요약5*5 크기의 과수원이 존재하며, 가장 왼쪾 위 칸은 (1,1), 가장 오른쪽 아래 칸은 (5,5)이다.이때 구역 k개를 제외한 구역에 사과 나무가 하나씩 존재한다준규는 (1,1)에서 사과를 수확, 해빈이는 (5,)에서 수확을 시작이때, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다.준규와 해빈이는 모든 사과를 수확하고 마지막에 같은 칸에서 만나려고 한다.이때, 사과를 수확하는 방법의 수를 구해라수학을 마친 칸으로는 다시 이동하지 않는다.또, 마지막을 제외하고 같은 칸에서 만날 수 없다.시간 제한1초입력k ( 0 ≤ k ≤ 22, 짝수)k개줄에는 사과 나무가 없는 칸의 위치가..