본문 바로가기

자료구조

(12)
[문제풀이] 백준 2252번 줄 세우기 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 문제..
[알고리즘] - 위상정렬 Topology Sort 정렬 알고리즘의 일종인 위상정렬 알고리즘은 '순서가 정해져 있는 일련의 작업을 수행할때' 사용하는 알고리즘이다. 즉 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것을 위상정렬이라고 한다. 예를들면 선수과목을 생각하면 편하다. B라는 과목을 듣기 위해서 A라는 과목을 필수로 들어야 한다는 것과 동일하다. 즉 순서가 정해져있는 일련의 작업을 의미하게 된다. Toplogy Sort Algorithm 위상정렬 알고리즘은 다음 순서로 동작한다. - 진입차수가 0인 노드를 큐에 넣음 - 큐가 빌때까지 다음 과정을 반복 - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 - 새롭게 진입차수가 0이 된 노드를 큐에 넣음 만약 이 과정에서 모든 원소를 ..
[알고리즘] 신장 트리, Kruskal 알고리즘 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 즉 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 신장트리는 코딩테스트에서 그리디 알고리즘 문제로 자주 출제되는 유형 중 하나라고 한다. 위 그림은 신장트리의 예시이며 모든 정점을 포함하면서 사이클이 존재하지 않는 구조를 띄고 있다. DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있으며 여러모양의 신장트리가 존재할 수 있다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간전으로 연결하여야 한다. 신장트리는 일반적으로 통신 네트워크를 구축할때 사용되기도 한다. Kruskal 알고리즘 신장트리에서 간선들의 가중치 합이 최소인 트리를 말한다. Minimum Spanning Tree ..
[문제풀이] 백준 1976번 여행가자 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라..
[알고리즘] Dynamic Programming Dynamic Programming Dynamic Programming에서 Dynamic programming은 딱히 의미 없는 용어이다. 그냥 Dynamic, 멋있어서 붙인 용어라고 한다. Dynamic programming은 Optimal Substructure(최적 부분 구조)와 Overlapping Subproblem(중복되는 부분 문제)를 만족할때 자주 사용한다고 한다. Optimal Substructure는 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 결과를 도출하고 그 결과를 모아 큰 문제를 해결할 수 있는 문제를 의미한다. Overlapping Subproblem은 동일한 문제를 반복적으로 해결하는 문제이다. Fibonacci Sequence 대부분 동적 프로그래밍 예제로서 피보나치..
[문제풀이] 백준 4673번 셀프 넘버 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net org_numbers = set(range(1, 10001)) gen_numbers = set() for number in org_numbers: keep = number while number > 0: keep += int(number % 10) number = int(number / 10) gen_numbers.add(keep) self_numbers = sorted(org_numbers-gen_numbers..
[알고리즘] 완전탐색 (Exhaustive Search) Exhaustive Search 완전탐색은 무식하게 문제를 풀어나가는 방식이라고 하는데, 필자 생각에는 무식하다는 표현은 어울리지 않는 것 같다. 대부분의 알고리즘 문제는 완전탐색으로 다 풀수 있을 정도로 강력한 방식이다. 물론 그래서 무식하다고 부를 수 있지만 사실 컴퓨팅 성능이 미친듯이 좋으면 어떤알고리즘을 쓰더라도 빠르게 결과를 볼 수 있다. 그래서 무식한 방법이라고 절대 무시하면 안된다. 완전탐색을 문제를 해결하기 위한 모든 경우의 수를 나열하고, 정답을 찾아가는 방법을 의미한다. 완전탐색에는 Brute-Force, Bitmask, Recursive Fuction, Permutation, BFS, DFS 알고리즘이 있다. 완전탐색은 탐색의 방법론을 의미하고 그 안에 다양한 알고리즘들이 있다. Br..
[문제풀이] 백준 14713번 앵무새 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 7차 시도 n = int(input()) lines = [] for i in range(n): lines.append(list(map(str, input().split()))) target = list(map(str, input().split())) for item in target: correct = False for idx in range(n): if len(lines[idx]) != 0: if item == lines[idx][0]: lines[i..