전체 글

[python] 백준 - 1929. 소수 구하기

🤔문제 해결 S2 | 에라토스테네스의 체 소수: 1과 자기 자신 이외의 약수를 가지지 않는 1보다 큰 자연수 숫자 하나하나를 모두 for문을 돌려서 구할 수 있지만 비효율적임. 에라토스테네스의 체를 이용한다. 0부터 구하고자하는 값의 길이 만큼 0의 값을 가진 배열을 만든다. ex) dp = [0, 0, 0, 0, ..., 0] for문으로 2부터 배열의 끝까지 돌면서 자기 자신을 제외한 배수는 전부 1로 바꿔준다. 맨 위의 그림을 보면 이해하기 쉬움 배열에서 0인 녀석들을 print해준다. 💻소스 코드 def eratos(n): for j in range(n * 2, E + 1, n): dp[j] = 1 return S, E = map(int, input().split()) dp = [0] * (E +..

너비 우선 탐색(Breath First Search, BFS)

📔 너비 우선 탐색(BFS) 이란 너비를 우선으로 하여 탐색을 수행하는 알고리즘 최단경로(최단길이)를 찾을 때 주로 사용한다. 큐와 그래프로 해결한다. (파이썬에서는 데크(deque)를 쓰면 속도가 빠름) 📔 너비 우선 탐색(BFS) 구현 from collections import deque # 인접리스트 # 노드: 1,2,3,4,5,6,7 n = 7 adj = {x: [] for x in range(1, n + 1)} edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ] # 무방향 그래프이므로 반대쪽도 성립 for edge in edges: s, e = edge adj[s].append(e) adj[e].append(s) print(adj) # bfs..

계수 정렬(counting sort)

📔 계수 정렬(counting sort) 이란 작은 범위 조건이 있는 경우에 한해서 빠른 알고리즘 시간복잡도: O(N), 최악의 경우 O(N^2) 크기를 기준으로 갯수만 세주면 된다. 비교정렬 X 📔 계수 정렬(counting sort) 구현 N = 5 # 5 이하인 수들을 정렬해라 numbers = [1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 3, 3, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5] print(f'정렬 전: {numbers}') count_list = [0] * (N + 1) for number in numbers: count_li..

[python] 백준 - 1011. Fly me to the Alpha Centauri

🤔문제 해결 S1 | 수학 DFS로 구현해보려고 했으나 역시 시간초과로 실패했다. 알고리즘이 수학이다보니 역시 손으로 직접 패턴을 구해야 한다. 패턴을 보면 다음과 같다. 노란색으로 칠한 곳을 보면 뭔가 알 수 있다. . . . . 거리의 제곱근은 홀수 횟수가 끝나는 지점. 4: 2*2-1 = 3 9: 3*2-1 = 5 16: 4*2-1 = 7 25: 5*2-1 = 9 그렇다면 제곱근이 아닌 숫자는 어떻게 찾을까? 파란색을 보자. . . . . 거리의 제곱근만큼 다음 숫자가 있다. EX 예를 들어 거리가 7이다. 제곱근은: 2.xxxx 이므로 2이다. 2를 제곱하면 4 우리는 4부터 보면된다. 그렇다며 나머지는 거리 7에서 4를 빼면된다. 카운트는 2*2-1 이므로 3 제곱근은2, 시작은4, 나머지는3,..

병합 정렬(merge sort)

📔 병합 정렬(merge sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵정렬과 비슷 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 퀵정렬과 다른 점이 있다면 퀵정렬의 경우 pivot값에 따라 편향되게 분할 될 수 있는 가능성이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 가진다. 그러나 병합정렬의 경우 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다. 만약 8개의 숫자를 정렬한다고 하자. 8에서 4로 나누고, 4에서 2로 나누고, 2에서 1로 나눈다. 즉 3번 나눴다. 그러므로 나누는 것은 3 = log8 이므로 logn이다. 나..

[python] 프로그래머스 - 풍선 터트리기(월간 코드 챌린지 시즌1)

🤔문제 해결 Lv3 풍선이 살아남을 수 있는 조건: 내 풍선 기준 왼쪽 풍선 크기가 클 때 내 풍선 기준 오른쪽 풍선 크기가 클 때 만약 왼쪽과 오른쪽 둘다 크기가 작으면 풍선은 죽는다 이 문제에서 핵심은 풍선의 크기가 가장 작은 녀석들을 하나씩 뽑아주면 되는 것! 값을 기준으로 정렬을 해주면 크기가 가장 작은 풍선(5)은 무조건 살아남는다. - (모두 다 터트릴 수 있다) 크기가 두번째로 작은 풍선(6)도 무조건 살아남는다. - (자신보다 작은 풍선(5)을 터트릴 찬스가 1번 있기 때문) 크기가 세번째로 작은 풍선(7) 부터는 인덱스의 상황에 따라 결정된다. 만약 7이 앞의 두 풍선 사이에 있을 경우 자신의 양쪽이 모두 작기 때문에 풍선은 죽는다. 하지만 두 풍선 사이가 아니라면 ( 5 < 6 < 7 ..