본문 바로가기

알고리즘

버블정렬, 선택정렬, 삽입정렬, 힙정렬, 퀵정렬, 병합정렬 버블 정렬 햔 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복 시간 복잡도 O(n2), 공간 복잡도 O(n) def insert_sort(x): for i in range(1, len(x)): j = i - 1 key = x[i] while x[j] > key and j >= 0: x[j+1] = x[j] j = j - 1 x[j+1] = key return x선택 정렬 수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업 반복 시간 복잡도 O(n2), 공간 복잡도 O(n) def selectionSort(x): length = len(x) for i in range(length-1): indexMin = i for j in range(i+1, length): if x[ind..
[최단경로]플로이드 와샬, 다익스트라, 최소 신장트리(프림, 크루스칼) 그래프, 경로, 최단경로 그래프 : 정점과 간선으로 이루어진 자료구조 경로 : 간선들을 순서대로 나열한 것 최단경로 : 시작 정점부터 목표 정점까지의 가중치의 합이 최소가 되는 경로 다익스트라 알고리즘 양의 가중치를 가진 최단 경로 탐색에서 사용하는 알고리즘 각 지점에서 최단 경로를 찾아가는 그리디한 방법이자 최단 경로의 부분경로 역시 최단 경로인 DP 기반의 알고리즘 음의 가중치가 있는 경우 그리디한 접근으로 무한루프에 빠질 가능성이 있어 이때는 플로이드 와샬 사용 한 정점에서 모든 정점으로의 최단 경로를 구할 때 예시, 프로그래머스 배달 문제 import heapq from collections import defaultdict def di(dic, start, N, K) : cnt = 0 dista..
[알고리즘] DFS와 BFS DFS(Depth-First Search, 깊이 우선 탐색) 그래프 탐색 임의의 노드에서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 구현이 너비 우선 탐색(BFS) 보다 간단함, 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느림 전위 순회 등 트리 순회는 모두 DFS의 한 종류 해가 없는 경우에 빠질 가능성이 있음 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다(check, visited 등) 1)스택을 사용 2)재귀사용 예시 프로그래머스 여행 경로 링크 BFS(Breadth-First Search, 너비 우선 탐색) 그래프 탐색 두 노드 사이의 최단 경로 혹은 임의의..
[월간 코드 챌린지 시즌2]모두 0으로 만들기, 파이썬 문제 프로그래머스 모두 0으로 만들기 문제 링크 풀이 월간 코드 챌린지 시즌2 1, 2 번은 매우 쉬웠는데 3번에서 런타임에러가 나와서 4번은 풀지도 못했다. 3번이 레벨 3이기 때문에 3번까지는 무난히 풀 수 있어야 한다. 어쨌든 3번은 트리가 주어졌을 때 리프노드부터 탐색할 수 있는지 묻는 문제이다. 주어진 트리의 모든 노드 가중치 합이 0이 아니면 -1을 리턴한다, 0이라면 무조건 답을 구할 수 있다. 트리는 어떤 노드도 루트노드가 될 수 있기 때문에 시작점을 아무거나 잡아도 상관 없지만 길이가 2이상이라 편의상 0을 루트노드로 잡았다. 풀이 1의 경우 재귀를 사용했는데 파이썬은 기본 재귀 횟수를 1000으로 제한한다고 한다. 따라서 a의 최대 길이인 300,000으로 재귀 횟수 제한을 늘려주어야 ..
[프로그래머스] 월간 코드 챌린지 - 스타 수열, 파이썬 문제 프로그래머스 스타수열 링크 풀이 난이도 : 레벨 3 월간 코드챌린지가 뭔지는 모르겠으나 기업 코딩테스트용-스타일 문제는 아니다. 주어지는 배열 a의 최대 길이가 500,000 이기 때문에 O(N^2)으로는 시간초과가 나온다. 부분수열은 순서를 바꿀 수 없기 때문에 순서대로 a 배열을 순환하며 조건에 맞게 딕셔너리에 값을 넣어준 후 나중에 비교하였다. [0, 1, 0, 1]과 같은 순서는 문제 없으나 [0, 1, 1, 0], [1, 1, 0, 1]과 같은 자료는 문제가 될 수 있다. 따라서 위 케이스 등을 고려해서 문제에서 요구한 답을 O(N)으로 구할 수 있도록 코드를 짰다. 코드 from collections import defaultdict def solution(a): N = len(a) if..
2020 카카오 인턴십 - 보석 쇼핑, 파이썬 문제 프로그래머스 카카오 코딩 테스트 문제 링크 풀이 난이도 : 레벨 3 gems 배열 크기는 최대 100,000 이기 때문에 O(N^2)으로 풀면 시간 초과가 난다. 따라서 start, end 두개의 포인터를 조작하는 투포인터 알고리즘을 활용 보석의 종류별로 최소 1개 이상의 수량이 있을 때까지 right를 1씩 더해줌 최소 1개 이상의 수량이 확보되었으면 left를 1씩 움직여가며 중복된 보석을 제거해줌 gems 배열 끝까지 위 단계를 반복해 cand 배열에 넣은 후 구간 길이가 짧고, 같다면 left 크기가 작은 원소를 리턴한다. 코드 from collections import defaultdict def solution(gems): cand = [] left = right = 0 N, gem_nu..
[프로그래머스] 스티커 모으기(2)- 파이썬 문제 프로그래머스 Summer/Winter Coding(~2018) 문제 링크 풀이 난이도 : level 3 예전 문제들은 이렇게 딱 기본 문제로 나온 것 같은데 요즘 추세는 장황한 문제가 나오는 편이다. DP로 풀었다. leet code에서도 비슷한 문제를 좀 더 깔끔하게 푼 풀이를 본 것 같은데 아래 코드는 그다지 깔끔하지는 않다. 원형이기 때문에 첫 번째를 포함하면 마지막 스티커를 포함할 수 없어 케이스를 나누어 계산하였다. dp_y는 포함케이스, dp_n는 불포함 케이스로 계산하여 풀어주었다. dp[idx]는 각 idx 까지의 최대값이다. idx 위치에서 스티커를 포함한다면 그 전단계를 포함하지 못하므로 idx -2 위치의 최대값을 포함, 그렇지 않다면 최대값은 idx -1 위치의 최대값이다. 마..
[프로그래머스]2020 카카오 인턴십- 경주로 건설, 파이썬 문제 ㅍ로그래머스 경주로 건설 문제 링크 풀이 경로문제, 벽이 있는 문제이므로 아래, 위, 오른쪽, 위 4가지 방향으로 모두 움직이는 케이스를 고려해야 한다. 비용은 상하 에서 좌우로 변할 때 600원 상하, 좌우끼리는 100원 소요되므로 상하는 -1, 좌우는 1 값을 넣어 계산해줬다. 다음에 위치할 수 있는 위치(상하좌우로 이동, 0~N 사이의 위치, 벽이 아닌 경우)를 계산한다. check 배열을 만들어 초기값으로 무한을 주고 check 배열에 들어있는 값보다 같거나 작을 경우 큐에 추가해준다. check 배열을 만들지 않으면 무한루프에 빠짐 x == N-1 and y == N-1 마지막에 도달하면 지금까지의 비용을 cand 배열에 넣고 최소값을 리턴한다. 뭔가 좀 지저분하게 푼 것 같은데 나중에 다..

티스토리툴바