일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- backtracking
- 이분탐색
- Algospot
- 분리집합
- BOJ
- 알고리즘문제해결전략
- union-find
- acm
- stack
- 문자열
- 세그먼트트리
- 백트래킹
- DP
- 다이나믹프로그래밍
- 동적계획법
- 백준
- 그리디
- 너비우선탐색
- 완전탐색
- 누적합
- Greedy
- 분할정복
- 스택
- 종만북
- 알고스팟
- 재귀
- priority_queue
- 유니온파인드
- BFS
- DFS
- Today
- Total
목록전체 글 (105)
DAMPER's 낙서장
www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 처음에 이 문제를 보고 바로 동전DP를 떠올렸지만, 각 가방에 한 개의 보석만 넣을 수 있고, 각각의 가방에 넣을 수 있는 보석의 무게가 다르기 때문에 조금 다른 문제라 생각했다. 풀이 방법 용량이 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다. 예를들어, 아래와 같은 상황이라고 하자. 먼저 가방 용량을 오름차순으로 정렬하고, 보석을 무..
www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 전형적인 BFS 문제. 1번칸부터 100칸까지 있으며 10 X 10 맵으로 되어있다. 하지만 이 문제에서는 그냥 100칸짜리 1차원 배열에 넣어도 상관 없다. 1번칸에서 100번칸까지 가면 되는 문제. 주사위를 굴려 1칸부터 6칸까지 갈 수 있으며, 해당 칸에 사다리가 있으면 더 앞으로(+), 뱀이 있으면 뒤로(-) 움직이게 된다. 100칸 int 배열에 사다리, ..
www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제인가? 한번 생각하게 하는 문제. 언제 우리가 원하는 수를 만들 지 모르니 D, S, L, R 모든 연산을 해보고, 이미 한번 만났던 애들인지 한번 체크해보고 다음을 계산하게하여 푸는 문제. Queue에 연산결과(수)와 지금까지의 연산과정을 모두 넣어야하므로 std::queue 으로 진행하였다. 이 문제에서 키 포인트 1. 이미 연산했던 수 인지 아닌지 체크하기. -> 이미 연산했던 수라..
한 시작점에서 다른 모든 정점까지의 최단 거리(간선 가중치의 합이 최소)를 구하는 알고리즘 중 가장 유용한 알고리즘으로 다익스트라 알고리즘이 있다. 하지만 다익스트라 알고리즘은 음수 간선이 있는 그래프의 경우, 그 정당성이 보장되지 않아 벨만-포드 알고리즘을 사용해야한다. 벨만-포드 알고리즘은 음수 간선이 있는 최단 경로를 찾을 뿐만 아니라, 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우 알려주기도 한다. 벨만-포드 알고리즘 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히(?) 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 수행 과정에서 각 정점까지 최단 거리의 상한을 담은 배열 upper[]을 유지한다. 이 값은 알고리즘이 진..
모든 정점이 짝수점(정점의 차수가 짝수인 점)이고, 모든 간선이 하나의 컴포넌트에 포함되어 있다고 가정하자. 함수 findRandomCircuit(u) : 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 재귀적으로 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료. 함수를 실행하면 여러 부분 서킷이 생성될텐데, 전체를 포함하는 하나의 서킷을 원하므로 모든 부분 서킷들을 합쳐야한다. 부분 서킷이 생긴다는 말은 무슨 말일까? 어떤 정점에서부터 출발하는 간선이 하나가 아닌 여러개일 수 있는데, 이때 서킷의 정의에 따라 출발하는 간선만큼 해당 정점으로 오는 간선이 존재해야한다. -> 그만큼 부분서킷이 생긴다. 해당 정점에서 나가는 간선이 2개 존재한다면, 2개의 부분 서킷이 생긴다. 이..
출처 : algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 algospot.com 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서..