깊은 밤을 날아서

K번째 최단 거리 찾기 개요 다익스트라 알고리즘을 이용하여 K번째 최단 거리를 구합니다. 구현 방법 최단 경로 리스트를 2차원 리스트로 설정하여 내부를 K개의 최단 경로로 채웁니다. K번째 경로를 찾기 위해서 여러 번 노드가 쓰일 수도 있으므로 방문 리스트는 따로 적용하지 않습니다. 위의 내용을 기억하며 아래의 최단 거리 리스트 채우기 규칙을 따릅니다. 최단 경로 리스트 및 그래프 인접 리스트를 초기화합니다. 우선 순위 큐에서 연결된 노드와 가중치 데이터를 가져옵니다. 연결 노드의 K번째(마지막) 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 K번째 경로에 값을 업데이트합니다. 이때 경로가 업데이트되는 경우 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가합니다. 큐가 비워질때까지 ..

1. 다익스트라 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘 입니다. 특정 출발 노드에서 다른 노드로 가는 최단 거리를 모두 구하기 때문에 출발 노드가 고정되어 있을 때 사용 가능합니다. 추가적으로 에지들의 가중치 또한 항상 양수여야 합니다. 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수 O(ElogV) 구현 방법 간단하게 말하자면 BFS로 탐색을 진행하되, 다음 탐색 지점을 방문하지 않은 노드 들 중 가장 가까운 곳부터 선택하도록 하는 방법입니다. 위와 같이 항상 갈 수 있는 가장 최솟값인 경로만 택함으로써 결과적으로 각 노드는 출발 노드로부터 최단 경로만에 도달하게 됩니다.(간선의 가중치가 모두 양수가 아니라면 돌아올수록..

1. 유니온 파인드 개요 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘 union, find 연산을 완벽히 이해하는 것이 핵심 union 연산: 각 노드가 속한 집합을 1개로 합치는 연산. 노드 a, b가 a { A, b { B일 때 union(a,b)는 A U B를 말함. find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산. 노드 a가 a { A 일때 find(a)는 집합의 대표 노드를 반환 구현 방법 1차원 리스트 이용 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨. 1차원 리스트를 자신의 인덱스값으로 초기화. union 연산 각..

우선순위 큐 개요 우선순위를 가지는 queue. 정해진 우선순위가 높은 개체가 먼저 Get. 위 그림은 이해를 돕기위한 그림. 구현 방법 1. 일반적인 pq사용 from queue import PriorityQueue # 생성 방법 myque = PriorityQueue() # myqueue를 우선순위 큐로 생성 # 기본 함수 put(data) # 원소 추가 get() # 큐에서 데이터 꺼내기 qsize() # 큐 사이즈 가져오기 empty() # 큐가 비어 있는지 확인 put 연산의 경우 내부에 들어가는 튜플이나 리스트의 원소의 차례대로 우선순위를 가짐. 맨 앞에 있는 것으로 정렬 후 두번째 요소로 정렬 가능. EX) pq.put([2, 3]) pq. put([2, 1]) pq. get() -> [2,..

1. 큐(queue) 개요 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조 파이썬 구현 방법 collections에 deque 사용하여 간단하게 구현 가능 from collections import deque q = deque() 연산(이름이 q일 때) q.append(data): rear 부분에 새로운 데이터를 삽입하는 연산 q.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산 s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산 2. 너비 우선 탐색(BFS, breadth-first search) 개요 그래프 완전 탐색 방법 중 하나. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘. 시간 복잡도(노드 수: V..

1. 스택 삽입과 삭제가 LIFO(후입선출) 방식으로 이루어진 자료구조 구현 방법 0번 강의에서 언급했듯이 파이썬에선 리스트로 간단하게 스택 구현이 가능 리스트 이름이 s일때 s.appped(data): top 위치에 새로운 데이터를 삽입하는 연산 s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산 쓰이는 곳 DFS 쌍이 맞아야 하는 문제(괄호 여닫기 등) 2. DFS 그래프: 노드(정점)와 에지(간선)로 이루어진 자료구조 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 그래프 완전 탐색 알고리즘 시간 복잡도(노드 수: V, 에..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제에 대한 간단한 이해 수열이 주어졌을때 연속된 몇개의 수열 합의 최댓값을 구하는 문제입니다. 입출력에 대한 이해 수열과 수열의 길이, 몇개의 연속된 숫자일지가 주어집니다. 문제에 대한 세부 이해 1. 주어진 것(입력값) 2. 구하고자 하는 것(출력값) 둘 다 위와 같습니다. 3. 규칙 몇개의 수열이 연속될지에 따라 합을 구해야 하는 수열의 개수가 달라집니다. - 첫 번째 방법으로는..

처음으로 스터디원들과 함께하는 공통 문제를 풀어보았다~ 난이도는 가볍게 Lv 1! https://school.programmers.co.kr/learn/courses/30/lessons/135808 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제에 대한 간단한 이해 값어치가 다른 과일을 상자로 묶어 최저가로 판매하는 문제입니다. 입출력에 대한 이해 과일의 최댓값 k, 상자안의 사과 갯수 m, 그리고 사과값이 들어있는 리스트가 주어지고 이를 통해 최대 판매 가격을 도출합니다. 문제에 대한 세부 이해 1. 주어진 것(입력값) 과일의 최댓값 k, 상자안의 ..

그동안 시간이 없어서 블로그를 잠시 쉬었는데 다시 시작해보려 한다. (사람들이랑 하는 챌린지는 코드업 기초 100제 중 어려운 문제 풀면서 계속했는데 너무 많이 쉽더라... 백준 실버문제도 안 되는 느낌) 오늘 푼 문제는 함께 스터디하는 사람 중 한명이 먼저 푸신 수들의 합 2다. https://www.acmicpc.net/problem/2003 문제에 대한 간단한 이해 수열이 주어지고 그 수열 안에서 연속적으로 이어지는 부분 수열이 어떤 숫자를 만족하는 경우의 수 구하기입니다. 입출력에 대한 이해 수열의 길이, 만족해야할 숫자, 그리고 수열이 주어집니다. 문제에 대한 세부 이해 1. 주어진 것(입력값) 수열 2. 구하고자 하는 것(출력값) 경우의 수 3. 규칙 중요한 것은 항상 내부에서 이어져 있어야 ..

1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 문제에 대한 간단한 이해 - 후위 표기식 계산 문제입니다. 입출력에 대한 이해 - 후위 표기식이 들어오면 연산하여 값을 출력해줍니다. 문제에 대한 세부 이해 1. 주어진 것(입력값) 후위 표기식 2. 구하고자 하는 것(출력값) 연산 결과값 3. 규칙 - 후위 표기식은 피연산자들 + 연산자들 뭉텅이로 구성됩니다. - 한 뭉텅이에서 가장 먼저 연산되어야 할 연산자가 가장 앞에 옵니다. - 후위 표기식에 대한 예시를 보았을 때 계산이 피연산자가 나온 후 가..