🌱 → 🌳

탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색 동작 예시 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$ 에 비례함 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남음 2단계를 거치면 8개가량의 데이터만 남음 3단계를 거치면 4개가량의 데이터만 남음 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 $O(logN)$을 보장함 파이썬 이진 탐색 라이브러리 bis..

그래프 탐색 알고리즘: DFS/BFS 탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로 DFS/BFS가 존재 자료구조 스택(선입후출) 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 예시) 박스 쌓기 DFS method 정의 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] * 9 dfs(graph, 1, ..

예제 1) 1이 될 때 까지 while True: # (N==K로 나누어떨어지는 수)가 될 때까지 1씩 빼기 target = (n//k)*k count += (n-target) n = target if n

요구사항에 따라 적절한 알고리즘 설계하기 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 시간제한이 1초인 문제를 만났을 때, 일반적인 기준 N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계 N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계 N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계 N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계 알고리즘 문제 해결 과정 (일반적으로) 1. 지문 읽기 및 컴퓨팅적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 📌 문제 해설 "Xi>Xj를 만족하는 서로 다른 좌표의 개수와 같아야된다" 라는 뜻은 즉 Xi가 리스트 안에서의 크기 순서를 출력하면 된다는 말 (크기 순서는 0부터 시작.) 즉, 리스트안에서 자기보다 작은 숫자의 개수를 세는 것이므로, 자신이 리스트 안에서의 크기 순서를 출력하면 됨 📌 코드 실패 코드 (시간 초과) n = int(input())..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 정답 코드: def is_prime(n): if n == 1: return False for j in range(2, int(n**0.5)+1): if n % j == 0: return False return True t = int(input()) for i in range(t): num = int(input()) a,b = num//2, num//2 while a > 0: i..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 처음 코드: while(1): a=int(input()) if a ==0: break cnt=0 for i in range(a+1,2*a+1): if i == 1: continue for j in range(2,int(i**0.5)+1): if i % j == 0: break else: cnt+=1 print(cnt) 각 테스트 케이스마다 계속 소수를 계산하니까 시간 초과 발생 정답 코드:..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 처음 작성한 코드: a,b= map(int, input().split()) for i in range(a,b+1): cnt = 0 if i > 1: for j in range(2,i): if i % j == 0: cnt += 1 if cnt == 0: print(i) 답은 나오지만 시간 초과 발생 소수는 자신과 1밖에 약수가 없는 수이다. 그럼 모든 수를 돌면서 나누어 떨어지는 수가 있는지 없는지 보면 되는데 모든 수를 봐야할 ..