큐(Queue) 란? 선입선출(FIFO, First In First Out) 형식을 갖는 자료구조 → 먼저 들어간 입력이 먼저 나옴 종류 선형 큐(Linear Queue) 일반적인 리스트 형태를 갖으며, 선입선출 형식을 갖음 원형 큐(Circular Queue) 처음과 끝이 있는 것이 아닌, 회전하며 인덱싱 삽입, 출력에 있어 메모리 효율을 높일 수 있음 우선순위 큐(Priority Queue) 먼저 입력한 순서가 아닌, 우선순위를 두고 우선순위가 높은 순서로 출력 구현 리스트 생성 list의 append를 활용하여 구현 queue = [] index를 이용한 구현 front = 0 rear = -1 queue = [0 for _ in range(N)] 삽입(EnQueue) list의 append를 활용..

문제 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. 0번부터 V번까지의 노드와 E개의 간선을 가진 그래프 정보가 주어질 때, 이 그래프로부터 최소신장트리를 구성하는 간선의 가중치를 모두 더해 출력하는 프로그램을 만드시오. [입력] 첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 노드번호 V와 간선의 개수 E가 주어진다. 다음 줄부터 E개의 줄에 걸쳐 간선의 양 끝 노드 n1, n2, 가중치 w가 차례로 주어진다. 1

문자열을 빨리 찾을 순 없을까? 개념 문자열은 문자들을 이어붙여 만든 개념으로 이를 빠르게 탐색하고 싶을 때 문자열들을 문자 하나를 기준으로 앞에는 어떤 문자가 오는지, 뒤에는 어떤 문자가 오는지를 체크 해놓으면 여러 문자열을 저장할 때 더 적은 비용을 들여 탐색할 수 있다. 말은 쉽지.. 트라이(Trie) 알고리즘 문자열 집합을 표현하는 트리 자료구조 문자열을 탐색하는데 있어 시간을 줄이기 위한 알고리즘(문자열 탐색 알고리즘) 장점 빠른 탐색 시간( O(M *L) → O(M) ※M: 문자열의 수, L: 가장 긴 문자열 길이) 단점 정렬이 되어 있어야 함 비효율적인 메모리 기존 : 문자열 길이(개행포함) * 문자열의 총 개수 트라이 형식 : 문자열 * (다음 노드의 수 + 끝인 경우의 문자열) * 문자열..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이해 완전 탐색을 통해 구현할 수 있지만, 이동에 있어 비용이 다르기 때문에 우선순위 큐를 활용한 다익스트라가 더 유리 비교를 위해 두 방식 모두 풀이했습니다. 구현 BFS 방문했을 때 최소값을 알기 위한 visited 배열 선언(초기화 값은 최댓값인 100,001) N부터 너비우선 탐색을 통해 탐색 방문 시 이전 방식보다 가중치가 작다면 최솟값을 변경하면서 ..

https://www.acmicpc.net/problem/12851 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 완전 탐색을 하면서 최소가 되는 시점에만 값을 변경, 이후 같은 값이 나오면 카운트 ++ 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 # 46944KB380ms # 12851 숨바꼭질 2 import sys from collections import deque input = sys.stdin.readline def solution(): N, K = map(int, input().split()) que = deque([(0, ..

https://www.acmicpc.net/problem/1697 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 다익스트라를 통해 해결도 가능할 것 같아 풀어봄 방문 확인용 배열에 최솟값을 저장해 가지치기를 할 수 있음 N == K 인 경우, 조건문을 통해 배열에 넣고, 빼는 시간을 줄임 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 너비우선탐색 # 35388KB140ms import sys from collections import deque N, K = map(int, sys.stdin.readline().strip().split())..