집주변이 최고야

들어가며: 최단경로 알고리즘, 다익스트라 란? 다익스트라 알고리즘 동작 과정 heapq 란? heapq 을 사용한 다익스트라 알고리즘 구현 관련 문제 들어가며: 최단경로 알고리즘, 다익스트라 이란? 최단 경로 알고리즘은 현재 위치에서 가고자 하는 위치까지 가장 짧은 경로를 찾는 알고리즘을 의미 다익스트라 알고리즘은 최단 경로 알고리즘 종류 중 1가지. (다익스트라, BFS, 벨만-포드, 플로이드, a* ...) 다익스트라 알고리즘은 음의 간선을 표현할 수 없음. (음의 간선 표현은 벨만포드 알고리즘을 활용) 다익스트라 알고리즘은 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 해당 포스팅은 이것이 코딩 테스트다 를 참고하여 작성하였습니다. 다익스트라 알고리즘 동작..

문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1 개의 팀이 존재한다. 이때 선생님은 "팀 합치기" 연산과 "같은 팀 여부 확인" 연산을 사용할 수 있다. 1. "팀 합치기" 연산은 두 팀을 합치는 연산이다. 2. "같은 팀 여부 확인" 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, "같은 팀 여부 확인" 연산에 대한 연산 결과를 출력하는 프로그램을 작성 입력 조건 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다 다음 M개의 줄에는 각각의 연산이 주어진다. "팀 합치기" 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 ..

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에..

문제 철수는 온라인으로 컴퓨터공학강의를 듣고 있다. 이때 각 온라인강의는 선수강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저. 들어야만 해당강의를 들을 수 있다. 예를들어 '알고리즘’ 강의의 선수 강의로 '자료구조'가 존재한다면, ‘자료구조를 들은 이후에 ‘알고리즘' 강의를 들을 수 있다. 철수는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번강의의 선수 강의로 1번과 2번강의가 있고, 1번과 2번강의는 선수강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자. 1번 강의: 30시간 2번 강의: 20시간 3번 강의: 40시간 이 경우 ..

위상 정렬이란? 진입차수와 진출차수 위상정렬 알고리즘 동작 흐름 위상정렬 알고리즘 동작 과정 예시 위상정렬 특징 위상정렬 구현 관련 문제 위상 정렬이란? 위상 정렬은 정렬 알고리즘의 일정 사이클이 없는 방향 그래프의 모든 노드의 방향성에 거스르지 않도록 순서대로 나열하는 것 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (O) 자료구조 → 고급 알고리즘 → 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 흐름 과정 (queue를 사용) A. 진입차수가 0인 모든 노드를 큐에 넣는다. B. 큐가 빌 때까지 다음의 과정을 ..

서로소 집합 이란? 일반적인 서로소 집합 자료구조 경로 압축 사이클 판별 서로소 집합(Disjoint Sets) 이란? 공통 원소가 없는 두 집합 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리고 한다. 서로소 집합 자료구조는 두 종류의 연산으로 나누어짐 1. 합집합(Union): 두 개의 원소가 포함된 하나의 집합으로 합치는 연산 2. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 흐름은 다음과 같음. 1. 합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인 A와 B의 루트 노드 A..

신장트리 란? 크루스칼 알고리즘 이란? 크루스칼 알고리즘 구현 관련 백준 문제 신장 트리(Spanning Tree) 란? 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프 n 개의 정점이 있다면 신장 트리의 간선 수는 n-1 개 최소 신장 트리(Minimum Spanning Tree)는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리 가중치는 거리, 비용, 시간 등 여러가지로 응용 가능 최소 신장 트리의 대표적인 알고리즘은 프림(Prim), 솔린(Sollin), 크루스칼(Kruskal) 알고리즘이 존재 Prim 알고리즘 최초 선택된 정점에 연결된 간선들 중에서 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘 간선의 개수 N, 노드의 개수가 E 시간복잡도 O(N^2) 또는 힙을..

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 예제 입력1 3 8 0 ..

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 ..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력1 5 17 예제 출력1 4 풀이 from collectio..