이숭간 공부기록

최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한지점에서 다른 한지점 한 지점에서 다른 모든지점 모든 지점에서 다른 모든지점 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함 ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등 1. 다익스트라 알고리즘 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘) 동작과정 출발노드를 설정 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단..

다이나믹프로그래밍 : 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과의 재사용 --> 한번 계산해서 해결한 문제는 다시 계산하지 않도록 한다. 일반적으로 두가지 방식 ( 탑다운, 보텀업)으로 구성된다. 언제 DP로 문제를 풀 수 있는가?? 1. 최적 부분 구조 : 특정 번째까지의 최적의해는 앞의 최적의해를 이용해서 계산되는경우 ex) i번째까지의 최적의해는 i-1, i-2번째까지의 최적의해를 이용하는 경우 2. 중복되는 부분문제 점화식으로 표현되는 식은 재귀함수를 통해 구현할 수 있다. but 시간복잡도가 큼 메모이제이션을 사용하는 탑다운 방법은 구현시 재귀함수를 이용한다. 즉, 큰 문제를 해결하기위해서 작은문제들을 재귀적으로 호출하여 작은문제가 모두 해결되었을때 ..

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.) 단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N 내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 ) n,m = map(int, input().split()) input_list = list(map(int, input().split())) for i in range(max(input_list), 0, -1): count = 0 for j in input_list: count += max(0, j-i) if count >= m: print(i) break 내코드2 _ 이진탐색으로 다시..

정렬이란? 데이터를 특정한 기준에 따라 순서대로 나열하는것 일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨 선택정렬 : 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는것을 반복 시간복잡도 : O(n^2) 삽입정렬(Insertion Sort) : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 ( 위치를 매번 계산해서 데이터를 넣어줌 / 정렬범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘 시간복잡도 : O(n^2) 선택정렬에 비해 난이도가 높지만 더 효율적으로 작동함, 특히 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여 최선의 경우 O(N)의 시간복잡도를..

대표적 그래프탐색 알고리즘 : DFS / BFS 탐색이란, 많은 양의 데이터중 원하는 데이터를 찾는 과정 _ 파이썬에서는 간단히 리스트로 스택 구현 가능 DFS : 깊이우선 탐색으로 가장 깊은곳까지 먼저 탐색하는 방식 DFS는 스택자료구조(혹은 재귀함수)를 이용한다. 1. 시작노드를 스택에 삽입 / 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다. 너비우선탐색으로 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐를 이용한다. 1. 탐색 시작노..

출제경향 : 그리디 / 구현 / BFS, DFS 가 가장 많이 출제됨 파이썬 - 대체로 1초에 2천만번정도의 연산을 할수있다고 가정하고 접근 지수표현방식 : 1e9 = 10의 9제곱을 의미한다 / 임의의 큰 수를 표현하기위해 자주 사용됨 /ex) 최단경로 알고리즘에서 도달할수 없는 노드에 대해 최단거리를 무한으로 설정할때 list 직접 데이터를 넣어 초기화할수도 있고 크기가N이고 모든값이 0인 리스트 초기화 : a = [0]*n 인덱싱 슬라이싱 : 연속적인 위치를 갖는 원소들을 가져올때 - 끝인덱스는 +1 컴프리헨션 : 대괄호안에 조건문과 반복문을 적용해 리스트를 초기화 할수 있음 array = [i for i in range(10)] array = [i for i in range(10) if i%2 =..