Python

[python] 백준 - 1931. 회의실 배정

🤔문제 해결 S2 | 정렬, 그리디 회의 시간이 긴 것과 상관 없이 회의가 끝나는 시각이 빠른것을 선택 회의가 끝나는 시각이 빠른 순으로 정렬 이전 회의가 끝난 시각과 비교하여 회의를 시작할 수 있으면 카운트 +1 없으면 통과 💨 끝나는 시각 뿐만 아니라 시작 시간도 두번 째로 정렬 해줘야 한다. 반례 [2,2], [1,2] 💨 sys.stdin.readline 과 input의 차이 (아래가 input()으로 받은 것) 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(key=lambda x: (x[1], x..

깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란 깊이를 우선으로 하여 탐색을 수행하는 알고리즘 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법! ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것! 경로를 찾고 싶을 떄 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 ) 스택으로 사용시 이웃 중 가장 뒤에 있는 것부터, 재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다. 📔 깊이 우선 탐색(DFS) 구현 def dfs(c): print(c, end=' ') for neighbor in adj[c]: # c의 이웃 중 if visited[neighbor] == 0: # 방문 아직 안한 친구이면 visited[neig..

[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,..