본문 바로가기

알고리즘

 (21)
[문제풀이] 백준 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명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 문제..
[문제풀이] 백준 1922번 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용..
[알고리즘] - 위상정렬 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 라..
[알고리즘] 그래프 이론 그래프 이론 코딩테스트에서 그래프이론을 활용하는 문제들은 대부분 난이도가 좀 있는 편이라고 생각한다. 지금까지 공부한 내용 중에서 DFS, BFS, 최단경로 알고리즘 모두 그래프를 이용하는 개념들이다. 알고리즘 문제에서 서로 다른 객체가 연결되어있다라는 내용이 내포되어있으면 가장 먼저 그래프 알고리즘 적용 여부를 판단해보아야 한다. 그래프 그래프는 정점과 간선으로 이루어진 자료구조 형태이다. 트리 또한 그래프의 일종이지만 트리는 방향성이 존재하고, 수직적인 관계를 가지고 있지만 그래프는 수직개념, 루트노드 등과 같은 개념이 없다. 즉 그래프는 네트워크 모델에 대한 관계를 나타낼때 효율적으로 사용될 수 있다. 대표적으로 지하철 노선도를 생각할 수 있다. 정점 - vertice : 노드라고 불리며 데이터가 ..
[알고리즘] Binary Search Binary Search 이진 탐색 알고리즘을 말 그대로 탐색 알고리즘이다. 하지만 단순하게 처음부터 마지막까지 순서대로 비교하면서 탐색하는 방법이 아닌, 탐색 범위를 좁혀가며 데이터를 찾아내는 방식이다. 이진 탐색 알고리즘을 적용하기 위한 조건으로 배열 혹은 리스트에 있는 데이터들은 정렬이 되어있어야 한다. 그리고 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하면서 원하는 데이터를 찾게 된다. 이진 탐색 알고리즘은 재귀호출을 이용하여 구현할 수도 있고, 반복문을 이용해서 구현할 수도 있다. Example Code def binary_search(source, target, start, end): if start > end: return None mid = (start + end) // 2 ..
[문제풀이] 백준 2579번 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제풀이 N = int(input()) score = [0] * 300 dp_table = [0] * 300 for i in range(N): score[i] = int(input()) dp_table[0] = score[0] dp_table[1] = max(score[0] + score[1], score[1]) dp_table[2] = max(score[0] + score[2], score[1] + score[2]) for i in range(3, N): dp_table[..

티스토리툴바