본문 바로가기

알고리즘

 (82)
Codeforces Round #784 (Div. 4) 들어가기 전에 고민 없이 바로 풀었던 문제는 정리하지 않았습니다. 지문은 이해했지만, 어떻게 풀지에 대해 고민해도 풀지 못한 것만 정리했습니다. D. Colorful Stamp https://codeforces.com/contest/1669/problem/D 2칸짜리 스탬프를 찍는 문제. 찍은 곳에 또 찍을 수 있고, 찍은 걸 회전할 수 있다.(스탬프 반대로 찍는다.) 단, 스탬프가 범위 밖으로 나가면 안 된다. 즉, 길이가 1이면 무조건 NO 풀이 문자 W를 기준으로 split한다. 만약, 문자열이 R이나 B만 있는 경우 NO를 출력 왜냐하면 스탬프는 범위 밖으로 찍을 수 없기 때문에 어떠한 경우에도 R이나 B 하나는 있어야 한다. 못푼 이유 WBW에서 NO가 난 것을 보고 겹쳐찍을 수 없는 경우(범위..
백준 [1045] 도로 무난한 최소 스패닝 트리 문제 문제 설명이 좀 난해할 뿐이지, 기본 개념 문제와 별 차이는 없다. https://www.acmicpc.net/problem/1045 1045번: 도로 0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, www.acmicpc.net 문제 요약을 하자면 다음과 같다. i < j 인 간선들 중에서 i가 작은 순으로 나열한다. i 가 같다면, j가 작은 순으로 나열 이 때 모든 도시가 연결되있지 않으면 -1 간선의 수가 M개가 되지 못하면 -1 그 후, 상위 M개의 간선에서 시작점과 끝점의 index 카운팅 후..
백준 [16297] Eating Everything Efficiently DP + 위상 정렬 문제 수학적 센스가 필요한 문제다. DFS로도 풀 수 있다. https://www.acmicpc.net/problem/16297 16297번: Eating Everything Efficiently Margriet A. is in pizza heaven! She has bought a oneday access pass to Pizza World. Pizza World is a food festival, where all stands have their own special type of pizza. Margriet would really like to try many different types of pizza, but she thinks that www.acmicpc.net 문제를 요..
백준 [2637] 장난감 조립(JAVA) 2차원 dp 테이블을 이용했다. 완성품 즉, 엔드 포인트가 N이라고 했으니 이 N을 기준으로 각 부품들의 개수를 구해주면 된다. 각 중간 부품들과 완제부품들에 기본 부품이 몇 개나 필요한지 모두 적어보면 감이 잡힐 것이다. 코드 더보기 import java.io.*; import java.util.*; class Main { static int N, M; static int[] count; static int[][] dp; static ArrayList[] nodes; static StringBuilder answer = new StringBuilder(); public static void main(String[] args) throws Exception { input(); solve(); print(..
위상 정렬(topological sorting) 유향그래프에서 각 정점들이 한 방향으로 나열된 형태 정점 u와 v가 u -> v 순서일 때, 어떠한 경우에도 u -> v 순서가 유지된다. 이러한 특성 때문에 사이클이 존재하지 않는다. 주로 다음과 같은 곳에 사용된다. 1. 소프트웨어 공학에서 일정 계획 방법론인 PERT나 CPM 2. 스킬트리, 선수과목 같은 사전 작업같은 것이 필요한 작업들 물론, BFS/DFS만으로 풀 수 있지만 위상 정렬을 알면 더 쉽게 풀 수 있다. 위상 정렬의 수행 과정 2개 배열이 필요하다. 해당 정점에 연결된 간선의 수를 담는 배열 A 정점별로 간선 자료구조를 담는 배열 먼저, 자신을 가리키는 간선이 없는 정점들을 찾는다. 해당 정점에서 출발하는 간선이 있으면 지움 (배열 A의 카운트를 1 줄인다.) 만약, 해당 간선의 도..
최소 스패닝 트리(MST, Minimum spanning tree) 최소 신장 트리라고도 한다. 그래프에서 최소 스패닝 트리를 만들기 위해선 다음 조건을 만족해야 한다. 1. 모든 정점은 연결돼있다. 2. 사이클이 없어야 한다.(트리 형태이기 때문) 3. 최소 가중치를 가진 무방향 간선들로만 연결돼야 한다. (간선의 개수는 정점의 개수 - 1 개) 즉, 모든 정점을 사이클 없이 최소한의 비용으로 연결해야 한다. 그림으로 올바른 형태와 잘못된 형태를 보면 다음과 같다. 모든 정점을 최소한의 비용으로 연결한단 특성 때문에 통신, 운송 네트워크 등 공급과 관련된 연결망을 구축하는 문제들이 많다. 스패닝 트리를 만드는 알고리즘은 크게 2가지가 있다. 각각 유리한 점이 있고, 특정 풀이를 쓰도록 강요하는 문제는 많이 없기 때문에 편한걸 쓰면 된다. 1. 크루스칼 알고리즘 가중치가..
BFS(breadth first search) 그래프 순회 방법 중 하나 DFS가 깊이(depth)라면, BFS는 너비(breadth) 우선 탐색이기 때문에 정점에서 인접한 정점들을 우선 탐색한다. 주로 큐를 이용해 구현한다. 우선순위 큐로 구현한다면 다익스트라 알고리즘이 된다. BFS 진행은 3단계로 나눌 수 있다. 1. 시작 index를 정한다. 2. 정점의 이동반경을 확인한다. 3. 방문하지 않은 정점이 있다면, 탐색 큐에 넣어준다. BFS 탐색 순서는 다음과 같다. 시작 index는 1이라 가정한다. 인접 리스트에서 BFS 코드 더보기 import java.io.*; import java.util.*; class Main { static ArrayList[] graph = new ArrayList[10]; public static void m..
DFS(depth first search) 그래프 순회 방법 중 한가지 BFS가 너비(breadth)라면, DFS는 깊이(depth) 우선 탐색이기 때문에 정점에서 가장 멀리 떨어진 곳을 먼저 탐색한다. 주로 재귀를 통해 구현하기 때문에 백트래킹과 유사점을 갖는다. DFS 진행은 4단계로 나눌 수 있다. 1. 현재 정점과 인접한 간선들을 본다. 2. 해당 간선으로 통하는 정점을 방문했는지 본다. 3. 방문하지 않았으면 방문한다. 4. 막혔으면 되돌아간다. 다음 그래프를 DFS로 탐색하는 순서다. 왼쪽 간선부터 탐색하는 방법이다. 또한, 방향이 없는 무방향 그래프이다. 진행 순서를 붙이니 좀 지저분해 보이지만, 피보나치 수열을 재귀로 진행했을 때와 같다. 빨간 선은, 방문할 정점이 있는 노드로 호출되는 방향이다. 파란 선은, 갈 곳이 더 없기 때문..

티스토리툴바