note

투 포인터 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리 특정한 합을 가지는 부분 연속 수열 찾기 * 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문에 투 포인터 알고리즘으로 해결할 수 있다. * 리스트 내 원소에 음수 데이터가 포함되어 있는 경우, 투 포인터 알고리즘으로 해결할 수 없다. n = 5 # 데이터의 개수 m = 5 # 찾고자 하는 부분합 data = [1, 2, 3, 2, 5] # 전체 수열 count = 0 interval_sum = 0 end = 0 # start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_su..

다양한 그래프 알고리즘 - 그래프: 노드 + 간선 ㄴ '서로 다른 개체(혹은 객체)가 연결되어 있다' ㄴ 인접행렬(2차원 배열) - 메모리↑, 시간↓ / 인접리스트(리스트) - 메모리↓, 시간↑ - 그래프 vs 트리 그래프 트리 방향성 방향 그래프 / 무방향 그래프 방향 그래프 순환성 순환 / 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 X 부모-자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합 - 서로소 집합: 공통 원소가 없는 두 집합 - 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 ㄴ union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 ㄴ find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 # ..

가장 빠르게 도달하는 방법 - '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우' - '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' - 최단 경로 문제는 보통 그래프를 이용해 표현 ㄴ 각 지점은 그래프에서 '노드'로 표현되고, ㄴ 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작 - 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류 - 알고리즘 1) 출발 노드 설정 2) 최단 거리 테이블 초기화 3)..

중복되는 연산을 줄이자 - 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. - 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. # 피보나치 함수를 재귀 함수로 구현 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^N) - 피보나치 수열의 호출 과정을 그림을 그려..

순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 데이터 정렬 여부와 상관 없이 가장 앞에 있는 원소부터 하나씩 확인 - 시간 복잡도 O(N) ㄴ 데이터의 개수가 N개일 때 최대 N번의 비교 연산 # 순차 탐색 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_da..

정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 -> 매번 '가장 작은 것을 선택' - 시간복잡도 O(N^2) ㄴ 연산횟수: N + (N-1) + (N-2) + ··· 2 → N*(N+1)/2 → O(N^2) ㄴ 소스코드: 2중 반복문 사용 # 선택 정렬 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]: min_in..

스택 (LIFO) stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 - 별도의 라이브러리 없이 리스트의 append(), pop() 메서드 이용 큐 (FIFO) from collections import deque # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.pop..

구현 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' -> 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념 -> 프로그래밍 문법 숙지, 라이브러리 사용 경험을 늘려야 함. · 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 · 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 메모리 제약 사항 - C/C++에서 변수의 표현 범위 (int 4바이트, long 8바이트 -> 파이썬 X, 자바 BigInteger, C++ 외부 라이브러리 필요) - 파이썬에서 리스트 크기 (데이터의 개수 1000 -> 메모리 4KB / 백만 -> 4MB / 천만 -> 40MB) 채점 환경 - 파이썬은 C/C++에 비해 동작 속도 느림. 1초에 2,000만 번의 연산을 수행한다고 가정하..

그리디 알고리즘(탐욕법): 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다. ex) 거스름돈 문제 - 가장 큰 화폐 단위부터 돈을 거슬러 줌 ㄴ 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들을 종합해 다른 해가 나올 수 없다! n = int(input()) cnt = 0 coin = [500, 100, 50, 10] for i in coin:# 시간 복잡도 O(K)