2의 거듭제곱 판단하기 "어떤 자연수가 2의 거듭제곱임을 판별하라." 주어진 숫자가 \(2^{63}\)이하의 자연수라고 하면 당연히 2, 4, 8, 16, ... 순차적으로 확인해서 2의 거듭제곱인지 아닌지 판별하려고 할 것이다. (물론 unsigned long long type으로 말이다.) 쿼리가 m개라면 \(O(63m)\) 의 시간복잡도를 가질 것이다. 물론 이것만으로도 충분히 빠른 판단이라 생각되지만 특별한 방법을 찾게 되어서 블로그에 남기기로 하였다. 결론부터 말하면 어떤 자연수 \(n\)에 대해 \[(n\ \&\ (-n)) == n\] 이면 그 수는 2의 거듭제곱이다. 결론을 알았으니 맞는지 잠시 생각해보자. 1) 우리가 찾고자 하는 2의 거듭제곱 수 \(n\)의 비트표현을 살펴보면 한 자리만..
안녕하세요. 오늘은 피보나치 수열에 대해 다루어 보려고 합니다. 출처 : https://www.acmicpc.net/blog/view/28 피보나치 수열은 일반적으로 재귀형태로 구현을 많이 합니다.하지만 이런 방식은 n이 커질수록 시간이 기하급수적으로 오래걸립니다.그래서 좀 더 좋은 방식들에 대해 찾다보니 위의 링크에서 많은 정보를 얻었습니다.위 내용에 추가적으로 살을 붙여서 정리해 보겠습니다. Contents재귀형식재귀 + 저장(메모이제이션)을 이용한 방식for-loop를 이용한 방식피보나치 수의 나머지(피사노 주기)피보나치 관계식의 행렬표현+ 피보나치 수열의 합 재귀형식재귀형식은 모두 다 아시다시피 아래와 같이 구현됩니다.0, 1, 1, 2, 3, 5, 8, ... 이므로 n이 1보다 작으면 n을 아..
알고리즘 공부[6] 그래프 절단점과 SCC
안녕하세요. 오늘은 그래프의 절단점과 SCC(Strongly Connected Component)에 대해 알아보겠습니다. ContentsCut vertex(절단점 찾기)SCC(Strongly Connected Component)Kosaraju algorithmTarjan algorithm Cut Vertex(절단점)그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다.이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다.느낌상에는 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다.그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니..
안녕하세요. 오늘은 그래프의 간선에 대한 내용과 싸이클 검출 방법에 대해 알아보겠습니다. Contents 간선의 분류 싸이클 존재 여부의 확인 간선의 분류간선 구분에 대한 정확한 정의를 살펴봅시다. DFS를 수행할 때 방문하는 간선들을 모아 만든 tree를 DFS spanning tree라고 합니다. 아래와 같은 그래프가 있고, DFS를 1번 정점으로 부터 정점 번호가 작은 순으로 선택한다고 합시다. 그렇다면 DFS Spanning tree는 아래 그림에서 실선에 해당하는 트리를 말합니다. (Root는 1번 정점이 되겠죠) 여기서 실선으로 이루어진, DFS spanning tree를 이루는 간선을 tree edge(트리 간선)이라고 합니다. forward edge(순방향 간선)이란 트리간선이 아닌데, 트..
알고리즘 공부[4] 한붓그리기(Eulerian circuit)
안녕하세요. 오늘은 한붓그리기, 오일러 서킷이라 부르는 문제들에 대해 다루어 보겠습니다. ContentsEulerian cirtuit(오일러 서킷)Eulerian trail(오일러 트레일) Eulerian Circuit(오일러 서킷)오일러 서킷이라는 것은 우리들에게 한붓그리기 문제로 더 알려져 있습니다. 오일러 서킷그래프가 주어졌을 때 그래프의 한 시작점으로부터 모든 간선을 한번씩만 지나 다시 시작점으로 돌아오는 경로를 말합니다.이러한 경로가 있으려면 어떠한 조건을 만족해야 할까요?가장 많이 사용되고 있는 방법으로는 단순하게 정점의 degree를 사용하는 것입니다.degree라는 것은 위상정렬 할 때 잠시 살펴보았죠? 그 때는 indegree를 이용하였고, 여기서 degree라는 것은 정점에 연결되어 있..
알고리즘 공부[3] Topological sort(위상정렬) (C++)
안녕하세요. 오늘은 그래프를 활용한 문제에서 등장하는 위상정렬에 대해서 알아보겠습니다. ContentsDAG(Directed Acyclic graph)Topological sort란?위상정렬의 구현방식(1)-indegree위상정렬의 구현방식(2)-DFS DAG(Directed Acyclic Graph)우선 위상정렬을 공부하기 전에 DAG에 대해서 알아봅시다. Directed Acyclic graph란 말 그대로 간선에 방향이 있고, 싸이클이 없는 그래프를 말합니다.Directed Graph에서 방향을 가지고 있는 간선들의 sequence에 대해 시작점과 끝점이 같아지는 sequence가 있다면 싸이클이 있다고 합니다. DAG는 이런 싸이클이 없는 유향그래프이죠.이전의 그래프의 정의와 함께 말씀드렸듯 DA..
알고리즘 공부[2] DFS(깊이 우선 탐색) (C++)
안녕하세요. 오늘은 그래프에 대해서 가장 많이 등장하는 DFS에 관하여 알아보겠습니다.DFS는 매년 여러 곳의 입사시험 및 프로그래밍 대회에서 등장합니다. ContentsDFS(Depth-First search)DFS구현(1) RecursiveDFS구현(2) StackDFS의 time complexity DFS(Depth-First Search)DFS란 무엇일까요? 한국말로 해석해보면 깊이 우선 탐색이라는 말이 됩니다. 그래프에서 특정 정점을 찾을 때 그래프의 깊이를 우선적으로 탐색한다는 말이죠. 이렇게 말하면 솔직히 감이 잘 안옵니다.예를 봅시다! https://steemitimages.com/0x0/https://janav.files.wordpress.com/2014/01/dfs-bfs-differe..