두부의 코딩일기

플로이드-워셜 (Floyd-Warshall) vs 다익스트라 (Dijkstra) 다익스트라 플로이드-워셜 사용 목적 단일 출발점 최단 경로를 찾음 모든 정점 쌍 간의 최단 경로를 찾음 가중치 제약 음의 가중치를 가진 간선을 처리할 수 없음 음의 가중치를 가진 간선을 처리할 수 잇음 기본 구조 그래프의 인접 리스트 혹은 인접 행렬을 사용함 그래프의 인접 행렬을 사용함 시간 복잡도 O(V+E)logV (우선 순위 큐를 사용했을 경우) O($N^{3}$) 알고리즘 유형 그리드 알고리즘 동적 프로그래밍 플로이드-워셜 개요 플로이드-워셜은 a → b 로 가는 비용과 a → c → b 로 가는 비용 중에 더 적은 값을 최단 거리로 판단하는 알고리즘으로 다음과 같은 점화식을 가진다. dpab= Math.min(dpa..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✅ 실버 Ⅰ 🔶 풀이 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오. 다이나믹 프로그래밍 문제다. 예제 2번으로 규칙을 찾아보겠다. 카드팩은 총 5개이고, 카드 5개를 구매하기 위해 지불해야 하는 최대 금액을 찾으면 된다. P1 = 10, P2 = 9, P3 = 8, P4 = 7, P5 = 6 card[1] = 10, card[2] = 9, card[3] = 8, card[4] = ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 최소 한 개의 모음과 두 개의 자음으로 구성된 길이 L의 암호를 출력하라. 백트래킹으로 풀어야 된다. 해당 문제에서는 알파벳이 증가하는 순서로 배열되었을 것이라고 한다. 정렬은 필수다. 우선, 이미 선택한 알파벳보다 큰 알파벳을 선택해서 임의의 L 길이를 가진 암호를 만든다. L 길이가 완성됐다면 최소 모음 1개, 자음 2개를 가지고 있는지 판단해 준다. public static ..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라. 모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라. 다익스트라를 두 번 나누어서 해결했다. 1. X에서 각 마을까지의 최단 거리 2. 각 마을에서 X까지의 최단 거리 (역방향) 위 두가지를 구..

REST (Representational State Transfer) 정의 웹 서비스를 설계하고 구현하기 위한 아키텍처 스타일로 HTTP 프로토콜과 리소스 지향적인 구조를 기반으로 클라이언트와 서버 간의 통신을 단순화하고 효율적으로 처리할 수 있도록 함. ✅ 리소스 : 웹 서비스에서 클라이언트가 요청하고 서버가 제공하는 데이터 또는 객체를 말하며, 고유한 식별자(URI)를 가지고 있다. HTTP URI(Uniform Resource Identifer)를 통해 자원(Resource)을 명시하고, HTTP Method(POST, GET, PUT, DELETE)를 통해 해당 자원에 대한 CRUD Operation을 적용하는 것을 의미한다. ✅ URI : 인터넷상에서 고유한 리소스를 식별하기 위한 문자열로 UR..

세그먼트 트리(Segment Tree)의 필요성 특정 구간 내 쿼리를 효율적으로 처리하기 위한 자료구조다. ✅ 구간 쿼리 : 배열 또는 리스트와 같은 시퀀스 데이터에서 특정 구간에 대한 정보를 검색하거나 수정하는 작업을 말한다. 위와 같이 arr[50]의 배열이 있다고 가정했을 때, arr[3] ~ arr[10]까지의 합을 구하고, 특정 값을 변경하려는 행위가 필요하다고 가정해보자. 1. 단순 반복문을 통한 덧셈 연산 이 방법은 O(N)의 시간복잡도를 가지고 있으며, 이를 M번 수행한다고 가정한다면 O(NM)의 시간복잡도를 가지게 된다. 특정 값 A → B로 변경하는 것은 O(1)의 시간복잡도를 가지고, 이를 M번 수행한다면 O(M)의 시간복잡도를 가진다. ▶ 시간복잡도: O(NM) + O(M) = O(..

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 dp[날짜][지각 횟수][연속으로 결석한 횟수] 를 기준으로 dp 배열을 생성했다. 개근상을 받을 수 있는 조건은 총 6가지다. 1. 0번 지각, 0번 연속 결석 → dp[N][0][0] 2. 0번 지각, 1번 연속 결석 → dp[N][0][1] 3. 0번 지각, 2번 연속 결석 → dp[N][0][2] 4. 1번 지각, 0번 연속 결석 → dp[N][1][0] 5. 1번 지각, 1번 연..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 해당 문제는 완전 탐색으로 진행하면 시간 초과가 발생한다. 때문에 정렬과 우선순위 큐를 이용해서 해결할 수 있다. 위 그림은 예제 1번을 보기 좋게 표현했다. 수업이 끝난 직후에 다음 수업을 시작할 수 있다고 했으므로 강의실 2개를 사용한다. 우선, 시작 시간을 기준으로 오름차순 정렬을 해줘야된다. 마감 시간을 기준으로 오름차순 정렬하게 되면 아래와 같은 상황에서 반례가 발생한다. 4 1 2 1 4 2 6 4 5 1. (1..

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net ✅ 플레티넘 Ⅴ 🔶 풀이 경찰차 A (1, 1) 과 경찰차 B (N, N) 이 있다. 순서대로 사건이 일어났을 때, 경찰차가 이동하는 최소 거리의 합을 구하라. 해당 문제도 dp다. 하지만 점화식을 찾는 dp는 아니고, dfs를 이용해서 문제를 해결해나가면 된다. dp[one][two] 는 "경찰차 A의 위치가 one번째 사건이고, 경찰차 B의 위치는 two번째 사건에 위치..

https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net ✅ 플래티넘 Ⅴ 🔶 풀이 내가 선택한 플래티넘 문제는 개인적으로 가장 어려워하는 dp.. 음의 차이를 나타내는 힘든 정도의 최솟값을 구하라. 문제의 이해를 돕기 위해 편의상 상덕이를 A, 희원이를 B로 하겠다. dp 배열은 각자 마지막으로 부른 음을 기준으로 힘든 정도의 최솟값을 저장해줬다. 현재 상태: dp[A가 마지막으로 부른 음][B가 마지막으로 부른 음]; A가 다음으로 부를 경우: dp[n..