프로그래밍 (187) 썸네일형 리스트형 [백준] 1922. 네트워크 연결 - 파이썬 풀이. 최소 신장 트리 알고리즘인 크루스칼 알고리즘을 이용해서 풀면된다. 최소 비용을 구해야하는 문제이니 cost를 기준으로 graph를 정렬 시킨 후 크루스칼 알고리즘을 이용하면 어렵지 않게 풀 수 있다. 최소 신장 트리 알고리즘이 가물가물해서 한번 풀어봤다. 소스코드. " target="_blank" rel="noopener">https://gist.github.com/hanhyung6376/f6622fd34ba8c968bc12afce179c4d80.js"> [백준] 11724. 연결 요소의 개수 - 파이썬 풀이. 그래프의 연결 요소끼리 각 그래프의 위치에 추가하고 깊이 우선 탐색을 실시한다. visited배열을 이용하여서 현재 위치를 방문했는지 체크를 해주고 방문하지 않은 위치라면 dfs를 실시하고 +1을 한다. 소스코드. [백준] 17435. 합성함수와 쿼리 풀이. sparse table이라는 자료구조를 이용해야한다. sparse table은 정적 구간 질의를 처리할 수 있는 자료구조인데 대부분의 구간 질의를 O(log n)시간에 처리하지만 특정한 연산에 대해서는 O(1)의 시간 복잡도를 가지는 특징을 가지고 있다. sparse table로 구간 질의를 처리하기 위해서는 배열이 정적이어야한다. 해당 문제를 살펴보면 f2(1) = f(f(1)), f4(1) = f2(f2(1))과 같은 구조로 되어있다. 즉 sparse table에는 2의 제곱으로 늘어나는 값들을 저장해서 풀면된다. 아직 확실히 이해가 되지 않아서 다시 풀어보아야 할 것 같다. 소스코드. [백준] 18352. 특정 거리의 도시 찾기 - 파이썬 풀이. bfs를 이용해서 풀었다. 양방향 그래프이지만 최단거리를 구하는 문제이기때문에 왕복을 한다면 최단거리가 아니다. 따라서 bfs를 이용하여서 해당 도시를 방문했는지 확인을 하고 거리를 구한다. 소스코드. [백준] 16975. 수열과 쿼리 21 - 파이썬 풀이. 이진 트리를 이용해서 리프노드만을 이용해서 풀었다. 리프노드들을 제외한 노드들은 구간합을 구하는 문제가 아니라서 저장될 필요가 없다. 소스코드. [백준] 1238. 파티 - 파이썬 풀이. 다익스트라 알고리즘을 이용해서 출발점에서 도착점까지의 최단 경로 + 도착점에서 출발점까지의 최단 경로를 구해서 최댓값을 출력해주면 된다. 소스코드. [백준] 1517 버블 소트 - 파이썬 풀이. 세그먼트 트리로는 아직 풀지 못해서 병합정렬로 풀었다. 우선 문제의 버블 정렬은 두 요소 간 순서가 맞으면 가만히 놔두고 순서가 틀렸다면 숫자를 교환해야한다. 그리고 swqp의 횟수를 구해야한다. 병합 정렬을 이용하여 swap의 횟수를 구하였다. 소스코드. [프로그래머스] 숫자 문자열과 영단어 - 파이썬 숫자 문자열과 영단어 문제 설명 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요. 참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다. 숫자영단어 0 zero 1 one 2 two 3 three 4 four 5 fi.. 이전 1 2 3 4 ··· 24 다음
