해당 글은 https://8iggy.tistory.com/104 를 참고하여 썼습니다. DFS 진짜 어렵다... 너무 어렵다. 그래도 해야겠지. 가봅시다. DFS는 그래프 탐색을 할 때 사용하는 알고리즘으로, Depth First Search의 줄임말이다. 깊이 우선 탐색을 뜻하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 stack이나 재귀함수를 이용해서 구현할 수 있다. DFS의 동작과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 노드가 없다면 스택에서 최상단 노드를 꺼낸다. 3. 2의 과정을 더 이상 수행할 수 없을 때까지 반복..
자료구조 및 알고리즘
DP 도대체 이름이 왜 동적 계획법인지 궁금한 알고리즘이다. 지금까지 봤을 때는 점화식 세우기가 핵심인 알고리즘인 거 같다. 동적 계획법이란 최적화 이론의 기술로 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계방법이다. 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출한다. 연산 횟수를 기가 막히게 줄여주며 이에 따라 시간복잡도가 개선되는 장점을 가지고 있다. DP를 적용하기 위한 2가지 조건 동적 프로그래밍에 대해 찾아보는데 공통점이 여럿 있었다. DP를 사용하기 위해서는 두 가지 조건이 충족되어야 한다는 것이다. 1. 최적 부분 구조 - 전체 문제의 답을 부분 문제의 답을 이용하여 ..
우선순위 큐 우선순위 큐는 데이터를 추가한 순서대로 삭제하는 큐와 달리, 데이터 추가는 어떤 순서로 해도 상관 없지만 데이터를 제거할 때는 가장 작은 값을 제거하는 특성을 가지는 자료구조이다. 이는 내부적으로 정렬 메커니즘이 있다는 것을 의미한다. 우선순위 큐는 내부적으로 힙이라는 완전 이진 트리로 되어있다. 힙 트리의 루트노드에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데 전자는 최대힙(Max-heap) 후자는 최소힙 (Min-heap)이라고 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(logN)이다. 무작위 숫자들을 힙에 전부 넣고 하나를 빼면 정렬된 결과..
큐 Queue가 어떻게 쿠웨웨가 아니라 큐인지 모르겠지만... 큐는 스택의 특징과 다르게 선입선출(FIFO)의 성격을 가지고 있다. 따라서 큐는 순서대로 대기하고 실행시키고 싶을 때 사용하는 자료구조이다. 급식실에서 밥 먹으려고 줄 서있는 학생들을 생각하면 이해하기 쉬울 것 같다. 코드 큐 또한 파이썬에서는 리스트로 구현가능한데, pop을 해줄 때 앞의 값을 제거 해야하므로 pop(0)을 해주어야 한다. pop(0)의 시간복잡도는 O(n)이므로 O(1)보다는 효율적이지 못하다. O(1)인 방법으로 해결하기 위해 collections에서 deque를 import해주어 queue를 구현해볼 수 있다. 참고로 Queue 모듈에서 queue를 사용할 수 있지만, Queue 모듈은 멀티 스레딩 환경까지 고려해 스..
스택 스택은 컴퓨터에서 자주 쓰이는 자료구조 중 하나로, 후입선출(LIFO)의 특징을 가지고 있다. 나중에 들어온 것이 먼저 나간다는 뜻인데, 이는 쌓아둔 접시 혹은 프링글스를 생각하면 이해하기 쉬울 것이다. 이런 특징을 이용해서 뒤로 가기를 구현할 수도 있다. 코드 파이썬에서는 스택을 따로 구현해놓지 않았는데 리스트 자료형이 스택과 유사하게 동작하기 때문이다. push - append(x) -> 리스트의 가장 뒤에 새로운 값을 추가 pop - pop() -> 리스트 가장 뒤에 있는 값을 삭제 stack = [] #파이썬에선 이게 스택이다 import sys input = sys.stdin.readline a = int(input()) stack = [] for _ in range(a): x = inpu..
