Algorithm

정의와 성질 스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 된다. 이를 FILO(First In Last Out) 자료구조라고 부르기도 한다. 큐와 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 원소의 추가/제거의 시간 복잡도는 O(1)이다. 제일 상단의 원소 확인의 시간 복잡도는 O(1)이다. 제일 상단이 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능하다. 스택은 원소의 추가/제거, 그리고 제일 상단의 원소 확인 기능만 제공한다. 그래서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아니다...

정의와 성질 연결 리스트는 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소는 배열의 원소들처럼 연속하게 저장되는 것이 보장되지 않고, 흩어져 있다. 연결 리스트의 성질 K번째 원소를 확인/변경하기 위해 O(K)가 필요하다. 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거는 O(1)이다. 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만, 할당이 쉽다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) - 각 원소가 자신의 다음 원소의 주소를 가지고 있는 연결리스트이다. 이중 연결 리스트(Doubly Linked List) - 각 원소가 자신의 이전 원소와 다음 원소의 주소를 가지고 있는 연결 리스트이다...

정의와 성질 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다. 배열의 성질 O(1)에 K번째 원소를 확인/변경 가능하다. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다. 메모리 상에 데이터들이 연속으로 배치되어 있어 Cache hit rate가 높다. 메모리 상에 연속된 구간을 잡아야 해서 할당에 다소 제약이 있다. 사용 팁 memset 함수는 실수할 여지가 많다. for문은 투박하기는 하지만 실수할 여지가 없기 때문에 무난하고 좋다. algorithm 헤더의 fill 함수는 실수할 여지도 별로 없고 코드도 짧아 좋다. STL vector vector는 배열과 거의 동일한 기능을 수행하는 자료구조이다. 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱..

STL과 함수 인자 함수 인자 첫 번째의 경우, int를 함수 인자로 보내면 값이 복사되어 넘어간다. 그러므로 함수에서 값을 바꾸더라도 main의 변수 t에는 영향이 없다. 두 번째의 경우, 함수에서 배열을 인자로 받고 있다. 배열의 주소를 넘겨주게 되는 것이므로, arr[0]의 값은 바뀌게 된다. 세 번째의 경우, 구조체는 값이 복사되기 때문에 함수에서 값을 바꾸어도 원본에 영향을 주지 않는다. 참조자 swap1 함수는 인자로 복사된 값을 받았기 때문에 의도대로 swap되지 않는다. swap2 함수처럼 포인터를 보내거나, swap3 함수처럼 참조자(Reference)를 이용하여 해결할 수 있다. STL(Standard Template Library) - vector vector는 일종의 가변 배열로 크..

시간 / 공간 복잡도 시간 복잡도(Time Complexity) 입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관 관계 빅오 표기법(Big-O Notation) 주어진 식을 값이 가장 큰 대표 항만 남겨서 나타내는 방법 시간 복잡도를 표기할 때 빅오 표기법의 형태로 나타낸다. 시간 복잡도 그래프 N이 점점 커짐에 따라 시간 복잡도의 차이가 수행 시간에 아주 큰 영향을 주고 있음을 볼 수 있다. 풀이가 제한 시간 내에 문제를 통과할 수 있는지, 내 알고리즘의 시간 복잡도가 올바른지를 생각할 것! 공간 복잡도(Space Complexity) 입력의 크기와 문제를 해결하는 데 필요한 공간의 상관 관계 코딩 테스트에서 공간 복잡도 보다는 시간 복잡도 때문에 문제를 많이 틀리게 되므로, 공간 복잡도 보다는 시..

25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 매일매일은 아니어도 조금씩은 풀어야 할 것 같아서 풀어보게 되었다. 백준 허브라는 확장 플러그인이 있는데, 이걸 적용하면 백준 문제를 풀었을 때 깃에 바로 커밋이 된다. 어제 백준 허브도 설정해 놨고 신나서 몇 문제 조금 풀었다!! GitHub - lyh109/Algorithm: This is a auto push repository for Baekjoon Online Judge created w..