본문 바로가기

알고리즘문제풀이

 (4)
[문제풀이] 백준 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 라..
[알고리즘] 서로소 집합 - Disjoint Sets 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1, 2}와 {3, 4}의 집합이 있다면 두 집합은 서로 서로소 관계이다. 만약 여기에 {2, 3} 의 관계를 나타낸다면 모두 서로소 관계가 아닌 것을 확인할 수 있다. 서로소 개념은 그래프 알고리즘에서 중요하게 사용되는 경우가 있어서 잘 알아두어야 한다. 그래서 서로소 집합 자료구조 (union-find 자료구조)는 서로소 부분 집합들로 나누어진 원소들을 처리하기 위한 자료구조라고 할 수 있다. 이는 union과 find 두 개의 연산자를 사용한다. union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 담당하고 find 연산은 특정한 원소가 속한 집합을 찾는 연산을 담당한다. 서로소 집합 알고리즘 기본적으로..
[알고리즘] Binary Search Binary Search 이진 탐색 알고리즘을 말 그대로 탐색 알고리즘이다. 하지만 단순하게 처음부터 마지막까지 순서대로 비교하면서 탐색하는 방법이 아닌, 탐색 범위를 좁혀가며 데이터를 찾아내는 방식이다. 이진 탐색 알고리즘을 적용하기 위한 조건으로 배열 혹은 리스트에 있는 데이터들은 정렬이 되어있어야 한다. 그리고 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하면서 원하는 데이터를 찾게 된다. 이진 탐색 알고리즘은 재귀호출을 이용하여 구현할 수도 있고, 반복문을 이용해서 구현할 수도 있다. Example Code def binary_search(source, target, start, end): if start > end: return None mid = (start + end) // 2 ..
[문제풀이] Stack - 괄호 1차 시도 n = int(input()) for idx in range(n): line = input() stack = [] for character in line: if character == '(': stack.append(character) elif character == ')': if len(stack) != 0: stack.pop() else: print("NO") stack = None break if stack is not None: if len(stack) == 0: print("YES") else: print("NO") 어렵지 않은 문제였다.

티스토리툴바