알고리즘 (Python)/이것이 코딩 테스트다 with 파이썬 (이론) (9) 썸네일형 리스트형 [그래프 이론 알고리즘] 다양한 그래프 알고리즘 그래프 이론 알고리즘 - DFS/BFS 알고리즘과 최단 경로 알고리즘에서 다룬 내용은 모두 그래프 알고리즘의 한 유형 - 크루스칼 알고리즘은 그리디 알고리즘, 위상 정렬 알고리즘은 큐 자료구조 혹은 스택 자료구조를 활용 - 문제에서 서로 다른 객체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 함 서로소 집합 자료구조 (Union-Find 자료구조) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - union과 find 2개의 연산으로 조작 가능 - union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 - find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 트리 자료구조를 이용하여 집합을 표현 서로소 집합 .. [최단 경로 알고리즘] 가장 빠른 길 찾기 최단 경로 알고리즘 - 말 그대로 가장 짧은 경로를 찾는 알고리즘 - '한 지점에서 다른 특정 지점까지의 최단 경로', '모든 지점에서 다른 모든 지점까지의 최단 경로' 등의 사례가 존재 - 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많음 - 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용됨 음의 간선 - 0보다 작은 값을 가지는 간선 - 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택됨 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 .. [다이나믹 프로그래밍] 다이나믹 프로그래밍 다이나믹 프로그래밍 - 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 탑다운과 바텀업 2가지 방식, 메모이제이션 기법이 있음 - 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식 - 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 문제들의 중복 여부를 확인 - 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤 (탑다운 방식) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션 기법을 적용할 수 있으면 코드를 개선 다이나믹 프로그래밍을 사용 가능한 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 .. [이진 탐색 알고리즘] 범위를 반씩 좁혀가는 탐색 순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위하여 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음 - 이름처럼 순차로 데이터를 탐색한다는 의미 - 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단 - 리스트에 특정 값의 원소가 있는지 체크할 때 사용 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N) 이진 탐색 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 - 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데.. [정렬 알고리즘] 기준에 따라 데이터를 정렬 정렬 알고리즘 - 정렬 (Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐 - 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 됨 정렬 라이브러리 - 현대의 정렬 알고리즘은 정립되어 있기 때문에 앞으로 큰 개선이 이루어질 것이라고 예상하기는 어려움 - 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제 - 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 많음 정렬 라이브러리의 시간 복잡도 - 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장 - 정렬 라이브러리는 이미 잘 작성된 함수이므로 .. [DFS/BFS 알고리즘] 탐색 알고리즘 DFS/BFS 탐색 (Search) - 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미 - 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸 그래프 (Graph) - 그래프는 노드와 간선으로 표현됨 - 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말함 - 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현 - 그래프는 크게 2가지 방식으로 표현할 수 있음 인접 행렬 (Adjacency Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 - 파이썬에서는 2차원 리스트로 인접 행렬을 구현할 수 있음 - 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)라고 작성 - 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요.. [DFS/BFS 알고리즘] 꼭 필요한 자료구조 기초 자료구조 (Data Structure) - 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미 - 스택과 큐는 자료구조의 기초 개념으로 Push (삽입)과 Pop (삭제) 두 핵심적인 함수로 구성 스택 (Stack) - 스택은 박스 쌓기에 비유할 수 있음 (흔히 박스는 아래에서부터 위로 차곡차곡 쌓음) - 이러한 구조를 선입후출 (FILO) 또는 후입선출 (LIFO)라고 함 - 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없음 - 기본 리스트에서 append(), pop() 함수를 사용하면 스택 자료구조와 동일하게 동작 큐 (Queue) - 큐는 대기줄에 비유할 수 있음 (흔히 놀이공원에서 줄을 설 때 먼저 온 사람이 먼저 들어감) - 나중에 온 사람일수록 나중에 들.. [구현 알고리즘] 아이디어를 코드로 바꾸는 구현 구현 알고리즘 - 코딩테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' - 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미 - 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다로움 - 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미 - 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미 - 일반적으로 알고리즘 문제를 풀 때는 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용 [그리디 알고리즘] 당장 좋은 것만 선택하는 그리디 그리디 알고리즘 (탐욕법) - 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘 - 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 - 유형이 다양하기 때문에 암기가 아닌 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함 - 보통 코딩 테스트에서는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 문제에서 '가장 큰 순서대로'와 같은 기준을 알게 모르게 제시 - 대체로 위 기준은 정렬 알고리즘을 사용하여 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제 - '가장 큰 화폐 단위부터'와 같이 탐욕적으로 문제에 접근했을 때 정.. 이전 1 다음