이것저것 코딩하는 블로그

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 짧은 순서대로 탐색하는 것이 유리하다. 짧은 것이 다른 것의 접두사가 될 확률이 높기 때문이다. > 이렇게 생각했었는데 문자열대로 정렬하면 [12, 9, 123]일 때 [12, 123, 9]로 정렬된다. 자릿수별 아스키 코드로 정렬하기 때문이다. 이러면 i와 i+1만 비교하면 된다. 같은 숫자로 시작하는 것들끼리 몰리기 때문이다. 따라서 문자열 기준으로 정렬한 후, i번째 수가 i+1..

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 생각한 풀이: 32 3222 34 3444 라는 예제를 보고, 맨 뒤만 반복하여 4자리로 정렬 기준 수를 만들어준 뒤 (3222 3222 3444 3444) 이 숫자로 정렬하고, 만약 정렬 기준 수가 같을 때는 원래 수가 더 짧은 기준 정렬 수를 a, 긴 기준 정렬 수를 b라고 했을 때 a[0] > a[-1]이면 a를 앞에 두고, 아니면 b를 앞에 두었다. 이럴 경우 위와 같은 예제를..

1. Minimum Spanning Tree (MST) MST란, 트리가 주어져 있을 때 모든 노드들이 연결되어 있으면서 가중치의 합이 최소인 spanning tree (tree의 일부분, 부분집합 개념으로 생각하면 된다) 이다. 단, 이는 cycle을 포함해서는 안된다. Spanning tree의 정의 자체가 cycle을 포함하지 않는 것이기 때문이다. 이를 찾아주는 알고리즘이 크루스칼 알고리즘이다. 2. 크루스칼 알고리즘 이는 union-find를 이용하여 MST를 찾아준다. union-find에 대한 글은 다음 링크를 참고하자. https://codinglilly.tistory.com/32 [Algorithm] Union-Find 1. Union-Find란? 여러 개의 원소가 있고, 여러 개의 집합..

1. Union-Find란? 여러 개의 원소가 있고, 여러 개의 집합이 있다고 가정하자. 특정 원소가 어느 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할때 해당 알고리즘을 사용한다. 집합에 속하는 것을 한 원소를 대표로 하여 자식 노드로 이어줌으로써 집합을 구현한다. 1) Union 두 집합을 합치는 연산이다. 두 집합에 속하는 자식 노드들을 모두 찾은 후, 한 집합의 부모 노드를 다른 집합의 자식 노드로 하면 모든 원소가 하나의 부모 노드로 이어지게 된다. 코드로 표현하자면, 부분집합 x의 조상(루트)을 부모로 하고 y를 그 밑에 붙인다고 생각하면, uf(find[x]) = uf(find[y]) 가 된다. 2) Find 집합에 속한 원소를 찾는 연산이다. 부모 노드에 대해 연결된 자식 노드를 찾고..

1. 플로이드-워셜 알고리즘이란? 다익스트라 알고리즘은 특정 시작점이 있을 때만 사용할 수 있다. 따라서 모든 지점의 거리를 구하는 데는 번거로울 수 있다(모든 점들에 대해 다익스트라 알고리즘을 수행해야 한다). 이 때 사용하는 것이 플로이드-워셜 알고리즘이다. 기본 아이디어는 다익스트라와 유사하다. 단, 이를 모든 노드가 시작점일 때를 고려하여 수행할 뿐이다. A에서 B로 가는 경로보다 A에서 X를 거쳐 B로 가는 경로가 짧다면 최단 경로를 갱신하는 방식이다. 그러나 애초에 모든 점을 방문해야 하므로 다익스트라 알고리즘에 비해 느리다. 따라서 지점의 갯수가 적다면 다익스트라를 여러 번 돌리는 게 나을 수 있다. 코드를 보며 알아보자. 2. 구현 n = int(input()) graph = [] dist..

1. 다익스트라 알고리즘 다익스트라 알고리즘은 가중치가 있는 그래프에서, 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다. 이는 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리 라는 아이디어를 기반으로 한다. 과정을 살펴보면 다음과 같다. 1) 거리 배열을 최댓값으로 초기화하고, 출발지의 값만 0으로 설정한다. 2) 현재 방문하지 않은 정점 중 가장 거리 값이 작은 지점을 선택한다. 3) 해당 지점과 인접한 지점들의 거리를 갱신한다. 4) 모든 지점이 선택될 때 까지, 2와 3을 반복한다. 다음 그래프를 통해 살펴보자. 자세한 설명은 다음 링크를 참고하면 된다. 많은 도움을 받았다. https://www.codetree.ai/missions..