쏭의 개발 블로그

[1] 최단경로 알고리즘이란? 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한 지점에서 다른 한 지점까지의 최단경로 한 지점에서 다른 모든 지점까지의 최단경로 모든 지점에서 다른 모든 지점까지의 최단 경로 표현 각 지점은 그래프에서 노드로 표현 지점간 연결된 도로는 그래프에서 간선으로 표현 [2-1] 다익스트라 최단경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작( 현실세계의 간선은 음의 간선X) 그리디 알고리즘으로 분류됨 매 상황에서(방문하지 않은 노드 중) 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 동작과정 출발 노드를 설정 최단 거리 테이블을 초기화 모든 노드까지 가기 위한 비용을 무한으로 설정 자기자신의 노드는 0 방..

1. 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 두가지 방법 top-down (하향식) bottom-up (상향식) 동적계획법이라고도 부름 동적? (자료구조) 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당 (다이나믹 프로그래밍) 별다른 의미 없이 사용된 단어 2. 다이나믹 프로그래밍의 조건 (1) 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결 가능 (2) 중복되는 부분 문제 (Overlapping Sub-problem) 동일한 작은 문제를 반복적으로 해결해야함 3. 다..

1. 이진탐색 알고리즘이란? 순차탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진탐색 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색범위를 정함 예시 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기 0 1 2 3 4 5 6 7 8 9 0 2 4 6 8 10 12 14 16 18 [1단계] 시작점 : 0 , 끝점 : 9 , 중간점 : 4 (소수점 이하 제거) 0 1 2 3 4 5 6 7 8 9 0 2 4 6 8 10 12 14 16 18 중간점에 위치한 값인 8과 찾고자하는 값 4를 비교 찾고자하는 값 4 < 중간점 값 8 ⇒ 중간점 이상의 값들을 볼 필요가 없음 [2단계] 시작점 : 0 ..

[1] 정렬 알고리즘 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 오름차순으로 가정 1. 선택정렬 처리되니 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 과정 7 - 5 - 9 - 0 - 3 - 1 - 6 - 2 - 4 - 8 [1단계] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 값 ‘7’과 바꿈 0 - 5 - 9 - 7 - 3 - 1 - 6 - 2 - 4 - 8 [2단계] 처리되지 않은 데이터중 가장 작은 ‘1’을 선택에 가장 앞의 값 ‘5’와 바꿈 0 - 1 - 9 - 7 - 3 - 5 - 6 - 2 - 4 - 8 [3단계] 처리 되지 않은 데이터 중 가장 작은 ‘2’를 선택해 갑장 앞의값 9와 바꿈 0 - 1 - 2 - 7..

탐색(Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 DFS, BFS → 코딩테스트에서 매우 자주 등장하는 유형(반드시 숙지!!!)⭐ DFS/BFS를 위해 반드시 알아야할 자료구조 ✏️ 스택 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 시각화 삽입, 삭제 2가지 연산으로 구성 파이썬 구현 리스트 자료구조 사용 stack=[] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop..

[1] 그리디 알고리즘(탐욕법) 현재상황에서 지금 당장 좋은 것만 고르는 방법 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력 반복적으로 선택해도 최적의 해인지 → 정당성이 중요 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨 거스름돈 문제 n=1260 count=0 array=[500,100,50,10] for coin in arry: count += n//coin n %=coin print(count) public class Main{ public static void main(String[] args){ int n=1260; int cnt=0; int[] coinTypes={500,100,50,10}; for(int i=0;i