본문 바로가기

개발/알고리즘

 (64)
[백준 / Python] 파티_1238 첫 번째 풀이 코드12345678910111213141516171819202122232425262728293031323334353637383940import sysfrom heapq import heappush, heappop n, m, x = map(int, input().split())data = [[] for _ in range(n + 1)]INF = int(1e9)for _ in range(m): a, b, c = map(int, sys.stdin.readline().split()) data[a].append((b, c)) def dijkstra(start, end): distance = [INF for _ in range(n+1)] distance[start] = 0 q = [] heappush..
[BOJ] 좋은수열_2661 이 문제는 내 힘으로 풀지 못하였다. 요 몇일 백트래킹 문제를 풀고 있는데, 내가 이 개념을 아는 줄 알았는데 잘 모르는 것 같다. 이 상태로 문제를 더 푸는건 의미가 없는 것 같다. 여기서 바로 잡고 가자. 재귀와 basecase를 어떻게 활용하는지 공부해보자. 재귀와 base case를 공부하여 밑에 정리하고 왔다. 조금은 보이지 않던 것들이 보이는 것 같다. 그래도 다시 흠칫하는 것은, data[-i:] == data[-i*2:-i]부분이다. 나라면 길이가 if cnt == n이 된다면 이때 판별할 것 같았다. 하지만 이렇게 되면 길이가 n이 될떄까지의 모든 경우의 수를 다 구해놓고, 나쁜 수열이 된다면 버려야 한다. 즉, 소모가 매우 크다. data[-i:] == data[-i*2:-i] -> 이..
[BOJ] 차이를 최대로_10819 이 문제는 가장 기본적인 순열 문제이다. 하지만 라이브러리를 쓰지 않고, 직접 구현하라고 하면 할 수 있을까? 하는 생각이 들었다. 구현 방법은 dfs 백트래킹을 사용하여 모든 경우의 수를 구해주면 되겠다 싶었지만, 막상 코드를 작성하려 하니 손이 움직이지 않았다. 그러니 dfs로 구현해보자. 재귀를 사용했다. - 재귀는 베이스 케이스를 잘 지정해야 한다. 여기선 개수가 m개일 때, 루프문을 나가는 것으로 하였다.
[BOJ] 행성 터널_2887 위 문제는 N개 노드의 간선이 될 수 있는 모든 경우의 수를 판단해 준 후, 크루스칼 알고리즘을 활용하려 했다. 하지만 N의 갯수가 최대 10만이기 떄문에 N(N-1)과 같은 방식으론 해결할 수 없다. 이를 해결한 풀이는 다음과 같다. x, y, z를 각각 나눠서 생각해본다. x=[]에는 x값을 정렬한 후, 거리를 계산한 값만 추가한다. y, z, 도 방금 한 x와 똑같이 수행한다. 그 후 data배열에 다 추가한다. 그럼 완벽히 최소 값부터 정렬된 것은 아니겠지만, 그래도 x, y, z의 각각 자신이 갖고 있는 최소값을 추가해주는 상황이다.
[알고리즘] 크루스칼 이전 포스팅에서 union-find알고리즘을 살펴보았다. union-find알고리즘은 무방향 그래프 내에서의 사이클을 판별할 때도 사용할 수 있는 특징이 있다. 신장트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부른 것이다. 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾는 것을 최소 신장 트리 알고리즘이라고 한다. 최소 신장 트리 알고리즘 중 하나로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데, 이 알고리즘은 그리디 알고리즘으로 분류된다. 크루스칼 알고리즘의 구현 방법 먼저 모든 간선에 대해..
[알고리즘] 유니온 파인드(Union-Find) 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로 상호 배타적 지비합, Disjoint-set이라고도 한다. 여러 노드 중 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지를 확인하는 알고리즘이다. 서로소 집합 자료구조의 연산 알고리즘은 다음과 같다. 1. union(합집합): 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드를 찾는다. - A와 B의 루트 노드 중 Union-Find알고리즘 서로소 집합 알고리즘이라고도 불린다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 이 자료구조는 union과 find 2개의 연산으로..
[알고리즘] 다익스트라 알고리즘 문제를 풀다 보면, 노드와 간선이 주어지고 가장 짧은 길 찾기 등과 같은 문제들을 자주 볼 수 있다. 이러한 문제를 해결하기 위한 알고리즘이 바로 최단 경로이다. 최단 경로를 구하는 방식은 다익스트라, 벨만 포드, 플로이드 와샬, SPFA로 크게 4가지 정도가 있다. 이전에 플로이드 와샬에 대해 정리한 적이 있으니, 오늘은 다익스트라에 대해 정리해보자. 다익스트라 알고리즘이란? 여러 개의 노드와 간선이 있을 때, 특정한 지점에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라는 기본적으로 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 떄문에 그리디 알고리즘으로도 분리된다. 이 설명은 뒤에 더 보겠다. 다익스트라 알고리즘 원리 다익스트라 알고리즘은 ..
[알고리즘] 플로이드-워셜 플로이드 워셜이란? 그래프 상에 각각의 노드에서 출발하여, 특정 노드까지의 최단거리를 모두 구해주는 알고리즘이다. + 다익스트라는 한 지점에서 모든 지점까지의 최단거리를 구해주지만, 플로이드 워셜은 모든 지점에서 모든 지점까지의 최단거리를 구할 수 있다. 특징 세개의 중첩 반복문을 사용하고, O(v^3)의 시간 복잡도를 가진다. 구하는 방법과 원리 보통 이 알고리즘을 사용하는 문제는, 한 지점에서 다른 지점까지의 거리를 모두 알려준다. 주어진 정보를 활용하여 최단거리를 구해야 하는데, 이때 a지점에서 b지점까지의 거리와, a지점에서k + b지점에서k까지의 거리를 비교하여 더 적은 값을 최단거리로 잡는다. 이 부분에 대한 코드만 보면 이렇다. for k in range(1, n+1): for a in ra..

티스토리툴바