🌱 → 🌳

다이나믹 프로그래밍( 동적 계획법) 다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 탑 다운(하향식) 보텀 업(상향식) 일반적으로 프로그래밍 분야에서 동적(dynamic)이란? 자료구조에서 동적 할당(dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미 반면 다이나믹 프로그래밍에서 ‘다이나믹’은 별 의미 없이 사용된 단어 다이나밍 프로그래밍의 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서..

탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색 동작 예시 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 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/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 정답코드: from collections import Counter import sys a = int(sys.stdin.readline()) b= [] for i in range(a): b.append(int(sys.stdin.readline())) b.sort() c = a//2 # 산술평균 print(round(sum(b)/a)) # 중앙값 print(b[c]) # 최빈값 cnt = Counter(b).mo..

처음 작성한 코드 import sys n = int(input()) m = [] for i in range(n): m.append(int(sys.stdin.readline())) m.sort() for i in m: print(i) → 메모리 초과 발생 시간복잡도를 줄이기 위해 sys를 쓰는 건 알겠지만 메모리 초과,, 공간복잡도를 줄이기 위해서는 어떻게 해야하는 지 몰라서 인터넷을 찾아봤다. 정답 코드 import sys n = int(sys.stdin.readline()) m = [0] * 10001 for i in range(n): m[int(sys.stdin.readline())] += 1 for i in range(10001): if m[i] != 0: for j in range(m[i]): p..