공부/알고리즘 깨알팁 (5) 썸네일형 리스트형 [알고리즘 깨알팁] heapify 시간복잡도 계산 바쁘신분은 3번만 나중에 그림 첨부 요망 1. heapify란? heapify는 일반 배열을 heap 자료구조로 만드는 과정. 2. 시간복잡도 계산 heap에서 left child는 현재 인덱스 *2, right child는 현재 인덱스 *2 +1 이다. 즉, 루트(인덱스 번호 1)에서 현재 힙의 최대 사이즈 / 2 노드까지만 자식 노드가 존재한다. -> 현재 배열의 중앙부터 루트까지 heapify를 완성해 나가면 heap 자료구조를 만들 수 있다. 여기서, 노드의 중앙 부터 heapify가 일어나는 수를 최악으로 계산하면, heapify 과정을 트리의 높이 h - 현재 자신의 depth 번 하게된다. 노드의 중앙 부터 했으므로, 노드의 중앙은 높이가 h-1, 노드의 개수는 n/2개이다. 즉, 해당 노드.. [알고리즘 깨알 팁] 코드와 데이터를 분리하자 (테이블 만들기) 종만북에 나오는 명언이 하나 있습니다. '코드와 데이터를 분리하라.' 저는 코드와 데이터를 분리하는 기준을 다음과 같이 두고 있습니다. 코드 : 무언가를 하는 반복적인 행위.데이터 : 반복적인 행위를 하기 위한 데이터의 집합. 반복적인 행위가 이 데이터에 따라서 다른 결과를 도출함. 종만북에서도 데이터를 배열로 선언(테이블로 만듦)해서 배열을 순회하며 처리하라고 되어있습니다! 많은 분들이 쓰고 계신 예가 하나 있습니다. 바로 BFS에서 이동을 처리하는 경우이죠. 저는 2015년에 (x,y)를 이동하는 방법을 다음과 같이 만들었습니다. 1234567891011121314151617int x,y; void move(int d){ switch(d){ case 0: x -= 1; break; case 1: x .. [알고리즘 깨알 팁] BFS 짜는 법 알고리즘을 풀면 아주아주 많이 마주치는 것이 바로 이 BFS입니다.BFS는 최단거리를 찾을때 굉장히 자주쓰이죠! BFS는 보통 큐를 이용한 방식을 사용합니다!큐의 가장 앞에 있는 노드를 불러서 다음노드들을 맨 뒤에 놓으면,결국 먼저왔던 노드들은 먼저 처리되고 나중에 불러진 노드들은 나중에 처리됩니다.BFS는 이런 특징을 이용해서, 같은 거리에 있는 어떤 지점을 처리한 뒤에 다음 거리에 있는 지점을 탐색할 수 있기 때문에 최단거리로 쓸 수 있는 것이죠! BFS에서 가장 중요한 것은 무엇일까요!?바로, 방문 체크를 잘 만들어야 한다는 것입니다!방문 체크를 잘 못만들면 큐에 들어갔던 값이 또 들어가고.. 또 들어가고... 또 들어가서 메모리가 터져버리거든요! 이렇게.. 무한 루프에서 빠져나올수 없게되죠.하지만.. [알고리즘 깨알 팁] 비트로 연산하는 방법 비트로 연산하는 방법! 많은 사람들이 비트로 연산하는 것에 대한 두려움과 거부감을 가지고 있는 것 같습니다.하지만, 비트연산이란 알고보면 별 것 없습니다! 우선, 비트연산을 하기 위해서 알아야할 5가지의 연산 방법을 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든 비트를 1이면 0으로 0이면 1로 반전합니다.ex ) ~0b 1100 = 0b 0011 4. >> : 1 비트 오른쪽.. [알고리즘 깨알팁] 재귀로 1, 2차원 구간 처리하기 가끔가다 for문만으로는 문제를 처리하기 힘든 경우가 있습니다. 대표적인 경우가 2차원 배열에 대한 순열을 만들어야 하는 경우이죠. 자, 이럴때 여러분은 어떻게 해결하십니까!? 음.. 다른 분들도 편하게 느끼실진 모르겠지만, 제가 사용하는 방법을 알려드리려고 합니다! 우선, 일차원 배열에서 재귀 함수를 어떻게 작성하는지 생각해봅시다. 이렇게, 4개의 배열이 있으면, 위와 같이 0번 인덱스를 처리 후 1번 인덱스, 2번 인덱스, ... 마지막인덱스를 확인한 후에기저사례로 모두 검색한 다음 이전 인덱스로 돌아갑니다! 즉, 현재 인덱스를 처리한 후 다음 인덱스를 처리한다.마지막 인덱스까지 다 봤으면 return한다. 이 처리입니다! 1차원 배열에서는 다음 인덱스는 그냥 현재 인덱스 + 1 입니다. 코드로 나타.. 이전 1 다음
