본문 바로가기

Algorithm

 (25)
[알고리즘] 서로소 집합 (Disjoint Sets) 서로소 집합(Disjoint Sets) - 공통 원소가 없는 두 집합 - {1,2}와 {3,4}는 서로소 관계 서로소 집합 자료구조 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1 ) 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 2 ) 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조로 불림 여러 개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정은 다음과 같음 1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 1 ) A와 B의 루트 노드 A', B' 를 각각 찾음 2 ) A'를 B'의 부모 노드로..
[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍(=동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 - 한 번 해결한 문제는 다시 해결하지 않도록 함 - 탑다운(하향식) / 보텀업(상향식)으로 두 가지 방식으로 구성 - 다이나믹 프로그래밍의 다이나믹은 별다른 의미 X ( * 자료구조에서 사용하는 동적 할당(프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법)과는 다름 ) 다이나믹 프로그래밍의 조건 다음의 조건을 만족할 때 사용할 수 있음 1. 최적 부분 구조(Optiaml Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 ..
[알고리즘] 이진 탐색 알고리즘 이진 탐색 알고리즘 순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 이진 탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면 데이터를 탐색 -> 시작점, 끝점, 중간점을 이요하여 탐색 범위 설정 1. 시작점[0], 끝점[9], 중간점[4] = 인덱스 의미 2. 중간점이 두 개 존재할 경우, 중간점 지점에서 소수점 이하 제거해서 단순히 4를 사용 3. 중간점 해당 값 8과 찾고자 하는 값을 비교하여, 중간점 값이 크다면 오른쪽 값은 확인할 필요X 4. 끝점을 중간점의 왼쪽으로 옮김 5. 중간점과 찾고자하는 값 비교 후 시작점 이동 6. 찾고자 하는 값이 인덱스 2에 위치한 것을 확인 이진 탐색 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일 =..
[알고리즘] 정렬 알고리즘(Sorting)(3) - 계수 정렬 계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(K+K)를 보장 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트 초기화 2. 각 인덱스가 데이터의 값에 해당 3. 각각의 데이터가 총 몇 번씩 등장했는 지 개수를 세면 됨 4. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 (Count) 5. 결과를 확인할 때 리스트이 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스 출력 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1,..
정렬 알고리즘(Sorting)(2) - 퀵 정렬 퀵 정렬 기준 데이터를 설정 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈 (첫 번째 데이터를 기준 데이터(Pivot)로 설정) 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 됨 1. 5 = 기준 데이터 = 피벗 2. 왼쪽에서부터 5보다 큰 데이터 선택, 오른쪽에서부터 5보다 작은 데이터 선택 (각각 7, 4 선택) 3. 7과 4 위치 변경 4. 4와 7 위치 변경 이후 다시 5를 기준으로 왼쪽에서부터 큰 데이터 선택, 오른쪽부터는 작은 데이터 선택 5. 9와 2 위치 변경 6. 9와 2 위치 변경 후, 다시 작업 수행 7. 데이터를 찾았는데 위치가 엇갈림 8. 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치 변경 9. 피..
정렬 알고리즘(Sorting)(1) - 선택정렬, 삽입정렬 정렬(Sorting) 데이터를 특정한 기준에 따라 순서대로 나열 선택정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꿈 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_index = j array[i], array[min_index] = array[min_index], array[i] #스와프 print(array) 선택정렬의 시간 복잡도 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내기 -> N + (N-1) + (N-2) + ... + 1 -> ..
파이썬 재귀 깊이 제한 변경(RecursionError) RecursionError BFS/DFS 문제를 풀다보면 RecursionError와 같은 런타임 에러를 마주하는 경우가 있다. 처음엔 코드 상에 문제가 없고 입력값에 맞는 출력값을 제대로 출력했는데도 에러가 떠서 당황했다.. RecursionError 해결방법 Python3 기준 최대 재귀 깊이는 1000이다. 그것보다 오버되는 수의 재귀가 호출되는 경우 에러가 발생하는 것이다. 이를 해결하기 위해서 파이썬 기본 재귀 깊이 제한을 임의로 변경하면 되는데 sys 라이브러리의 setrecursionlimit 메소드를 사용하면 된다. 백준 1012번 - 유기농 배추 문제 처음 제출한 코드 (에러 발생) - 코드 상에는 문제 없이 제대로 출력되는데 에러가 발생했다. import sys t = int(sys.s..
그리디 알고리즘(Greedy)과 구현(Implementation) (2) 구현(Implementation) - 머리 속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 풀이는 쉽지만 소스코드로 옮기기 어려운 문제를 의미 구현하기 어려운 문제 1 ) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 2 ) 특정 소수점 자리까지 출력해야 하는 문제 3 ) 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱해야 하는) 문제 완전탐색과 시뮬레이션 - 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행 문제 1 ) 상하좌우 n = int(input()) directions = list(input().split()) direction = ['R', 'L', 'U', 'D'] d..

티스토리툴바