zhelddustmq 님의 블로그

다익스트라 알고리즘: 다익스트라(데이크스트라)가 만든 알고리즘.  https://ko.wikipedia.org/wiki/에츠허르_데이크스트라  1. 출발지를 s로 정하고, 다음과 같이 표시한다. (s, t, x, y, z 순)거리 = [0, inf, inf, inf, inf]방문 = [True, False, False, False, False]2. 갈 수 있는 노드들의 최소거리를 측정한다.s->t: 10s->y: 5 (s, t, x, y, z 순)거리 = [0, 10, inf, 5, inf]방문 = [True, False, False, False, False]3. 방문 안한 녀석들 중 가장 가..

1. 모듈러 산술 연산 : 나머지 연산을 하는 것. 컴퓨터 언어에서 사용하는 %연산으로 표현하면 아래와 같다.r = a % m (r: 나머지, a: 피제수, m: 제수)r = a mod m# a를 m으로 나눈 나머지 r  2. 합동(Congruent) : mod 연산은 합동 관계를 바탕으로 두 수의 관계를 정의정수 a, b, m에 대해 m | (a-b)라고 하면, a와 b는 모듈러(modulus) m에 대해 합동이라 하고,a ≡ b (mod m)과 같은 수식으로 표현-> m | (a - b)에서 | 의 의미는 (a - b)는 m으로 나누어 떨어진다는 의미. 나누어 떨어지지 않는 경우는 ł-> a - b가 m이라는 정수로 나누어 떨어진다면, a ≡ b (mod m)과 같이 표현-> 이는 다르게 말하면, a..

1. N-Queen 문제란? (link) N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 센다.퀸은 상하좌우, 대각선 방향으로 거리 제한 없이 이동할 수 있다.N=8인 경우, 경우의 수는 다음과 같다.64 * 63 * ... * 57 = 178,462,987,637,760C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간이 소요된다. 2. 백 트래킹필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법을 백트래킹이라고 한다.       파이썬 코드:def nqueen(n): """ visited 의 인덱스는 행, 값은 열을 나타낸다. (1, 3)에 놓은 경우, visited[1] = 3 으로 표현하겠다는 것. 예시) n=4 이..

문제 설명n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.제한사항주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니..

1. 에라토스테네스의 체: 2부터 배수들을 지워나가며 지워지지 않은 제일 처음 수가 소수가 되고, 또 그 소수의 배수를 지워나가며 소수를 찾는 방법 2. 1부터 N까지 소수가 몇개인지 판별하는 방법 2-1 약수가 있는지 확인해서 끝까지 조사해서 없으면 소수( 시간 복잡도: O(N^2) ) 2-2 √N까지만 조사해서 없으면 소수( 시간 복잡도: O(NlogN) )  2-3 에라토스테네스의 체 이용( 시간 복잡도: O(Nlog(logN)) ) 3. 에라토스테네스를 활용해, 소수 구분하는 동작 순서 1) 2부터 N까지 모든 정수를 적음2) 아직 지우지 않은 소수 중 가장 작은 소수를 찾음(이 수를 P라고 함)3) 아직 지우지 않은 수들 중, P의 배수를 크기 순서대로 지움4) 아직 모든 수를 지우지 않았다면 ..

0. 파이썬은 python 3.5부터 gcd를 python 3.9부터 lcm을 math라이브러리에서 제공 1. 약수: 나누어 떨어지는 수 1-1 N의 약수 구하는 법:1부터 N이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾음( 시간 복잡도: O(N) )1부터 √n이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾고, 그 개수에 2를 곱함. N이 제곱수면, √N이 중복되므로 하나 뺌( 시간 복잡도: O(√N) )2. 유클리드 호제법:  A = Bq + R이라 할 때, A, B의 최대공약수 G(A, B)와 B, R의 최대공약수 G(B, R)이 같다. 두 수 A, B가 있고, 그 두 수의 최대공약수가 G라고 하자. (A > B)(단 a, b 는 서로소)A는 아래처럼 나타낼 수도 있다.(q는 몫,..

1. 버블 정렬(이전 글)2. 선택 정렬 (이전 글) 3. 삽입 정렬 (이전 글) 4. 퀵 정렬 (이전 글) 5. 합병 정렬6. 힙 정렬  5. 합병 정렬(Merge Sort): 데이터를 낱개로 쪼갠 후 merge 함수를 이용해 병합하는 방식 5-1 merge함수: 두 정렬된 파일을 하나의 파일로 합쳐 빈 파일에 저장하는 함수A= [1, 2, 3, 5] # 정렬된 배열 AB= [4, 6, 7, 8] # 정렬된 배열 BC= [] # 두 집합을 합칠 빈 배열 C ↓1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1 4 이므로 4을 C 에 넣습니다. C:[1, 2, 3, 4] ..

1. 버블 정렬2. 선택 정렬3. 삽입 정렬4. 퀵 정렬5. 합병 정렬(다음 글)6. 힙 정(다음 글)  0. 정렬을 배우는 이유: 데이터 형태에 따른 시간 복잡도를 줄이기 위함.0-1 시간복잡도:버블 정렬, 선택 정렬, 삽입 정렬: O(n^2)퀵 정렬: 최악->O(n^2) / 평균-> O(nlogn)합병 정렬, 힙 정렬: 최악, 평균 -> O(nlogn)1. 버블 정렬(Bubble Sort): 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식. 작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하는 방식 (다음 루프때는 (마지막-1)번째 자료..

1. 미로 탈출 경로 찾기문제 설명:N x M 크기의 미로가 주어집니다. 미로는 0과 1로 구성되어 있으며, 0은 이동할 수 없는 벽을 나타내고, 1은 이동할 수 있는 경로를 나타냅니다.시작 위치는 (0, 0)이며, 미로의 출구는 (N-1, M-1)에 위치해 있습니다.최단 경로로 미로를 탈출하는 방법을 찾는 프로그램을 작성하세요. 이동은 상하좌우로만 가능합니다. 요구사항:BFS 알고리즘을 사용하여 미로의 모든 경로를 탐색합니다.시작 위치에서 출구까지의 최단 경로의 길이를 찾아야 합니다.최단 경로의 길이를 반환합니다. 예시 입력:11101101011010111111예시 출력:8시작 위치 (0, 0)에서 출구 (3, 4)까지의 최단 경로의 길이는 8입니다. 예시 입력:1111100001111011000111..

1. 그래프(이전 글)2. DFS(이전 글)3. BFS4. 백트래킹5. 이진탐색 3. BFS: 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 순서대로 넣은 노드를 꺼내서 탐색.큐가 BFS를 구현하는 것에 용이함1. 루트 노드를 큐에 넣는다.2. 현재 큐의 노드를 빼서 visited 에 추가한다.3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.4. 2부터 반복한다.5. 큐가 비면 탐색을 종료한다. 3-1. BFS 구현from collections import dequedef bfs_queue(graph, start): visited = [start] q = deque([start]) while q: node = q.popleft() ..