본문 바로가기
반응형

개발/Algorithm

 (98)
[백준] 평행선(python) 백준, 평행선 2358번: 평행선 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. www.acmicpc.net TL;DR 해시(Hash) 문제 요약 1. 평면 상에 주어진 n개의 점 중 서로 다른 두 점을 선택해서 만들 수 있는 x축 또는 y축에 평행한 직선이 몇 개나 있는지 출력하라. - 평면 상에 존재하는 점들로 만들 수 있는 x축 또는 y축에 평행한 직선의 수를 구하는 문제이다. - 문제 상에 숨겨져 있는 뜻이 있는데 다음과 같은 경우이다. - (1, 2), (1, 3), (1, 4)와 같이 입력이 주어졌을 때, 만들 수 있는 직선의 수는 총 3C2..
[백준] 지름길(python) 백준, 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net TL;DR 최단 경로 찾기 - 다익스트라 알고리즘(Dijkstra algorithm) 문제 요약 1. D킬로미터의 고속도로에 존재하는 지름길을 이용했을 때 가장 짧은 거리를 출력하는 프로그램을 작성하라. - 0부터 D 킬로미터 떨어진 고속도로에서 지름길들에 대한 정보가 주어질 때 각 길을 사용했을 때 최단 거리로 목적지에 도착할 수 있는 거리를 계산하면 되는 프로그램이다. 입출력 형태 예시 1 :: 이 경우 가장 짧은 경로는 0 ~ 50..
[백준] 좋은 단어(python) 백준, 좋은 단어 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net TL;DR 스택(Stack) 문제 요약 1. A와 B로 이루어진 문자열에 대해서 A와 B끼리 다른 선과 교차되지 않고 선을 그을 수 있는 좋은 문자의 수를 찾아라. - 다른 선과 교차되지 않고 선을 긋는다는 것은 적어도 A와 B가 하나씩 교차되는 형태가 없어야 한다는 뜻이다. - 스택에 문자를 하나씩 넣어가며 비교하는 방법으로 문제를 해결할 수 있다. 입출력 형태 예시 1 :: ABAB의 경우는 A와 B를 서로 선으로 연결했을 때 두 선이 서로 교차되기 ..
[백준] 최대 힙(python) 백준, 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net TL;DR 우선순위 큐(Priority queue) 문제 요약 1. 입력받은 X가 자연수라면 배열에 넣고 0이라면 배열에 있는 값 중 가장 큰 값을 출력하고 값을 배열에서 제거한다. - 입력에 따라 수행되는 구문이 다르며, 0이 입력되었을 때 배열 내에서 가장 큰 수를 출력해야 한다. - 이를 완전 탐색으로 풀 때, 최악의 경우 O(n^2)가 되므로 다른 방법을 찾아야 한다. - 가장 큰 값에 우선순위를 두어 우선순위 큐를 사용..
[백준] 콘서트(python) 백준, 콘서트 16466번: 콘서트 HCPC (Hanyang Completely Perfect Celebrity)는 한양대학교 최고의 가수에게 주어지는 칭호이다. 한양대학교는 매년 최고의 HCPC를 선발한다. HCPC가 되기란 여간 어려운 게 아니다. 매일 아침 날달걀을 까먹 www.acmicpc.net TL;DR 이진 탐색(Binary search) 문제 요약 1. 1차 티켓팅에서 팔린 티켓의 정보가 주어진다. 2. 2차 티켓팅 때 1차 티켓팅에서 팔리지 않은 티켓 중 살 수 있는 가장 작은 번호의 티켓을 출력한다. - 1차 티켓에 팔린 티켓 정보를 활용하여 2차 때 구할 수 있는 티켓 번호 중 가장 작은 번호를 찾아 추력하면 된다. - 티켓의 수와 번호의 수가 매우 크기 때문에 완전 탐색으로 풀 경우..
[백준] 편의점(python) 백준, 편의점 14221번: 편의점 처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000) www.acmicpc.net TL;DR 다익스트라 알고리즘(Dijstra algorithm) 문제 요약 1. 편의점으로부터 가장 가까운 지점에 있는 집 후보의 정점 번호를 출력하라. 2. 거리가 같은 곳이 여러 군데라면 정점 번호가 낮은 곳을 출력하라. - 편의점과 집이 정점, 각 정점의 가중치가 있는 그래프에서 최단 거리 지점을 찾는 문제이다. - 편의점 노드와 집 노드가 따로 분리되어 있기 때문에 이를 사용하여..
[백준] 촌수계산(python) 백준, 촌수계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net TL;DR 너비 우선 탐색(BFS) 최단경로찾기 - 다익스트라 알고리즘(Dijkstra algorithm) 문제 요약 1. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하라. 2. 두 사람이 친척 관계가 없는 경우는 -1을 출력해야 한다. - 각 사람들이 노드, 노드 간의 길이는 1인 그래프의 형태를 생각할 수 있다. - 주어진 두 사람(노드) 간의 거리를 계산하는..
[백준] 연결 요소의 개수(python) 백준, 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 요약 1. 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오. - 모든 노드 사이의 움직일 수 있는 무향, 양방향 그래프가 주어질 때, 연결 요소의 개수를 구하는 프로그렘을 작성해야 한다. (연결 요소에 대해서는 입출력 형태에서 확인한다.) 입출력 형태 주어진 그래프를 그림으로 표..

티스토리툴바