최근 알고리즘을 풀다가 몰랐던 알고리즘 유형이 있어서 정리해보려고 한다!특정 구간이 중첩되는 횟수를 계산하는 문제였는데, 완탐으로 풀다가 시간초과가 발생했다 ㅠㅠ 이후로 찾아보다 누적합을 확장해서 풀 수 있다는 것을 알게 되었고, 정리해보려고 한다.  누적합 개념누적합이란 ?배열의 특정 구간의 합을 계산하기 위해, 배열 각 요소들을 누적 계산하고 저장한다.특정 구간의 합을 O(1) 시간 복잡도 안에 구할 수 있다.누적합의 구체적인 설명은 생략 // 누적합 활용해서 4~5 인덱스 합 구하기 예시 int[] arr = {1, 2, 3, 4, 5}; for(int i = 1; i  특정 구간 중첩 영역 구하기 (feat. imos)누적합을 활용하면 특정 구간에서 중첩되는 ..

최단경로 특정 지점까지 가장 빠르게 도다아는 방법을 찾는 알고리즘 최단 경로 문제는 보통 그래프를 이용해 표현한다. 최단 거리 알고리즘은 다익스트라 ,플로이드 워셜,벨만 포드 알고리즘 등이 있다. 이 중에서 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형이다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다. 다익스트라 최단 경로 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중..

다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다 피보나치 수열의 점화식은 다음과 같다 재귀함수를 이용해서 코드로 나타낼 수 있다 def fibo(x): if x == 1 or x ==2 : return 1 return fibo(x-1)+fibo(x-2) print(fibo(4)) 하지만 위와 같이 작성하면 f(n) 함수에 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 생길 수 있다. 시간복잡도는 O(2ⁿ) 정도로 소요된다. 위의 코드를 다시 생각해보면 동일한 함수가 반복적으로 호출된다. 이미 한번 계산했지만, 계속 호출할 때마다 계산을 다시 한다. fibo(6)을 구..

순차 탐색 가장 기본 탐색 방법으로 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 ⇒ 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다 , 다만 처음부터 순서대로 모두 탐색해야하기 때문에 시간복잡도는 O(N)이다 def sequential_search(n,target,array): for i in range(n): if array[i] == target: return i+1 input_data = input().split() n = int(input_data[0]) target = input_data[1] array = input().split() print(sequential_search(n,target,array)) # 입력 # 5 apple # b..

정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말함 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 숫자가 총 N개 있을 때 N-1번 반복하면 된다 연산 횟수는 N+(N-1)+(N-2)+ … +2 = (N² + N)/2 번이다. 따라서 시간 복잡도는 O(N²) 이므로 알고리즘 문제 풀이에 사용하기에는 느리다 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i # 앞에 있는 원소 인덱스 for j in range(i+1,len(array)): if array[min_index] > array[j]: # 현재 원소보다 크..

DFS와 BFS는 스택과 큐를 알아야만 한다. 스택 스택은 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조이다. 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 이용해 스택 자료구조와 동일하게 동작시킨다. append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고 pop() 메서드는 리스트의 가자 뒤쪽에서 데이터를 꺼낸다 stack = [] stack.append(5) stack.append(2) stack.append(1) stack.append(9) stack.pop() stack.append(4) stack.append(3) stack.pop() print(stack) # 최단 원소부터 출력 print(sta..

구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 코딩테스트에 자주 출제됨, 완전 탐색과 시뮬레이션 유형을 같이 공부함 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 방법을 말하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 말한다. 구현 시 고려해야 할 메모리 제약 사항 파이썬에서는 리스트 크기를 고려해야 한다. 대체로 코딩 테스트에서는 128~51MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. int 자료형 데이터의 개수에 따른 메모리 사용량 데이터의 개수 (리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 리스트 ..

Greedy 현재 상황에서 지금 당장 좋은 것만 고르는 방법 대부분의 문제가 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분하다. 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 잇따는 보장이 있을 때 매우 효과적이고 직관적이다. 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해본다. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 DP나 그래프 알고리즘 등 다른 알고리즘을 고려해본다. 예제 3-1 거스름돈 문제 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정함 손님에게 거슬러 줘야할 돈이 N원일 때 거슬..