Programming

순차 탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 가장 기본 탐색 방법 구현이 간단 count() 메소드 등에도 내부에서 순차 탐색 수행 데이터 개수가 N개일 때 최대 N번의 비교 연산 → 최악의 경우 시간 복잡도 O(N) 코드 구현 # 순차 탐색 소스코드 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) 이진 탐색(Binary Search) 찾으려는 데이터..

문제 해설 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체 단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체 수행 두 배열의 원소가 최대 100,000개까지 입력 → O(NlogN) 보장하는 정렬 알고리즘 이용 풀이 # 변수 : N 두 배열의 원소 개수, K 바꿔치기 연산 횟수 n, k = map(int, input().split()) # N과 K를 입력받기 a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기 b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기 a.sort() # 배열 A는 오름차순 정렬 수행 b.sort(reverse=True)..

문제 해설 학생 정보가 100,000(10만)개 입력 최악의 경우 → O(NlogN)을 보장하는 알고리즘 이용 이름, 점수를 입력받아 점수 기준으로 정렬하고 이름 출력 → 파이썬 튜플 & 기본 정렬 라이브러리 사용 * 튜플 자료형 대입 연산자(=)를 사용하여 값을 변경할 수 없다. 그래프 알고리즘을 구현할 때 자주 사용된다. ex) 다익스트라 최단 경로 알고리즘 흔히 서로 다른 성질의 데이터를 (비용, 노드 번호)의 형태로 함께 튜플로 묶어서 관리하는 것이 관례 * 람다(lambda) 함수 익명함수, 바로 정의하여 사용할 수 있는 함수 형식 : lambda 인자: 표현식 ex) sum = lambda x: x+1 인자 넣기 : 람다 표현식을 괄호로 묶은 후, 다시 괄호를 붙이고 함수를 붙이고 인수를 넣어..

문제 해설 가장 기본적인 정렬 문제. 파이썬 기본 정렬 라이브러리를 이용하는 것이 효과적 풀이 # 변수 : N 정수의 개수 # N을 입력받기 n = int(input()) # 변수 : array 정수를 저장할 리스트 # N개의 정수를 입력받아 리스트에 저장 array = [] for i in range(n): array.append(int(input()) # 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행 array = sorted(array, reverse=True) # 정렬이 수행된 결과를 출력 for i in array: print(i, end=' ') 해석 변수 : N 정수의 개수, array 정수 저장할 리스트 1. 정수의 개수(N) 입력받기 2. 정수 저장 리스드(array) 선언하여 N개의..

정렬 알고리즘 개요 정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 '이진 탐색(Binary Search)'을 위한 전처리 과정 정렬 알고리즘 종류 : 선택, 삽입, 퀵, 계수 등 파이썬의 기본 정렬 라이브러리를 적용하면 좀 더 효과적 알고리즘 효율의 중요성 → 면접 단골문제 내림차순 정렬 방법 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행 파이썬 리스트 원소 뒤집는 메서드 : 복잡도 O(N) 선택 정렬 매번 '가장 작은 것을 선택'하는 정렬방식 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 교환, 그다음 작은 데이터를 앞에서 두번째 데이터와 교환 → 반복 선택 정렬 소스코드 # 선택 정렬 소스코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]..

DFS (깊이 우선 탐색 알고리즘) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 BFS (너비 우선 탐색 알고리즘) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘 문제 해설 BFS 유형 : 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색 ex) 110 010 011 해당 입력을 예시로, 특정한 노드를 방문시에 이전 노드 거리 +1을 해서 값을 업데이트 시작은 (1, 1)이며 해당 노드의 값은 항상 1 상, 하, 좌, 우로 탐색을 진행하여 새롭게 방문한 (1, 2) 노드 값 2로 업데이트 계속해서 1씩 증가하며 최단 경로로 이동 * 소스코드 상에서, 첫 번째 시작 위치는 재방문하여 3으로 변경될 여지가 있으나, 문제에서 단순히 오른쪽 아래로 이동하는 ..