목록전체 글 (85)
Seung's Learning Record
재귀와 백트래킹은 개념은 정말 어려울게 없지만 문제를 풀때는 정말 머리를 쥐어짜내게 만드는거같다... 이 두 개념은 정말 문제를 많이 풀어봐야만 감이 잡히는 개념이기에 관련 문제를 많이 풀어보는걸 추천! 재귀 함수 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 어떠한 문제를 재귀로 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것과 같다. 재귀함수를 작성할 땐, 다음과 같은 조건이 지켜져야 한다. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함.(Base condition) 모든 입력은 base condition으로 수렴해야 함. void func(int n){ if(n == 0) return; cout
DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. 넓게 탐색하는 것이 아닌 깊게 탐색하는 방법이다. 각각의 좌표가 시작 좌표에서 떨어진 거리를 알 수 있었던 bfs와 달리 dfs는 거리 측정이 힘들다. 그래서 배열에서 탐색을 하는 문제에선 주로 BFS를 사용하여 문제를 푼다. 그렇다고 DFS가 아예 안쓰이는 것은 아니니 잘 이해하고 넘어가는게 좋다. DFS 구현 이론 큐를 사용하는 BFS와 달리 DFS는 스택을 사용하여 구현한다. BFS에서 사용한 예시인 파란칸 찾기 문제를 예시로 대략적인 플로우를 살펴보자. 시작 좌표 방문 표시 후, 스택에 push 스택의 top값을 pop하고 해당 좌표에 접해있는 상,하,좌,우 좌표를 확인 인접 좌표..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/k5GpZ/btsz1e47zlT/CncmzCDi4KvSKBdk5qYNIk/img.png)
BFS(Breadth First Search) BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점을 방문한 후, 인접한 정점들을 우선 방문하는 방법이다. 해당 그래프의 방문 순서가 저럴 경우, 큐에 값이 들어가고 나가는 순서는 다음과 같다. push(0) -> pop(0) -> push(1), push(2) -> pop(1) -> push(3) -> pop(2) -> push(4) -> pop(3) -> pop(4) BFS구현 이론 BFS 구현을 위해서는 큐를 사용해야 한다. 쉬운 이해를 위해 빨간색,파란색이 섞여있는 2차원 배열에서 파란색 칸만을 탐색하는 알고리즘을 작성하는 과정을 예로 들어 구현 플로우를 대강 정리해보자. 시작 좌표(0,0)를 방문 표시 후,..
Deque 이란? Restricted sturcture의 끝판왕인 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하다. Deque 성질 원소의 추가 O(1) 원소의 제거 O(1) 최상단의 원소 확인 O(1) 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 하지만 STL을 통해 인덱스에 접근이 가능하다. Deque 구현 덱의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다. 배열을 사용한 구현 const int MX = 1000000; int dat[2*MX+1]; int head = MX, tail = MX; void push_front(int x){ dat[head]=x; head--; } void push_back(int x){ dat[tail]=x; ..
Queue 란? 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 먼저 들어간 원소가 먼저 나오게 되는 FIFO(First In First Out) 구조이다. 큐에서는 원소가 제거되는 쪽을 가장 앞인 front, 원소가 삽입되는 쪽을 가장 뒤인 rear라고 부른다. Queue 성질 원소의 추가 O(1) 원소의 제거 O(1) 맨 앞, 맨 뒤 원소 확인 O(1) 맨 앞, 맨 뒤를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 Queue 구현 스택과 마찬가지로 큐 역시 배열을 이용하여 구현하는 방법과 STL을 이용하여 구현하는 방법이 있다. 배열을 사용한 구현 스택에서의 구현 방법을 큐에 대입해보자. 원소가 삽입되면 tail이 가르키는 인덱스에 값을 넣고 tail++를 하면된..
STACK 이란? 한쪽 끝에서만 원소를 삽입/삭제할 수 있는 자료구조이다. FILO(First In Last Out)구조로 가장 먼저 삽입된 원소가 가장 나중에 빠져나온다. 원소가 삭제되는 위치를 최상단, top이라고 부른다. STACK 성질 원소의 추가 O(1) 원소의 제거 O(1) 최상단의 원소 확인 O(1) 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 STACK 구현 스택의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다. 배열을 사용한 구현 const int MX = 1000000; int dat[MX]; int pos = 0;//다음 원소가 삽입될 인덱스 정보 //원소 삽입 void push(int x){ dat[pos++] = x; } ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/Ln8P7/btszzJYlKwx/1OAswskMLjW8pjD9VCylD1/img.png)
연결 리스트란? 연결 리스트란 쉽게 말해 원소를 저장할 때, 그 다음 원소의 위치를 같이 저장하는 선형 자료구조이며, 이때 원소들은 붙어있지 않고 흩어져있다. 연결 리스트를 사용했을때의 주요 시간 복잡도는 다음과 같다. k번째 원소를 확인/변경하기 위해서는 O(k)가 필요함 => 해당 연산을 반복 수행해야하는 경우, 연결 리스트보다 배열이 효율적(배열은 O(1)) 임의의 위치에 원소를 추가/제거는 O(1)이 필요함 => 해당 연산을 반복 수행해야하는 경우, 배열보다 연결 리스트가 효율적(배열은 O(N)) 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조 이중 연결 리스트 - 각 원소가 자신의 이..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/baWfJs/btszCE2zzka/cGwntr9tajGgdiTLbu3De1/img.png)
해당 문제를 풀기 위해 필요한 사전 지식으로는 아스키코드와 배열정도일 것이다. 당장에 구글에만 쳐봐도 정답 코드가 넘쳐난다. 그러던중 바킹독님의 풀이가 유독 눈에 띄어서 정리할 겸 가져와봤다. #include #include using namespace std; int main(void){ int arr[26]={0}; string s; cin >> s; for(auto c : s) arr[c-'a']++; for(auto i : arr) cout
c++ 11버전 이후로는 범위 기반 반복문을 사용할 수 있다. 범위 기반 반복문이란 시작과 끝점을 알려주지 않아도 알아서 처음부터 끝까지 순회를 해주는 반복문이다. 사용법 for(int elem : arr){ elem ++; cout
배열 배열이란 index와 그에 대응되는 데이터들로 이루어진 자료구조이며, 일반적으로 같은 타입의 데이터들이 순차적으로 메모리에 저장된다. 배열의 성질 O(1)에 k번째 원소를 확인/ 변경 가능 추가적으로 소모되는 메모리의 양, 즉 overhead가 거의 없음 Cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 배열의 선언 당시 지정된 크기로 고정됨. => 사이즈를 벗어난 인덱스에 접근 시, 런타임 에러 발생 int arr1[5]={1,2,3}// 1,2,3,0,0 int arr2[]={1,2,3,4,5} //크기 5로 고정됨 int arr3[5]={0};// 원소가 모두 0으로 초기화 됨 int arr4[5];//원소가 모두 쓰레기값으로 초기화 됨 이때 배열의 ..