2024. 9. 20. 01:07ㆍDevelopers 공간 [Basic]/Software Basic
이번 글에서는 개인적으로 코딩테스트를 준비하는 과정에서 가장 기초적으로 중요하다고 생각했던 부분을 정리해두려고 합니다.
코딩테스트는 회사마다 혹은 대회마다 스타일이 다르기 때문에, 다양한 케이스에 대해 준비하는 것 중 가장 기본적인 것들만 설명하겠습니다.
C++과 Python 둘 다 해두면 좋지만, 라이브러리를 사용하는데 있어 C++이 더 어려움이 많기 때문에 코딩 테스트에 활용하기엔 Python이 조금더 편한 편입니다.
따라서 이번 글에서 Python을 기준으로 정보를 정리하겠습니다. 중간중간 C++관련된 내용은 더보기로 참조부탁드립니다.
<구성>
0. 기초 지식
a. Space Complexity
b. Time Complexity
c. C & C++ 기본
d. Python 기본
e. 미리 정해둘 것
1. 기초 알고리즘
a. Brute Force / Back Tracking
b. BFS(Breadth First Search)
c. Simulation
d. DP(Dynamic Programming)
2. 성능 기반 구현
a. 기본적인 상황
b. 복잡한 상황
3. 새로운 알고리즘 추가
a. Shortest Path Algorithm
b. MST(Minimum Spanning Tree)
글효과 분류1 : 코드
글효과 분류2 : 폴더/파일
글효과 분류3 : 용어설명
글효과 분류4 : 글 내 참조
글효과 분류5 : 글 내 참조2
글효과 분류6 : 글 내 참조3
0. 기초 지식
가장 기본적인 지식이지만, 코딩테스트에서 중요하게 활용하는 기본적인 개념들 먼저 가볍게 정리하고 시작하려고 합니다.
기초 전공지식도 포함되어있지만, 어느 정도는 시험에 들어가기 전에 미리 상기하고 들어가면 좋으니 살펴보겠습니다.
공간복잡도와 시간복잡도의 개념에 대해 살펴보고, 이번 챕터에서는 C++과 Python의 기본개념에 대해 간단히 살펴보겠습니다.
a. Space Complexity
공간 복잡도는 프로그램이 수행되는 동안 메모리공간을 얼마나 효율적으로 활용하는지로 나타낼 수 있습니다.
프로세스가 차지하고 있는 메모리는 아래와 같이 4가지의 segment로 나뉩니다.
이런 segment들은 두가지로 분류됩니다.
- 정적 Segment : 프로그램이 실행되는 시점에 할당되어 프로그램이 끝날 때까지 유지되는 영역
▶ 위 Text Segment, Data Segment - 동적 Segment : 프로그램 실행 중, 필요에 의해 할당하고 해제하는 영역
▶ 위 Heap Segment, Stack Segment
그럼 가장 아래의 영역부터 살펴보겠습니다.
1. Text Segment(Code Segment) : Read Only
Assembly 코드 등 작성한 코드와 Constant들이 포함되는 부분입니다. 컴파일 타임에 사이즈가 고정되며, 프로세스 간에 메모리 최적화를 위해 공유되기도 합니다.
2. Data Segment : Read-Write
global 변수 & static 변수를 저장하는 공간이며, 사실은 아래와 같이 두가지로 나뉩니다.
- Data : 아래와 같이 Runtime 이전에 초기화된 데이터들이 포함됩니다.
int i = 3;
char a[] = "Hello World";
static int b = 2023; // Initialized static global variable
void foo (void) {
static int c = 2023; // Initialized static local variable
}- BSS(Block Stated Symbol) : 직접 초기화되지 않은 데이터들이 포함됩니다. 이들은 Runtime 이후에 0으로 초기화되곤 합니다.
static int i;
static char a[12];
3. Heap Segment
프로그램 실행 중 malloc&free(new&delete)에 의해 할당 및 반환되는 영역으로, 보통 pointer로 관리됩니다.
fragmentation이 일어날 수 있으며, size가 flexible하게 바뀝니다.
heap overflow 에러가 있기는 하지만 보통 메모리할당을 미리 막기 때문에 현상이 자주 보이지는 않습니다.
4. Stack Segment
지역 변수, 함수 파라미터, return 주소 등이 포함된 가장 일시적인 영역입니다. Stack형태로 유지되므로 LIFO(Last-In, First-Out) 원리로 동작하며, Heap보다 빠릅니다.
최대 사이즈가 정해져있어 stack overflow에러가 나기도 합니다. stack의 max size는 시스템마다 다르며, 바꾸어 줄 수 있습니다. (ulimit)
| Memory | Stack | Heap |
| 사이즈 | 상대적으로 작음 | 상대적으로 큼 |
| 접근 속도 | 상대적으로 빠름 | 상대적으로 느림 |
| Allocation | LIFO 방식 | Dynamic |
| Allocation 이후 Resize |
불가 | 가능 |
| Deallocation | 자동 | 수동 |
보통 코딩테스트에는 아래와 같은 메시지로 안내가 됩니다.
힙,정적메모리 256MB 이내, 스택 메모리 1MB 이내
이 말을 다시해석하면 Heap Segment와 정적메모리(Data Segment, Text Segment)는 합쳐 256MB이내이며, Stack Segment는 1MB이내로 프로그램을 만들어야합니다.
코딩 중에 자세하게 메모리를 확인하며 코딩할 수는 없습니다. 따라서 결론적으로, 코딩테스트할 때 다음을 참조하고 코딩하면 웬만하면 무리가 가지 않습니다.
- 최대한 상수가 될만한 요소는 Code Segment에 유지해야 합니다.
- Heap은 많이 사용할 수 있지만 느리므로, 공유가 필요한 Input 정보 혹은 간단한 할당에만 사용할 Output 정보에 사용합니다.
- Stack은 많이는 사용할 수 없지만 빠르므로, Heap으로 사용하는 것 이외에는 Stack으로 해결해야합니다.
b. Time Complexity
시간 복잡도는 프로그램이 수행되는 동안 얼마나 오래 걸리는지로 나타낼 수 있는데, 보통은 입력 크기에 대한 Loop를 활용한 연산 수로 나타냅니다.
이는 아래와 같은 Asymptotic Notation(근사표기) 세가지로 표현할 수 있습니다
1. O (Big-O method)**
알고리즘의 Worst case, 즉 Upper Bound를 나타 낼 때 사용합니다. 즉, 이 함수는 최대 이정도의 복잡도를 가지고 수행할 것 이라고 할 수 있습니다. 가장 많이 사용됩니다.
$$f(n) = O(g(n))$$
2. Ω (Omega method)
알고리즘의 Best case를 나타 낼 때 사용합니다. 즉, 이 함수는 최소 이정도의 복잡도를 가지고 수행할 것 이라고 할 수 있습니다.
$$f(n) = \Omega (g(n))$$
3. θ (Theta method)
알고리즘의 Average case, 즉 Lower Bound를 나타 낼 때 사용합니다. 즉, 이 함수는 평균적으로 이정도의 복잡도를 가지고 수행할 것 이라고 할 수 있습니다.
$$f(n) = \theta (g(n))$$
예를 들어 아래와 같은 "n개 중에 정답을 찾는" Linear Search 코드를 작성했다고 했을 때 위의 분석으로 하면 아래와 같습니다.
- $O(n)$
- $\Omega(1)$
- $\sum_{i=1}^{n}\frac{\theta (i)}{(n+1)} = \frac{\theta (\frac{(n+1)*(n+2)}{2})}{(n+1)} = \theta (n)$ : Uniformly Distributed된 Array라고 했을 때
#include <bits/stdc++.h>
using namespace std;
int search(int arr[], int n, int x){
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
int main(){
int arr[] = { 1, 10, 30, 15 };
int x = 30;
int n = sizeof(arr) / sizeof(arr[0]);
cout << x << " is present at index " << search(arr, n, x);
return 0;
}
역시나 코딩 중에 완벽하게 시간 복잡도를 확인하며 테스트할 수는 없습니다. 따라서 보통의 코딩테스트에서는 Big-O method를 for/while loop의 개수 정도로 예상하며 최적화합니다.
이는 아래 챕터에서 자세히 살펴볼 예정입니다.
c. C & C++ 기본
이번엔 C/C++을 활용하는 경우 기본적으로 알아아 할만한 것들을 살펴보겠습니다.
당연히 이 챕터의 내용만으로 코딩테스트를 할 수 있는건 아닐 겁니다. 가장 많이 활용되었던 개념들만 기록했습니다.
C++을 선택한 경우 일반적으로는 아래와 같은 템플릿을 활용합니다. 이 템플릿은 아예 그냥 손에 익혀두는 편이 좋습니다.
** setbuf()는 해당 파일의 버퍼특성을 바꿔주는 방법으로, NULL을 사용하면 버퍼를 사용하지 않고 바로바로 읽고 쓰게 됩니다. 선택입니다.
#include <stdio.h>
#include <algorithm>
using namespace std;
// Global Variables
int T; // The # of Tests
int answer; // Temporary answer for 1 test
int inputs; // Temporary inputs for 1 test
int main() {
setbuf(stdout, NULL);
int t=1;
scanf("%d", &T);
while (T--) {
// ...
printf("#%d %d\n", t++, answer);
}
return 0;
}
코딩할 때 라이브러리를 사용하기도 하는데, 아래와 같은 라이브러리는 최대/최소 등을 할당할 때 손쉽게 사용할 수 있습니다.
- #include <limits.h>
- UINT_MAX
- INT_MAX
- CHAR_MAX
- #include<float.h>
- FLT_MAX
- DBL_MAX
** 이외에도 STL이나 Algorithm 라이브러리를 활용해서 구현을 하는 경우도 있는데, 이는 선택적으로 사용이 불가한 경우도 있어 아래 더보기를 참조해서 참조하시길 바랍니다.
--------------------------------------------------------------------
<STL 자료구조>
STL은 코딩테스트에서 허용되는 곳도 있고, 허용되지 않는 곳도 있습니다. 하지만 허용되는 경우 적어도 아래와 같은 자료구조는 익혀두는 편이 좋습니다.
1. Vector
가장 많이 쓰는 vector는 아래와 같이 선언합니다.
#include <vector>
vector<int> *vptr = new vector<int>(10);
vector<int> v;
vector를 사용하는 방법들을 정리해보았습니다.
| 얻기 | v.front(); v.back(); v[i] v.at(i) |
| 넣기 | v[i] = 2; v.push_back(2); v.insert(v.begin() + 2, 2); v.insert(v.begin() + 2, v2.begin(), v2.end()); //v2넣기 v.assign(v2.begin(), v2.end()) |
| 초기화 | vector<int> v(10); // 길이 10짜리 vector<int> v(5, -1); // -1, -1, -1, -1, -1 vector<int> v{10,20,30} ; vector<int> v(arr, arr + 3); <----int arr[] = { 10, 20, 30 }; vector<int> v(v2.begin(), v2.end());, vector<int> v(v2) |
| 초기화(2D) | vector< vector<int> > v; ----> vector<int> v2(1,5); v.push_back(v2); vector<vector<int>> v(M, vector<int> (N, 0)); |
| 재초기화 | v.resize(5, 0) v = {10,20,30}; v = v2; <---- vector<int> v2{ 10, 20, 30 }; ** 주의할 것은 vector오브젝트는 포인터가 아닙니다. 그래서 pointer로 만들어서 넘기지 않으면 deep copy해서 넘어갑니다. |
| 인덱스로 지우기 | v.erase(v.begin()+i) |
| 첫 값을 찾아 지우기 | auto it = std::find(v.begin(), v.end(), 값); if (it != v.end()) { v.erase(it); } |
| 모든 값을 찾아 지우기 | v.erase(std::remove(v.begin(), v.end(), 값), v.end()); |
| 리턴 (임시 값) | return vector<int>{2,1}; return vector<int>(10); |
| 루프 | for (int x : v) printf("see this : %d\n", x); |
2. Queue
다음은 queue입니다. 필요할 때만 쓰면 되는데, 아래와 같이 선언합니다.
#include <queue>
queue<pair<int, int> > q;
queue<int> q;
queue를 사용하는 방법들을 정리해봤습니다.
| 길이 얻기 | q.size() |
| 비어있는지 확인 | while(!q.empty()){} |
| 지우기 | q.pop() |
| 얻고 지우기 | q.front() q.front().first, q.front().second // Pair 인 경우 q.pop() |
| 넣기 | q.push(make_pair(a,b)) |
3. Hash
hash는 아래와 같은 unordered_map을 활용합니다.
** c++11기준 MurmurHashUnaligned2 해쉬 함수사용합니다.
#include <unordered_map>
unordered_map<string,int> u;
| 존재여부 확인 | if(find(key) ==u.end()) |
| 사이즈 얻기 | u.size(); |
| 비었는지 확인 | u.empty(); |
| 비우기 | u.clear() |
| 지우기 | u.erase(key) |
| 얻기 | u[key] |
| 넣기 | u[key]= value |
--------------------------------------------------------------------
--------------------------------------------------------------------
<Algorithm>
알고리즘을 포함해 자주 활용하는 함수들은 아래와 같습니다.
| 제곱 | #include <math.h> | pow(a,b) |
| 축적하기 | #include <numeric> | int sum = std::accumulate(v.begin(), v.end(), 초기값); |
| 절대값 | #include <algorithm> | abs(a) |
| 정렬하기** | #include <algorithm> | std::sort(v.begin(), v.end()) |
| 찾기 | #include <algorithm> | find(v.begin(), v.end(), 값) != v.end() auto it = std::find(v.begin(), v.end(), 값); |
| 최소 최대 | #include <algorithm> | min(a,b) max(a,b) |
| 값으로 지우기 | #include <algorithm> | v.erase(remove(v.begin(), v.end, 값), v.end()) |
| 벡터 최소 최대 | #include <algorithm> | *min_element(v.begin(), v.end()) *max_element(v.begin(), v.end()) |
특히 sort는 자주 사용되는데, 자체 비교 요건을 가진 sort를 활용해서 구현할 필요가 있을 때도 있습니다.
#include <algorithm>
typedef struct abc {
int Y;
int X;
int NUM;
int DIRECT;
}MYSTRUCT;
bool cmp(MYSTRUCT a, MYSTRUCT b) {
if (a.NUM > b.NUM) {
return true;
}
else {
return false;
}
}
sort(MYSTRUCT_LIST.begin(), MYSTRUCT_LIST.end(), cmp);
단, 위를 구현할 때 아래와 같은 조건을 만족하는 strict weak ordering을 주의해야합니다.
- 반드시 antisymmetric
x<y true 이면 y<x false - transitive
x<y, y<z 이면 x<z - transitive for =
a=b, b=c 이면 a=c - irreflexive
x<x : 항상 False
또한 Python의 sorted는 원본을 유지하고 정렬된 복사본을 반환하는 특징을 가지는 함수인데, C++에서는 sort를 적용하면 내부적으로 정렬을 해버립니다.
따라서 정렬된 복사본을 반환하고 싶다면 위에서 얘기한 바와 같이 vector의 deep copy특징을 활용합니다.
std::vector<int> sorted = original;
std::sort(sorted.begin(), sorted.end());--------------------------------------------------------------------
--------------------------------------------------------------------
<Struct 활용>
C++에서 Struct를 활용하는 간단한 예시는 아래와 같습니다.
| 선언 |
struct Person { std::string name; int age; }; |
| typedef struct { std::string name; int age; } Person; |
|
| 생성자 추가 |
struct Person { std::string name; int age; Person(std::string n, int a) : name(n), age(a) {} }; |
| struct Person { std::string name; int age; Person(std::string n, int a) { name = n; age = a; } }; |
|
| 생성시 초기화 |
Person p = {"Bob", 25}; // C++11 이후 |
| Person p{"Charlie", 35}; // C++17 이후 | |
| 생성후 초기화 | Person p; p.name = "Alice"; p.age = 30; |
--------------------------------------------------------------------
d. Python 기본
이번엔 Python을 활용하는 경우 기본적으로 알아아 할만한 것들을 살펴보겠습니다.
필자는 Python을 선택한 경우 보통 아래와 같은 템플릿을 활용합니다.
** global은 수정할 때만 선언해줍니다. 읽는 것은 선언하지 않아도 가능하며, global을 선언하지 않고 해당 변수에 만약 "할당"을 해버리면 지역변수로 간주되어 에러가 날 수도 있습니다.
** sys라이브러리를 막는 경우 sys.stdin.readline을 해주지 않아도 동작하지만, 사용하면 속도가 훨씬 빠릅니다.
import sys
input = sys.stdin.readline
answer=-1
def main():
global answer;
# ...
if __name__=='__main__':
T = int(input())
for t in range(1, T + 1):
N, M, K = list(map(int, input().split()))
main()
print("#{} {}".format(t, answer));
아래와 같이 파일을 받아 처리하는 경우도 있습니다.
import sys
input = sys.stdin.readline
answer=-1
def main():
global answer;
# ...
if __name__=='__main__':
sys.stdin = open('test.txt', 'r')
T = int(input())
for t in range(1, T + 1):
N, M, K = list(map(int, input().split()))
main()
print("#{} {}".format(t, answer));
아래는 Python을 활용할때 참고하면 좋을 자료 구조들입니다.
| list | tuple | set | dictionary | |
| 순서(index) | O | O | X | X |
| 중복 | O | O | X | X |
| 수정 | O | X(immutable) | O | O |
| 초기화 | list() [0] * N |
tuple([0]*N) (10,20,30,40,50) |
{1, 2, 3}, set() {10,20,30,40,50} |
dict() {1:"a", 2:"b", 3:"c"} |
| 접근 | a[인덱스] | a[인덱스] | 값 in a == True ** 혹은 리스트로 바꿔서 |
a[key] |
| 추가 | a.append(10) a + [10] |
a + (10,) | a.add(10) | d[key] = value |
| 개수 | len(a) | len(a) | len(a) | len(d) |
| 삭제 | a.pop(i) a.remove(v) |
(불변, 삭제 불가) | a.remove(v) or discard(v) | del d[key] |
| 확인 | val in a | val in a | val in a | key in d |
| 인덱스 | a.index(val) | a.index(val) | (인덱스 없음) | (key 인덱스 없음) |
| 루프 | for x in a: for i, x in enumerate(a): |
for x in a: for i, x in enumerate(a): |
for x in a: | for k in d: → key 순회 for k in d.keys(): → key 순회 for k in d.values(): → value 순회 for k in d.items(): → key, value 순회 |
| 합 | sum(a) | sum(a) | sum(a) (숫자일 때만) | sum(d.values()) (숫자일 때만) |
| 최소/최대 | min(a) max(a) |
min(a) max(a) |
min(a) max(a) |
min(d) max(d) (key 기준) |
** 이외 사용하는 몇가지 자료구조나 method들을 참조하려면 아래 더보기를 참조하세요
--------------------------------------------------------------------
<자주 쓰는 자료구조 및 Methods>
1. frozenset : 기존의 set과 달리 아래와 같은 특징을 가지는 set입니다.
- 변경 할 수 없습니다. (immutable)
- 순서가 무관한 "집합"이 됩니다.
a = {frozenset((1,1)):'a', frozenset((1,2)):'b'}
a[frozenset((2,1))]='c'
# {frozenset({1}): 'a', frozenset({1, 2}): 'c'}
2. queue
queue를 활용하는 예시는 아래와 같습니다.
queue = queue.Queue()
queue.get()
queue.put()
queue.qsize()
queue.empty()
3. list
위 리스트에 대해 위에서 언급되지 않은 몇가지 함수들이 있습니다. 이들을 알고 있으면 좋습니다.
| 정렬하기 | $O(NlogN)$ | a.sort() : 내부정렬 sorted(a) |
| 비우기 | $O(1)$ | a.clear() |
| 추가하기 | $O(1)$ $O(N)$ |
a.append(값) a.extend([값들]) a.insert(위치, 값) ** insert는 뒤에 넣지 않고, 앞에 넣을때 사용할 수 있지만 $O(N)$이 걸려서 안쓰는 것이 좋습니다. 따라서 차라리 append한 후에 역순으로 변경하는 것을 추천합니다. |
| 개수 얻기** | $O(N)$ | a.count(값) |
| 위치 얻기 | $O(N)$ | a.index(값) |
| 지우기 | $O(N)$ | a.remove(값) del a[위치] |
| 특정 조건을 만족하는 것들 지우기 | $O(N)$ | a = [x for x in a if x % 2 != 0] ** 이렇게 하지 않으면 리스트가 중간에 변경되어서, 루프를 돌면서 삭제하는 것은 불가합니다. |
| 뽑기 |
$O(N)$ $O(1)$ |
a.pop(위치) ** $O(N)$이며 queue보다 느립니다. a.pop() : 맨 뒤 ** $O(1)$ |
| 역순으로 | $O(N)$ | a.reverse() a=a[::-1] |
| soft copy | $O(1)$ | b=a |
| deep copy | $O(N)$ | b=a.copy() |
| 길이 얻기 | $O(1)$ | len(a) |
| 최소 최대 얻기 | $O(N)$ | min(a), max(a) |
| 최소 최대의 인덱스 얻기 | $O(N)$ | a.index(max(a)) ** 성능이 좋지 않고 같은 값이 있는 경우 잘못된 값을 얻을 수 있습니다. argmax = max(enumerate(a), key=lambda x: x[1])[0] ** 값으로 정렬하고 인덱스 리턴 |
| 2차원 초기화 | $O(N)$ | a = [[] for _ in range(N)] a = [(y,x) for x in range(5) for y in range(5)] ** a = [[]]*N은 동작하지 않습니다 |
| 리스트 전체 True | $O(N)$ | all(_a >= 2 for _a in a) |
| 리스트 일부 True | $O(N)$ | any(_a >= 2 for _a in a) |
| 리스트 결합 | Lazy Iter | zip(a,b) zip(a,b,c) ** a와 b와 c의 길이는 같지 않으면 짧은 것에 맞춰집니다. |
4. heap사용법
Heap은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete Binary Tree) 기반의 자료구조입니다.
Heap은 두가지로 나뉘는데, 부모 노드가 제일 큰 Max Heap과 제일 작은 Min Heap이 있습니다. 뒤 설명할 Python의 heapq는 Min Heap이 default입니다.
- Heapify $O(n)$ : n개의 데이터를 heap 아키텍쳐로 변경하는 과정
- Insert $O(log\,n)$ : 맨 밑에 넣어서 위로 올립니다.
- Find-min** $O(1)$ : 가장 위에서 빼냅니다.
- Delete-min $O(log\,n)$ : 가장 위에서 빼내고, 재정렬합니다.
사용 방법은 아래와 같습니다.
import heapq
# 1. Heapify
heaplist = [50 ,10, 20]
heapq.heapify(heaplist)
# 2. Start from the start
heaplist = []
heapq.heappush(heaplist, 50)
heapq.heappop(heaplist)
5. Adjacency List
그래프를 표현하는 자료구조는 인접 행렬(adjacency matrix)와 인접 리스트(adjacency list)가 있는데, 아래와 같이 directed graph인 경우 시작점을 기준으로 만들어주면 좋습니다.
adj = [[] for _ in range(N)]
adj[start].append((end, cost))--------------------------------------------------------------------
--------------------------------------------------------------------
<기타 주의점>
1. range 활용법
아래와 같이 활용합니다.
reversed(range(0, 5)) #4,3,2,1,0
range(4,-1,-1) #4,3,2,1,0
range(1,6) #1,2,3,4,5
2. [] if else 쓰는 법 주의
위에서 "특정 조건을 만족하는 것들 지우기"에 표현되기는 했지만 아래와 같은 두가지의 경우, 리스트를 조건에 의해 새로만들 때 아래 두가지를 구분해주어야합니다.
- else있을 때 : 앞에 if와 else가 존재합니다.
[값1 if 조건 else 값2 for …]
[x if x > 0 else 0 for x in nums]- else없을 때 : 뒤에 if만 존재합니다.
[값 for 항목 in 반복가능객체 if 조건]
[x for x in nums if x > 0]
# 2D
[(y,x) for x in range(5) for y in range(5) if y<3 and x<3]
[(y,x) for x in range(5) if x<3 for y in range(5) if y<3]
이를 활용해 아래와 같이 dictionary 도 만들어줄 수 있습니다. 아래는 dict1과 dict2에서 최대값을 뽑아 하나의 dictionary로 합치는 과정입니다.
{k: max(dict1[k], dict2[k]) for k in dict1}set에서도 같습니다.
set(s for s in S if s>=2)
3. key넣어주기
min, max, sorted같은 명령어에는 key=를 넣어줄 수 있습니다. 이는 주어진 자료구조의 특징을 반영하기 위함입니다.
아래는 dictionary를 활용한 예입니다. 기본적으로 dictionary를 sorted해주면 key를 기준으로 정렬됩니다.
d = {'b': 2, 'a': 5, 'c': 1}
sorted_items = sorted(d.items())
print(sorted_items) # [('a', 5), ('b', 2), ('c', 1)]
하지만 value를 기준으로 하는 경우 아래와 같이 key=를 사용해서 정렬해주어야합니다.
sorted_by_value = sorted(d.items(), key=lambda x: x[1])
# [('c', 1), ('b', 2), ('a', 5)]
# If you want it back to dictionary
sorted_dict = dict(sorted(d.items(), key=lambda x: x[1]))
다음은 min, max를 살펴보겠습니다. 아래는 특이한 구조의 리스트라 key=를 사용해서 최대값을 찾아주었습니다.
people = [
{'name': 'Alice', 'age': 25},
{'name': 'Bob', 'age': 30},
{'name': 'Charlie', 'age': 22}
]
oldest = max(people, key=lambda p: p['age']) # Bob
단, 아래와 같이 리스트에 조건이 있는 경우 max에 빈 리스트가 들어갈 수 있으므로 default값을 넣어주어야합니다.
oldest = max([p for p in people if p['age']>30], key=lambda p: p['age'], default=-1)
4. Swap
다른 언어와 다르게 아래와 같이 Swap을 한번에 구현가능합니다.
a = [10, 20, 30, 40]
a[1], a[2] = a[2], a[1]
5. 개행 없이 프린트하기
별 것 아닌 것 같지만, String을 다루는 문제에서 사용해야할 수도 있습니다.
print(b, end = " ")
6. 길이가 같은 리스트 두개 다루기
zip을 활용합니다.
c = [x + y for x, y in zip(a, b)]
7. ord함수를 활용해 String다루기
String은 대부분 리스트와 비슷하게 동작하지만, 직접 숫자로 바꾸어 다루고 싶은경우 ord()함수를 활용합니다. 아래와는 'A', 'B', 'C', 'D' 같은 문자열을 순서대로 1, 2, 3, 4로 매핑하는 과정입니다.
char = 'B'
ord(char) - ord('A')
#1
--------------------------------------------------------------------
e. 미리 정해둘 것
이번엔 문제를 시작하기에 앞서서 문제를 풀기전에 정해두면 좋은 것들을 이야기해보려고합니다.
아래 내용들을 미리 정하고 가지 않으면 문제를 풀때 혼란스러울 수도 있습니다.
1. 좌표계
Vision분야와 코딩테스트에서는 우리가 알고 있는 X축 & Y축과 달리, 아래와 같은 좌표계를 사용합니다.
Y축의 순서가 다르죠? 사실 어떻게보면 좌표계는 본인이 정하기 나름이라고 할 수도 있겠지만, 기존에 알고 있는 X축과 Y축의 순서로 데이터를 받으려면 실제 문제를 보기도 힘들고 다루기도 어려워집니다.
따라서 위와 같은 순서의 좌표계를 익숙하게 익혀놔야합니다. 먼저 데이터를 받을때를 살펴보면 데이터는 아래와 같이 주어집니다.
0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0
이를 내 데이터에 넣을 때는 아래와 같은 코드로 받게 됩니다. 위에서 정의한 순서대로 정의하면 X축을 한 줄씩 받으며 Y축으로 받게되는 것이죠.
MAP=[]
for i in range(Y_LENGTH):
MAP.append(list(map(int, input().split())))MAP = [list(map(int, input().split())) for _ in range(Y_LENGTH)]
이번엔 데이터를 사용할때도, 위와 같이 데이터를 받았기 때문에 아래와 같이 사용해야합니다.
for i in range(Y_LENGTH):
for i2 in enumerate(X_LENGTH):
index_x = i2
index_y = i
value = MAP[index_y][index_x]--------------------------------------------------------------------
<C++의 경우>
int MAP[Y_LENGTH][X_LENGTH];
for (register int i = 0; i < Y_LENGTH; i++) {
for (register int i2 = 0; i2 < X_LENGTH; i2++) {
scanf("%d", &MAP[i][i2]);
}
}
for (register int i = 0; i < Y_LENGTH; i++) {
for (register int i2 = 0; i2 < X_LENGTH; i2++) {
int index_x = i2;
int index_y = i;
int value = MAP[index_y][index_x];
}
}--------------------------------------------------------------------
이렇기 때문에 방향을 미리 정의해놓을때도 아래와 같이 Y축의 방향이 헷갈릴 수 있습니다.
방향을 정의하는 것이야 문제별로 다르게 정의하게되겠지만 필자는 아래와 같이 정의합니다.
direction = ((0,0),(1,0),(0,1),(0,-1),(-1,0))--------------------------------------------------------------------
<C++의 경우>
int direct[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} }int direction[5][2] = { {0,0}, {1,0},{0,1},{0,-1},{-1,0}};--------------------------------------------------------------------
2. Sort
알고리즘을 배울때 가장 먼저 배우는 Search와 Sort는 미리 알고 있어야할 것 같습니다. 특히 Search는 어떻게든 찾을 수 있다 하더라도, Sort는 미리 알고 있어야만 합니다.
Sort는 아래와 같이 다양한 방법들의 특징이 있습니다.
** In-Place : 추가 메모리 공간을 거의 사용하지 않고, 원본 리스트 자체를 변경하여 정렬을 수행하는 방식이며,
** Stable : “값이 같은 요소”들 사이의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬. 다른 뜻으로, 기준이 2개인 경우 첫번째 기준으로 sort후 두번째 기준으로 sort했을 때 첫번째의 sort순서가 유지되어야합니다.
| Time Complexity |
Space Complexity |
Stable | In-Place | ||
| Bubble Sort | $O(N^2)$ | $O(1)$ | O | O | 앞에서 부터 인접한 두개씩 비교하면서 swap |
| Selection Sort | $O(N^2)$ | $O(1)$ | X/O | O | 내 뒤에 있는 것들 중에 “가장 작은것”들과 swap |
| Insertion Sort | $O(N^2)$ | $O(1)$ | O | O | 내 앞에 있는 것들보다 작으면 앞으로 한칸씩 옮기기 |
| Heap Sort | $O(NlogN)$ | $O(1)$ | X | O | Heap을 만들며 sort하기 |
| Merge Sort | $O(NlogN)$ | $O(N)$ | O | X | recursive하게 작은 문제부터, 비교하면서 모아진 array만들기 |
| Quick Sort | $O(N^2)$ | $O(N)$ | X | O | resursive하게 작은문제부터, pivot을 기준으로 양쪽의 최소와 최대를 바꾸기 |
위 내용에 대해 항상 다 외우고 있을 필요는 없습니다. 하지만 다양한 Sort방법에 대해 어떻게 동작하는지를 알아둘 필요는 있고, 대부분의 Sort의 시간면에서 worst case는 항상 $O(NlogN)$이라는 것을 인지해야합니다.
하지만 실제 코딩테스트에서는 아래와 같이 간단한 방법으로 사용하곤합니다.
** 기본적으로 오름차순으로 동작하고, reverse=True 옵션을 넣어주면 내림차순으로 동작합니다.
** Python sort(), sorted() 알고리즘은 Timsort알고리즘($O(NlogN)$, Stable, 부분 In-Place)을 활용합니다.
sorted(a)--------------------------------------------------------------------
<C++의 경우>
** C++ sort() 알고리즘은 Introsort($O(NlogN)$, Non-Stable, In-Place)를 활용합니다.
** 역시나 기본적으로 오름차순으로 동작합니다.
sort(test_output.begin(), test_output.end());--------------------------------------------------------------------
1. 기초 알고리즘
아마 전공 혹은 다양한 경험을 통해 다양한 알고리즘들을 보셨겠지만, 코딩테스트에서 기본적으로 알아야할 유형이 4가지 있습니다.
- Brute Force / Back Tracking
- BFS(Breadth First Search)
- Simulation
- DP(Dynamic Programming)
필자는 아래와 같은 사이트에서 위 알고리즘들을 연습하는 것으로 시작합니다.
- SWEA(SW Expert Academy) : https://swexpertacademy.com/main/main.do
- 백준 : https://www.acmicpc.net/
아래와 같은 기본적인 알고리즘을 완벽히 숙지하면 삼성 A형 등 일반 대기업의 코딩테스트는 충분했던 것 같습니다.
a. Brute Force / Back Tracking
Brute force는 "무차별 대입"이라는 뜻으로, 가능한 모든 케이스를 살펴보겠다는 뜻입니다.
이를 활용하기 위해서는 DFS(Depth First Search)를 활용한 Back Tracking을 사용하며, 이 둘은 혼용해서 말합니다.
** DFS(Depth First Search) : 그래프 탐색 알고리즘(Graph traversal algorithm), 즉 모든 꼭지점을 탐색하기 위한 알고리즘입니다. 그 중 깊이(Depth)를 우선으로 탐색하는 알고리즘을 DFS라고 부르며, stack을 활용해 구현할 수 있습니다.
** Back Tracking : 해를 찾다가, 지금 가고 있는 길이 가능성이 없어보이면 더이상 그 경로를 확인하지 않고 돌아가는 방법입니다.
DFS를 구현할 수 있는 방법은 시스템 stack을 활용한 순환 호출을 활용하거나, 직접 stack 자료구조를 활용해 구현하는 것이 가능하며, 필자는 시스템 stack을 활용해 구현하겠습니다.
우리가 모든 경우를 살펴본다고 했지만, 결국 특정한 상황을 기준으로 모두 살펴봐야하는 것이고 이는 아래와 같은 순열과 조합을 구현해 살펴보게됩니다.
- 중복순열 $_n\pi _r$ : n개중에 r개를 중복해서 순서를 고려해서 선택
- 일반순열 $_nP_r$ : n개중에 r개를 중복없이 순서를 고려해서 선택
- 일반조합 $_nC_r$ : n개 중에 r개를 중복없이 순서를 고려않고 선택
- 중복조합 $_nH_r$ : n개 중에 r개를 중복해서 순서를 고려않고 선택
$$\begin{aligned}
_n\pi _r&=n^r\\
_nP_r&=n(n-1)(n-2)\dots (n-r+1)=\frac{n!}{(n-r)!}\\
_nC_r&=\frac{_nP_r}{r!}=\frac{n!}{r!(n-r)!}\\
_nH_r&=_{n+r-1}C_r
\end{aligned}$$
쉬운것부터 하나씩 DFS로 구현하는 법을 살펴보겠습니다.
- 중복순열 $_n\pi _r$ : n개 중에 중복을 허용해 search해서 depth를 r만큼 길이로 선택
- SELECTED_LIST의 역할이 "n개 중에 선택된 것들"을 의미하는, 순서가 중요한 array가 됩니다.
** global로 선언된 SELECTED_LIST를 활용하는 것이 싫다면, 함수의 파라미터로 넘겨주는 방법도 있습니다.
** 필요하다면 모든 문제마다 초기화하는 것을 잊지마세요 - ex) SWEA 2112($_3\pi _D$)
- SELECTED_LIST의 역할이 "n개 중에 선택된 것들"을 의미하는, 순서가 중요한 array가 됩니다.
def dfs(depth):
if depth == r:
# CHECK!
return
for i in range(n):
SELECTED_LIST[depth] = i
dfs(depth + 1)--------------------------------------------------------------------
<C++의 경우>
void dfs(int depth) {
if (depth == r) {
// CHECK!
return;
}
for (register int i = 0; i < n; i++) {
SELECTED_LIST[depth] = i;
dfs(depth+1);
}
}--------------------------------------------------------------------
- 일반순열 $_nP_r$ : n개 중에 search해서 depth를 r만큼 길이로 선택
- SELECTED_LIST의 역할이 "n개 중에 선택된 것들"을 의미하는, 순서가 중요한 array가 됩니다.
- USED_LIST는 "n개 중에 사용된 것들"를 의미하는, 순서가 중요하지 않은 binary array가 됩니다.
** 필요하다면 모든 문제마다 초기화하는 것을 잊지마세요
- 중복순열이 일반순열이 되면, "이미 사용한 것"들에 대해 체크를 해주어야합니다.
즉, 이미 사용한 것은 사용하지 못하므로 이를 확인할 방법이 필요합니다.
- 중복순열이 일반순열이 되면, "이미 사용한 것"들에 대해 체크를 해주어야합니다.
- ex) SWEA 9942($_NP_N$)
def dfs(depth):
if depth == r:
# CHECK!
return
for i in range(n):
if USED_LIST[i] > 0:
USED_LIST[i] -= 1
SELECTED_LIST[depth] = i
dfs(depth + 1)
USED_LIST[i] += 1 # 백트래킹--------------------------------------------------------------------
<C++의 경우>
void dfs(int depth) {
if (depth == r) {
// CHECK!
return;
}
for (register int i=0; i < n; i++) {
if (0 < USED_LIST[i]) {
USED_LIST[i] -= 1;
SELECTED_LIST[depth] = i;
dfs(depth+1);
USED_LIST[i] += 1;
}
}
return;
}--------------------------------------------------------------------
- 일반조합 $_nC_r$ : n개 중에 search해서 depth를 r만큼을 선택
- SELECTED_LIST의 역할이 "n개 중에 선택된 것들"을 의미하는, 순서가 중요한 array가 됩니다.
- USED_LIST는 "n개 중에 사용된 것들"를 의미하는, 순서가 중요하지 않은 binary array가 됩니다.
- 순열하려는 n개 중에 "일부 중복"이 있는 경우가 있습니다. 이런 경우, 아래 코드에서 USED_LIST를 초기화 할 때 1보다 큰 값을 가지는 값이 될 수 있습니다.
$$_nP_r(\text{s of r are same})=\frac{n!}{(n-r)!}\times\frac{1}{s!}$$ - 위의 경우 USED_LIST에 각각 만약 무한대 값이 할당이 되면, USED_LIST가 무효화되므로 위 중복순열과 같습니다.
ex) SWEA 4008
($_{N-1}P_{N-1}\times\frac{1}{n_{+}}\times\frac{1}{n_{-}}\times\frac{1}{n_{\times}}\times\frac{1}{n_{\div}}$)
- 순열하려는 n개 중에 "일부 중복"이 있는 경우가 있습니다. 이런 경우, 아래 코드에서 USED_LIST를 초기화 할 때 1보다 큰 값을 가지는 값이 될 수 있습니다.
- location : 순열이 조합이 되면 탐색하는 n만큼의 search를 처음부터하는 것이 아닌, "탐색한 위치 다음"부터 search를 해야합니다.
- ex) SWEA 4012($_NC_{\frac{N}{2}}$), SWEA 2115($_nC_2$)
def dfs(depth, location):
if depth == r:
# CHECK!
return
for i in range(location, n):
if USED_LIST[i] > 0:
USED_LIST[i] -= 1
SELECTED_LIST[depth] = i
dfs(depth + 1, i)
USED_LIST[i] += 1--------------------------------------------------------------------
<C++의 경우>
void dfs(int depth, int location) {
if (depth == r) {
// CHECK!
return;
}
for (register int i = location; i < n; i++) {
if (0 < USED_LIST[i]) {
USED_LIST[i] -= 1;
SELECTED_LIST[depth] = i;
dfs(depth+1, i);
USED_LIST[i] += 1;
}
}
return;
}--------------------------------------------------------------------
- 중복조합 $_nH_r$ : n개 중에 중복을 허용해 search해서 depth를 r만큼을 선택
- SELECTED_LIST의 역할이 "n개 중에 선택된 것들"을 의미하는, 순서가 중요한 array가 됩니다.
- location : 순열이 조합이 되면 탐색하는 n만큼의 search를 처음부터하는 것이 아닌, "탐색한 위치 다음"부터 search를 해야합니다.
def dfs(depth, location):
if depth == r:
# CHECK!
return
for i in range(location, n):
SELECTED_LIST[depth] = i
dfs(depth + 1, i)--------------------------------------------------------------------
<C++의 경우>
void dfs(int depth, int location) {
if (depth == r) {
// CHECK!
return;
}
for (register int i = location; i < n; i++) {
SELECTED_LIST[depth] = i;
dfs(depth+1, i);
}
return;
}--------------------------------------------------------------------
나머지는 직접 분류해보시길 바랍니다.
ex) SWEA 2105, SWEA 1949, SWEA 2383
일반조합 문제중 문제를 하나 풀어보시려면 아래 더보기를 참조하세요
--------------------------------------------------------------------
<SWEA 4012 결과>
T=-1
N=-1
allmap=[]
checked_list=[]
result_min=40000*8
def check():
global allmap, checked_list
A_food = 0
B_food = 0
for i, b in enumerate(checked_list):
for i2, b2 in enumerate(checked_list):
if b and b2 :
A_food += allmap[i][i2]
elif not b and not b2:
B_food += allmap[i][i2]
return abs(A_food-B_food)
def dfs(depth:int, location:int):
global N, result_min, checked_list
if depth==int(N/2):
result_min = min(result_min, check())
return
if location==N:
return;
checked_list[location]=True
dfs(depth+1, location+1)
checked_list[location]=False
dfs(depth, location+1)
if __name__=="__main__":
T = int(input())
for t in range(T):
N= int(input())
allmap=[]
checked_list=[]
for i in range(N):
allmap.append(list(map(int, input().split())))
checked_list.append(False)
result_min=40000*8
dfs(0, 0)
print("#{} {}".format(t+1, result_min))--------------------------------------------------------------------
b. BFS(Breadth First Search)
BFS 또한 위 DFS에 이은 그래프 탐색 알고리즘이지만, 코딩테스트에서는 주로 2D로 주어진 테이블에서 해당 테이블을 traverse하는데 사용합니다.
** BFS(Breadth First Search) : 그래프 탐색 알고리즘(Graph traversal algorithm), 즉 모든 꼭지점을 탐색하기 위한 알고리즘입니다. 그 중 너비(Breadth)를 우선으로 탐색하는 알고리즘을 BFS라고 부르며, queue을 활용해 구현할 수 있습니다.
위에서 언급된 바와 같이 BFS는 queue를 활용해 구현합니다. DFS와 달리 시스템 stack같은 것이 없으니, queue를 직접 구현해 구현해야합니다.
기본적으로 traverse하기 위한 BFS는 아래와 같이 구현합니다.
- MAP_CHECK : 이미 방문했는지 확인하기 위한 array 및 table이며, 위의 USED_LIST와 비슷합니다.
** BFS가 불리기 전에 MAP_CHECK는 항상 초기화되어야합니다. - direction : 어느 방향으로 BFS를 탐색할지 미리 정의해야합니다.
- Check1 : 일반적으로 확인하는 부분으로, 하나의 노드를 탐색할 때마다 확인하는 곳입니다.
direction = ((1,0), (0,-1), (-1,0), (0,1))
def BFS(y,x):
myqueue = queue.Queue()
MAP_check[y][x] = 1
myqueue.put((y,x))
while(!myqueue.empty())
tempy, tempx = myqueue.get()
#Check1
for diy, dix in direction:
new_tempy = tempy+diy
new_tempx = tempx+dix
if(new_tempy>=0 and new_tempy<N and
new_tempx>=0 and new_tempx<N and
not MAP_check[new_tempy][new_tempx]):
MAP_check[new_tempy][new_tempx]=1
myqueue.put((new_tempy,new_tempx))
return--------------------------------------------------------------------
<C++의 경우>
int direct[4][2] = { {0,1},{1,0}, {0,-1}, {-1,0}};//y,x
void BFS(int y, int x) {
queue<pair<int, int> > q;
int tempy, tempx;
int new_tempy, new_tempx;
MAP_CHECK[y][x] = 1;
q.push(make_pair(y, x));
while (!q.empty()) {
tempy = q.front().first;
tempx = q.front().second;
q.pop();
// Check1
for (register int i = 0; i < 4; i++) {
new_tempy =tempy + direct[i][0];
new_tempx =tempx + direct[i][1];
if (0 <= new_tempy && new_tempy < SIZE_Y &&
0 <= new_tempx && new_tempx < SIZE_X &&
!(MAP_CHECK[new_tempy][new_tempx])) {
MAP_CHECK[new_tempy][new_tempx] = 1;
q.push(make_pair(new_tempy, new_tempx));
}
}
}
return;
}--------------------------------------------------------------------
특정 경우에는 하나의 Layer씩 탐색하고 싶은 경우가 있을 수도 있습니다.
즉, 한번 queue를 통해 주변을 탐색하고 나서 남은 queue의 값들을 전부 탐색하고, 그다음 queue의 요소들을 탐색하겠다는 것이죠.
- Check2 : 한번의 Layer를 탐색하고 나서 확인하는 곳입니다.
- ex) SWEA 2117
direction = ((1,0), (0,-1), (-1,0), (0,1))
def BFS(y,x):
myqueue = queue.Queue()
MAP_check[y][x] = 1
myqueue.put((y,x))
while(!myqueue.empty())
myqueue_size = myqueue.qsize()
for i in range(myqueue_size):
tempy, tempx = myqueue.get()
#Check1
for diy, dix in direction:
new_tempy = tempy+diy
new_tempx = tempx+dix
if(new_tempy>=0 and new_tempy<N and
new_tempx>=0 and new_tempx<N and
not MAP_check[new_tempy][new_tempx]):
MAP_check[new_tempy][new_tempx]=1
myqueue.put((new_tempy,new_tempx))
#Check2
return--------------------------------------------------------------------
<C++의 경우>
int direct[4][2] = { {0,1},{1,0}, {0,-1}, {-1,0}};//y,x
void BFS(int y, int x) {
queue<pair<int, int> > q;
int queue_size;
int tempy, tempx;
int new_tempy, new_tempx;
MAP_CHECK[y][x] = 1;
q.push(make_pair(y, x));
while (!q.empty()) {
queue_size = q.size();
for (register int i = 0; i < queue_size; i++) {
tempy = q.front().first;
tempx = q.front().second;
q.pop();
// Check
for (register int i = 0; i < 4; i++) {
new_tempy =tempy + direct[i][0];
new_tempx =tempx + direct[i][1];
if (0 <= new_tempy && new_tempy < SIZE_Y &&
0 <= new_tempx && new_tempx < SIZE_X &&
!(MAP_CHECK[new_tempy][new_tempx])) {
MAP_CHECK[new_tempy][new_tempx] = 1;
q.push(make_pair(new_tempy, new_tempx));
}
}
}
// CHECK2
}
return;
}--------------------------------------------------------------------
BFS 문제 중 문제를 하나 풀어보시려면 아래 더보기를 참조하세요
--------------------------------------------------------------------
<SWEA 2117 결과>
import queue
T = 0
N=0
M=0
MAP = []
MAP_check = []
direction = ((1,0), (0,-1), (-1,0), (0,1))
def check(y,x):
global N, M, MAP, MAP_check,direction
myqueue = queue.Queue()
count_home = 0
max_home=0
MAP_check[y][x] = 1
myqueue.put((y,x))
for k in range(1,N+2):
myqueue_size = myqueue.qsize()
for i in range(myqueue_size):
tempy, tempx = myqueue.get()
if(MAP[tempy][tempx]):
count_home+=1
for diy, dix in direction:
new_tempy = tempy+diy
new_tempx = tempx+dix
if(new_tempy>=0 and new_tempy<N and new_tempx>=0 and new_tempx<N and not MAP_check[new_tempy][new_tempx]):
MAP_check[new_tempy][new_tempx]=1
myqueue.put((new_tempy,new_tempx))
price = 1
for tempk in range(2,k+1):
price += tempk*4-4
result = M*count_home-price
if result>=0:
if max_home < count_home:
max_home = count_home
return max_home
if __name__=="__main__":
T = int(input())
for t in range(T):
N, M = list(map(int, input().split()))
MAP = []
MAP_check=[]
real_result = -1
for i in range(N):
MAP.append(list(map(int, input().split())))
MAP_check.append([0]*N)
for y in range(N):
for x in range(N):
for i in range(N):
for i2 in range(N):
MAP_check[i][i2]=0
real_result = max(check(y,x), real_result)
print("#{} {}".format(t+1, real_result))
--------------------------------------------------------------------
c. Simulation
시뮬레이션은 말그대로 문제에서 구현된 것을 주어진 그대로 구현하는 문제입니다.
시간이 오래걸리는 경우가 대부분이며, 침착하게 문제를 푸는 것이 중요하고 아래의 팁을 참고하시면 좋습니다.
- 정말 문제에서 가이드 하는대로만 구현하면된다는 사실이 제일 중요합니다. 예를 들어 문제에서 순서가 주어진다면, 문제를 정말 "순서대로" 구현해야 합니다.
- 예시로 몇가지 상황을 줄텐데, 해당 예시는 앞으로 주어질 테스트케이스의 첫번째 케이스일 확률이 높습니다. 이를 철저히 활용하는 것이 좋습니다.
- ex) SWEA 5650, SWEA 4014, SWEA 4013, SWEA 2382, SWEA 5656, SWEA 5653, SWEA 5648, SWEA 5644
Simulation 문제중 문제를 하나 풀어보시려면 아래 더보기를 참조하세요
--------------------------------------------------------------------
<SWEA 2382 결과>
아래 문제는 풀어보시면 아시겠지만, 문제에 주어진 순서대로 구현하지 않으면 오히려 정말 복잡해집니다.
T=-1
MAP=[]
bugs = []
direction = ((0,0), (-1,0), (1,0), (0,-1),(0,1))
def move():
global bugs
#2. Move!
cached = {}
for i, b in enumerate(bugs):
b['y'] = b['y']+direction[b['di']][0]
b['x'] = b['x']+direction[b['di']][1]
key = (b['y'], b['x'])
if key in cached :
cached[key].append(i)
else:
cached[key] = [i]
#3.half check
for b in bugs:
if b['y']==0 or b['y']==N-1 or b['x']==0 or b['x']==N-1:
b['num'] = int(b['num']/2)
if b['di'] ==1:
b['di'] =2
elif b['di'] ==2:
b['di'] =1
elif b['di'] ==3:
b['di'] =4
elif b['di'] ==4:
b['di'] =3
else:
raise Exception("ERROR!!!")
for k,vl in cached.items():
if len(vl)<=1:
continue;
max_index = max(vl, key=lambda v:bugs[v]['num'])
total_value = 0
for v in vl:
total_value += bugs[v]['num']
bugs[v]['live']=False
bugs[max_index]['live']=True
bugs[max_index]['num']=total_value
bugs = [b for b in bugs if b['live']==True]
if __name__=="__main__":
T = int(input())
for t in range(1, T+1):
N, M, K = list(map(int, input().split()))
MAP=[]
bugs=[]
for n in range(N):
MAP.append([0]*N)
for k in range(K):
y, x, num, di = list(map(int, input().split()))
bugs.append({'y':y,'x':x,'num':num,'di':di, 'live':True})
for i in range(M):
move()
total_bugs = 0
for b in bugs:
total_bugs += b['num']
print("#{} {}".format(t, total_bugs))--------------------------------------------------------------------
d. DP(Dynamic Programming)
DP는 복잡한 문제를 작은 하위문제로 나누어 푸는 최적화 알고리즘입니다.
DP라는 알고리즘 없이도 DFS등으로 그냥 문제를 풀수도 있을 것 같지만, DP를 활용하지 않고는 주어진 문제의 최소 Complexity가 풀어지지 않는 경우가 많습니다.
이는 아래와 같이 두가지로 나뉩니다.
- Top-Down방법 : Top 문제 결과를 캐시해 이후에 Bottom 결과가 구해진 후 재활용하며, 재귀함수를 활용한 Memoization으로 구현합니다.
- Bottom-Up방법 : Bottom 문제 결과를 활용해 Top 문제를 해결하며, 테이블을 활용한 반복문으로 구현합니다.
def fib_top_down(n, memo):
if n in memo:
return memo[n]
if n < 2:
memo[n] = n
else:
memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
return memo[n]
def fib_bottom_up(n):
if n < 2:
return n
memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
필자는 아래와 같이 테이블을 활용한 Bottom-Up방식으로 주로 활용합니다.
주의할 점은 아래와 같습니다.
- 테이블의 길이는 순서를 결정할 개수가 될텐데, 인덱스 0에도 0 등의 default값을 포함해놓는 추천드립니다.
- 문제가 아무리 복잡하더라도, 가장 첫번째 혹은 가장 쉬운 케이스를 직접 풀어보면서 차근차근 나아가는 것이 좋습니다.
- ex) SWEA 1952, BJ 14501, BJ 1005
DP 문제중 문제를 하나 풀어보시려면 아래 더보기를 참조하세요
--------------------------------------------------------------------
<SWEA 1952 결과>
T = -1
price = {'d':0, 'm':0, 'm3':0, 'm12':0}
plan = [0]*12
memoization = [0]*13
if __name__=="__main__":
T = int(input())
for t in range(1,T+1):
d,m,m3,m12 = list(map(int,input().split()))
price['d']=d
price['m']=m
price['m3']=m3
price['m12']=m12
plan = list(map(int,input().split()))
memoization = [0]*13
memoization[0] = 0
# Jan
memoization[1] = min(price['d']*plan[0], price['m'])
# Feb
memoization[2] = memoization[1]+ min(price['d']*plan[1], price['m'])
for i in range(3,13):
memoization[i] = min(memoization[i-3]+price['m3'], memoization[i-1]+min(price['d']*plan[i-1], price['m']))
answer = min(memoization[12], price['m12'])
print("#{} {}".format(t, answer))--------------------------------------------------------------------
2. 성능 기반 구현
위와 같이 기본적인 구현을 하고 나면 아래 링크를 통해, 이번엔 시간 복잡도 Big-O method($O()$)에 최적화하여 구현하는 방법을 살펴보면 좋습니다.
필자는 아래와 같은 사이트에서 최적화 연습을 합니다.
- 코딜리티 : https://app.codility.com/programmers/ (네이버 등 활용)
아래서 보일 여러가지 상황들은 낮은 레벨에서는 쉬워 보일 수 있지만 위와 같은 방식으로 "문제만 푸는 것"으로는 부족합니다. 따라서 아래와 같은 주의사항들을 참고해 문제를 차근차근 풀어보는 것을 추천합니다.
- 결국에는 Big-O method 기준으로 최적화를 진행하는 것이고, 예를 들어 $O(N\times M)$은 루프가 N과 M이 있다는 뜻입니다.
따라서 루프중복을 줄여야만 길이가 길어졌을 때도 해당 문제를 풀어낼 수 있고, 이를 최적화하는 과정입니다. - Big-O method, 즉 Worst Case를 고려해 최적화하기 때문에 특정 상황에서 "우연에 의해 빠르게 해결되는 방법"을 선택해도 문제가 풀리지 않습니다.
- Python의 경우 주의할 것
- Python같은 경우 len(리스트)등의 간단한 함수들을 제공해 내부적으로 ob_size라는 값을 만들어 저장하니 $O(1)$이지만, C++의 경우 struct나 class를 직접 만들어 사용하기엔 시작이 부족하니 보통 $O(N)$입니다.
- Python의 경우 미리 정의된 method인 max(리스트)나 할당할 때 쓰는 [값]*N은 어떻게 해도 원래대로 $O(N)$입니다.
이와 같이 성능 기반구현까지 가능하면, IT기업의 코딩테스트까지는, 완벽하진 않지만 가능해지는 것 같습니다.
먼저 위와 같은 개념을 이해하기 위해 기본적인 상황을 살펴보고, 복잡한 상황을 살펴보겠습니다.
a. 기본적인 상황
코딜리티 Lesson3 TapeEquilibrium
주어진 array에서 어떤 위치를 기준으로 앞과 뒤를 비교했을 때의 최소값을 찾는 문제입니다.
array를 쭉 가면서 N개의 경우에 대해 N개의 경우를 비교해 찾으므로 $O(N^2)$을 사용하는 것이 일반적인 경우입니다.
def solution(A):
answer_min=1000*100000
for p in range(1,len(A)) :
sumA =0
for a in A[:p]:
sumA+=a
sumB = 0
for a in A[p:]:
sumB+=a
answer_min=min(answer_min, abs(sumA-sumB))
return answer_min;
테스트 케이스를 통과했으니 제출을 해봅니다. 근데, 로직상은 문제가 없으니 정확도가 100%가 나오지만 시간상의 문제로 통과되지 않습니다.
아래는 Time Complexity가 나오는데, 이를 확인해보니 역시나 아래와 같습니다.
이느 아래와 같이 "미리 계산할 array를 구현하는 것은 $O(N)\times 3$ 이므로 Time Complexity면에서 최적화가 될 것 같습니다.
def solution(A):
answer_min=1000*100000
forward_sum_list=[]
backward_sum_list=[]
length = len(A)
current_sum=0;
for p in A :
current_sum+=p
forward_sum_list.append(current_sum)
current_sum=0;
for p in reversed(A) :
current_sum+=p
backward_sum_list.append(current_sum)
for i in range(1,length):
answer_min=min(answer_min, abs(forward_sum_list[i-1]-backward_sum_list[length-i-1]))
return answer_min;
이번에도 제출을 해봅니다.
이제 Time Complexity를 확인해보니 예상대로 최적화가 되었습니다.
b. 복잡한 상황
코딜리티 Lesson4 MaxCounters
주어진 array를 "주어진 순서대로" 살피면서 다른 array를 만드는 문제입니다.
문제 자체가 순서대로 따라가기를 원하는 것이기 때문에
- M개의 순서에 대해서 쭉 따라가면서 : $O(M)$
- 최대 값을 얻고 : $O(N)$
- N개의 count array를 만들고 : $O(N)$
하면 $O(MN^2)$이 됩니다. 하지만 최대값이 M과 N이 모두 최대 100,000개 이기 때문에 거의 $O(N^3)$와 같습니다. 이를 그대로 구현해보겠습니다.
def solution(N, A):
result = [0]*N
for a in A:
if a>N:
result = [max(result)]*N
else:
result[a-1]+=1
return result
pass
테스트 케이스를 통과했으니 제출을 해봅니다. 근데, 로직상은 문제가 없으니 정확도가 100%가 나오지만 시간상의 문제로 통과되지 않습니다.
아래는 Time Complexity가 나오는데, 이를 확인해보니 역시나 아래와 같습니다. 정확히 측정되지는 않은 것 같지만, 더 최적화를 진행해야할 것 같습니다.
그럼 위 3가지에 대해 한번씩 생각해보겠습니다.
- 일단 주어진 순서대로 따라가야하기 때문에 최소 A길이(M)에 대한 loop는 존재해야합니다 : $O(M)$
** 중간에 max counter를 마주쳤을 때 그 최대값을 알려면 순서대로 진행해야하기 때문에 - 근데 최대값을 구하는 과정은 매번 $O(N)$을 사용하지 않고, 직접 매번 값을 얻어낼 때마다 max를 비교해서 얻어낼 수도 있겠네요. : $O(1)$
- N개의 count array를 만들어내는 과정은 보류
def solution(N, A):
result = [0]*N
max_val=0
for a in A:
if a>N:
result = [max_val]*N
else:
result[a-1]+=1
max_val = max(result[a-1],max_val)
return result
pass
근데 완벽하지 않습니다. 다시 한번 3가지에 대해 생각해보겠습니다.
- 일단 주어진 순서대로 따라가야하기 때문에 최소 A길이(M)에 대한 loop는 존재해야합니다. : $O(M)$
- 근데 최대값을 구하는 과정은 매번 $O(N)$을 사용하지 않고, 직접 매번 값을 얻어낼 때마다 max를 비교해서 얻어낼 수도 있겠네요. : $O(1)$
- N개의 count array를 매번 최대값으로 만들어내지 말고, "전체가 최대값"인 경우에 대해 기록해두면서 이를 대체합니다.
하지만 맨 마지막에 한번더 루프를 돌면서 "전체가 최대값"이 반영되었는지를 확인해야하긴 하겠습니다 : $O(N)$
def solution(N, A):
result = [{'v':0, 'max':0} for i in range(N)]
max_current=0
max_default=0
for a in A:
if a>N:
max_default=max_current
else:
if result[a-1]['max']==max_default:
result[a-1]['v']+=1
else:
result[a-1]['v']=max_default+1
result[a-1]['max']=max_default
max_current = max(result[a-1]['v'],max_current)
return [d['v'] if d['max']==max_default else max_default for d in result ]
제출해보겠습니다.
이번엔 Time Complexity가 정확하게 나왔네요.
3. 새로운 알고리즘 추가
필자의 개인적인 의견으로, 여기까지했으면 이후로는 완벽하게 준비하는 것은 어렵다고 생각합니다.
다양한 코딩테스트에 유동적으로 대응하거나 대회에 나가 다양한 문제를 풀기 위해서는, 다양한 문제들을 풀어보며 새로운 알고리즘들을 추가로 익혀두거나, 다양한 문제들을 풀어볼 필요가 있습니다.
필자는 아래와 같은 사이트에서 추가 알고리즘을 연습하거나, 알고리즘이 아닌 다른 문제들을 풀어봅니다.
- 한국
- 코드그라운드 : https://www.codeground.org/
- 구름 Goorm : https://level.goorm.io/
- 프로그래머스 : https://programmers.co.kr/
- 외국
- 코드 시그널 : https://codesignal.com (디자인 패턴 관련, 외국계 기업 활용)
- 리트 코드 : https://leetcode.com/
다양한 알고리즘 중에 Graph 기반의 알고리즘 몇가지를 소개하겠습니다.
먼저, Graph는 아래와 같은 기준 등으로 구분합니다.
- Directed / Undirected : edge에 방향이 있는지
- Weighted : edge에 weight(가중치)가 있는지 (weight가 positive만 가능할 수도 있습니다.)
- Cyclic / Acyclic : Cycle이 생기는지
- Connected : 모든 두 꼭지점 사이에 이동할 가능성이 있습니다.
Graph들은 위 조건들을 기준으로 아래와 같이 다양하게 불립니다.
- DAG(Directed Acyclic Graph) : Directed & Acyclic
- Tree : Undirected & Acyclic & Connected
** 노드 N개에 Edge개수는 $N−1$ - Complete Graph : 그래프의 모든 정점이 1:1 간선으로 연결된 그래프이다.
** Undirected 일 경우 정점 N개일 때 Edge 개수는 $N(N−1)/2$
이런 그래프들의 종류에 따라 아래와 같은 알고리즘에 활용될 수 있습니다.
- MST(Minimum Spanning Tree) : Undirected & Weighted & Connected
- 전체 정점을 연결하면서 가중치 합이 최소인 트리 구성
- ex) Kruskal, Prim, Sollin
- ex) BJ 1922
- Shortest Path Problem : Directed+Undirected & Weighted(Positive) & Connected
- 특정 정점에서 다른 모든 정점까지의 최단 거리 계산
- ex) Greedy, Dijkstra
- ex) BJ 1238
- Topological Sort : DAG
- 모든 정점을 순서대로 나열하되, 모든 edge(u → v)에 대해 u가 v보다 앞에 오도록 정렬
- ex) Kahn, DFS
- ex) BJ 1005
그럼 이와 같은 알고리즘을 몇개만 살펴보겠습니다.
a. Shortest Path Algorithm
Shortest Path 알고리즘은 아래와 같이 두가지로 나뉩니다.
- Single Source - Single Destination (Greedy Algorithm) : 현재 local에서 최선을 다해가며 이동해 나가는 방법으로, 전체를 보았을 때의 최소 path는 알아내기 어렵습니다.
- Single Source - All Destination (Dijkstra Algorithm) : 모든 경로를 파악해 최소 path를 알아냅니다.
이번 글에서는 Dijkstra를 살펴보겠습니다.
ex) BJ 1238
먼저 예시 문제를 기본적인 Dijkstra알고리즘을 활용해 푼 결과는 아래와 같습니다.
def dijkstra(startpoint):
MAX = len(edges)*10000
# O(N)
costs = [MAX]*N
costs[startpoint]=0
#O(N)
visited = [False]*N
# O(N)
for i in range(N):
# O(M)
targets = [e for e in edges.items() if startpoint ==e[0][0]]
# O(M)
for key,value in targets:
target = key[1]
if costs[startpoint]+value < costs[target] :
costs[target] = costs[startpoint]+value
visited[startpoint]=True
# O(2N)
min_target = min([(i, cost) for i, cost in enumerate(costs) if visited[i]!=True], key=lambda x:x[1], default=(-1,-1))[0]
if min_target==-1:
break;
startpoint=min_target
return costs
if __name__=="__main__":
N,M,X = list(map(int, input().split()))
for m in range(M):
# Start, End, Weight
start, end, weight = list(map(int, input().split()))
edges[(start-1,end-1)]=weight
costs_back = dijkstra(X-1)
costs = []
for n in range(N):
costs.append(dijkstra(n)[X-1]+costs_back[n])
print(max(costs))
위에 구현된 dijkstra()함수를 보니 time complexity는 $O(N\cdot (N+M))$와 같습니다. 이대로 제출하면 아마 시간내에 통과하기는 어렵습니다.
먼저, directed graph이므로 Adjacency List를 활용하겠습니다.
def dijkstra1(startpoint):
MAX = len(edges)*10000
# O(N)
costs = [MAX]*N
costs[startpoint]=0
#O(N)
visited = [False]*N
# O(N)
for i in range(N):
# O(1)
targets = edges[startpoint]
# O(M)
for target,value in targets:
if costs[startpoint]+value < costs[target] :
costs[target] = costs[startpoint]+value
visited[startpoint]=True
#O(2N)
min_target = min([(i, cost) for i, cost in enumerate(costs) if visited[i]!=True], key=lambda x:x[1], default=(-1,-1))[0]
if min_target==-1:
break;
startpoint=min_target
return costs
if __name__=="__main__":
N,M,X = list(map(int, input().split()))
for m in range(M):
# Start, End, Weight
start, end, weight = list(map(int, input().split()))
if start-1 in edges :
edges[start-1].append((end-1, weight))
else:
edges[start-1]=[(end-1, weight)]
costs_back = dijkstra(X-1)
costs = []
for n in range(N):
costs.append(dijkstra(n)[X-1]+costs_back[n])
print(max(costs))
조금 최적화 되긴했지만, Time Complexity가 크게 바뀌지는 않습니다. 따라서 아래와 같이 heap을 활용해 구현해주어야 최적화된 성능이 나옵니다.
import heapq
def dijkstra(startpoint):
MAX = len(edges)*10000
# O(N)
costs = [MAX]*N
costs[startpoint]=0
prior_queue=[]
heapq.heappush(prior_queue,(0, startpoint))
#visited = [False]*N
while prior_queue:
# O(logN)
cost, startpoint = heapq.heappop(prior_queue)
#if visited[startpoint]:
# continue;
if cost > costs[startpoint]:
continue;
targets = edges[startpoint]
# O(M)
for target,value in targets:
if costs[startpoint]+value < costs[target] :
costs[target] = costs[startpoint]+value
# O(logN)
heapq.heappush(prior_queue,(costs[target], target))
#visited[startpoint]=True
return costs
결과적으로 Dijkstra최적화시의 성능인 $O((N + M)\,log\, N)$가 나옵니다.
주의할 점은 위 코드에 visited를 다 주석처리한 것을 볼 수 있는데, 이전에는 "최소인 것들만 찾아서 다음에 활용했다"면, 이번에는 "모든 노드들을 다 넣어준 다음에 아닌 경우에 continue"하는 경우로 구현했기 때문에 visited보다는 costs로 비교해야만 합니다.
즉, 최단 경로라는 보장이 없기 때문에 현재 이미 계산된 costs보다 작은 값이면 그냥 continue합니다.
b. MST(Minimum Spanning Tree)
MST알고리즘은 아래와 같은 종류가 있습니다.
- Kruskal : n 개의 node만으로 시작해, 전체적으로 cost가 작은 것을 연결합니다.
- Prim : 1개의 node에서 최소의 cost를 따라 node를 추가해가는 방법입니다.
- Sollin : 전체적으로 최소의 edge들을 선택해 연결하고 서로서로를 최소의 edge를 이용해 연결합니다.
이번 글에서는 Kruskal만 활용하겠습니다.
ex) BJ 1922
결국엔 Kruskal은 아래와 같은 두가지만 참조해서 구현하면 됩니다.
- 이전 단계에서 만들어진 Spanning Tree와는 상관없이, cycle을 형성하지 않는 한 무조건 최소 Edge 만을 선택합니다.
- 가장 작은 edge weight는 무조건 선택될 수 밖에 없습니다.
N=-1
M=-1
edges=[]
def check_root_for_acyclic(root_list, node):
if root_list[node]==node:
return node;
else:
return check_root_for_acyclic(root_list, root_list[node])
def kruskal():
# O(MlogM)
edges_sorted = sorted(edges, key=lambda x:x[0])
# O(N)
root_list=[i for i in range(N)]
result_weight=0
# O(M)
for w,a,b in edges_sorted:
# O(N)
a = check_root_for_acyclic(root_list, a)
b = check_root_for_acyclic(root_list, b)
if a==b: # Connected !
continue;
else: # Not Connected
# Choose any one with rule
if a<b:
root_list[b]=a
else:
root_list[a]=b
result_weight +=w
return result_weight
if __name__=="__main__":
N = int(input())
M = int(input())
for m in range(M):
a,b,cost =list(map(int, input().split()))
edges.append((cost,a-1,b-1))
result =kruskal()
print(result)
결과적으로 time complexity는 $O(M\,log\,M)$입니다.
time analysis : https://www.geeksforgeeks.org/worst-average-and-best-case-analysis-of-algorithms/
순열 조합 차이 : https://eocoding.tistory.com/58
중복조합 논리 : https://kenadams.tistory.com/entry/%EC%A4%91%EB%B3%B5%EC%A1%B0%ED%95%A9-%EA%B3%B5%EC%8B%9D
'Developers 공간 [Basic] > Software Basic' 카테고리의 다른 글
| [PyTorch] Multi-Loss 그리고 Huggingface Accelerator (0) | 2025.01.02 |
|---|---|
| [PyTorch] Optimizer & LR Scheduler 정리 (1) | 2024.08.17 |
| [PyTorch] PyTorch Lightning 그리고 Distributed Computing (2) | 2024.08.17 |
| [Python] Multi-process와 Multi-thread 구현하기 (1) | 2024.01.21 |
| [Pytorch] Attention Layer 분석 및 구축하기 (0) | 2023.06.20 |