개발새발

다익스트라 알고리즘은 그래프 이론에서 주어진 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. (그래프 이론 + dp)다익스트라 알고리즘 개요다익스트라 알고리즘은 다음과 같은 단계로 동작합니다:출발 노드 선택: 시작 노드를 선택하고, 시작 노드의 최단 경로를 0으로 초기화합니다.우선순위 큐 활용: 출발 노드부터 갈 수 있는 모든 경로를 우선순위 큐(힙)에 넣습니다. 시작 노드의 최단 경로가 0이므로 시작 노드를 우선순위 큐에 넣습니다.최단 경로 갱신: 우선순위 큐에서 최소 비용의 노드를 꺼내서 해당 노드에서 갈 수 있는 모든 노드들의 최단 경로를 갱신합니다. 이 때, 기존 경로보다 더 짧은 경로를 발견하면 해당 ..

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 배열이나 부분 집합을 찾기 위해 두 개의 포인터를 사용하는 기법입니다. 이 기법은 주로 배열을 효율적으로 탐색하면서 O(N^2) 이상의 시간 복잡도를 O(N)으로 줄일 때 사용됩니다.투 포인터 기법의 기본 원리포인터 초기화:배열의 시작 위치에 두 개의 포인터를 설정합니다. 일반적으로 하나는 start 포인터, 다른 하나는 end 포인터입니다.포인터 이동:조건을 만족할 때까지 두 포인터를 이동시킵니다.각 포인터의 이동은 문제의 조건에 따라 다릅니다. 예를 들어, 부분합이 일정 값을 넘는 경우 start 포인터를 이동시키고, 그렇지 않으면 end 포인터를 이동시킵니다.조건 만족 확인:두 포인터가 가리키는 구간이나 값..

1. sort() vs sorted()list = [2, 3, 1]list.sort()print(list) #[1,2,3]list2 = [2, 3, 1]b = sorted(list)print(b) #[1, 2, 3]리스트.sort() :: 원본의 값 직접 수정 VS sorted(리스트) :: 새로운 리스트 값 반환역순 정렬을 위해서는 sort(reverse=True) / sorted(reverese=True)튜플 정렬첫번째 원소 오름차순 a.sort(key=lambda x:x[0])첫번째 원소 내림차순 a.sort(key=lambda x:-x[0]) or a.sort(key=lambda x:x[0], reverse=true)두번째 원소 오름차순 a.sort(key=lambda x:x[1])두번째 원소..

알고리즘 문제를 풀다보면 가끔 순열, 조합을 구현해야한다.. 코테에서도 가끔 등장하는데 문제 볼때마다 까먹어서 다시 공부를 해야한다,, 내가 보고 공부하려고 기록하는 파이썬으로 순열과 조합 구현하는 코드! itertools를 사용하지 못할 수도 있어 직접 구현하는 방식만 공부했다 순열(n개 중에 r개를 선택해서 만들수 있는 모든 경우의 수) 조합(n개 중에 순서 상관없이 r개를 뽑는 모든 경우의 수) 1. 재귀함수를 이용한 조합 def comb(arr, n): result = [] if n > len(arr): return result if n == 1: for i in arr: result.append([i]) elif n > 1: for i in range(len(arr) - n + 1): for j..

내가 계속 까먹어서 기록해 놓는 파이썬 소숫점 표현방법!알고리즘 문제를 풀다보면 대부분 반올림을 써야하는데 익히 알고 있는 round를 쉽게 쓴다.하지만 round에는 큰 허점이 있어서 다른 방법을 사용해야 하는데 아직은 사용할 때마다 긴가민가 하다... 1. 반올림, 올림, 내림일반적인 반올림에는 round를 사용한다.올림과 내림의 경우 ceil(올림), floor(내림)을 사용한다.round(1.234, 2) # 반올림, 소숫점 2번째 자리까지 표시(1.23)import mathmath.ceil # 올림math.floor # 내림 2. round 함수의 문제점하지만 round 함수의 경우 자릿수를 표시해주는 '0'에 대해서는 문제가 발생한다.print(round(1.000, 2)) # 1.00이..