일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 다이나믹프로그래밍
- union-find
- 완전탐색
- Algospot
- stack
- 재귀
- 종만북
- backtracking
- DFS
- 백트래킹
- 백준
- acm
- Greedy
- 스택
- 이분탐색
- 너비우선탐색
- 분리집합
- 유니온파인드
- priority_queue
- 알고스팟
- DP
- BOJ
- 세그먼트트리
- 알고리즘문제해결전략
- 그리디
- BFS
- 분할정복
- 누적합
- 동적계획법
- 문자열
- Today
- Total
목록Problem Solving (85)
DAMPER's 낙서장
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 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서..
오일러 서킷(Eulerian circuit) : 그래프의 모든 간선을 정확히 한번씩 지나서 시작점으로 돌아오는 경로. 오일러 경로(Eulerian path) : 그래프의 모든 간선을 정확히 한번씩 지나는 경로. 시작점과 도착점이 다르다. 무향 그래프에서 오일러 서킷을 찾으려면? 먼저 오일러 서킷의 존재 여부를 확인한다. 1. 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우는 오일러 서킷이 존재할 수 없다. 그래프의 정점이 둘 이상의 컴포넌트로 쪼개져 있어도, 간선들이 한 컴포넌트에 있다면 오일러 서킷은 존재한다. 그래프의 모든 '간선'을 지나 시작점으로 되돌아오기만 하면 되기 때문. 2. 도착점에 인접한 모든 간선은 이미 지나온 상황이어야한다. 3. 도착점에 인접한 간선의 수는 항상 짝수이다..