컴퓨터 프로그래밍(암호학, 알고리즘)

BFS(Breadth First Search)는, Edge들을 따라 순회하는 순서가, 바로 밑 자손들을 전부 훑고 난 후, 그 다음 자손들을 훑는 순으로, Graph의 Edge를 따라 순회하는 알고리즘을 말한다. 여기서 유의할 것은, (DFS도 마찬가지지만) BFS라는 것이 'Search'라는 단어가 있어서 목표로하는 버텍스나 엣지를 찾는 ..

문제 출처: https://algospot.com/judge/problem/read/WORDCHAIN 문제: 단어들이 주어질 때, 끝말 잇기 순서대로 나열하시오. 불가능하다면 IMPOSSIBLE 출력 예를들어, dog god dragon need 가 주어졌을 때, 끝말 잇기 가능한 순서는 dog god dragon need 풀이: 모든 알파벳을 정점으로 두고, 두 정점간의 관계를 단어의 ..

오일러 서킷은, 그래프상의 모든 간선(Edge)을 한 번씩만 지나서 시작점으로 돌아오는 경로를 말한다. 흔히, 한 붓그리기로 알려져 있는 것이다. (위키 참조: https://en.wikipedia.org/wiki/Eulerian_path) 위 그림을 보면, 1-2-4-3-4-6-5-3-1 의 경로가 오일러 서킷이 된다. 오일러서킷을 구하는 방법은 다음..

점들간에 순서 의존성이 있을 때, 이 의존성을 고려해서 정렬하는 것은 위상정렬(topological sorting)이라고 한다. 예를 들어, 5명 애들에 대해 두 명씩 키를 비교한 자료가 다음과 같다고 하자. A > B B > C C > D D > E 이러한 자료를 근거로해서 키 순서대로 정렬한다면 A > B > C > D &g..

그래프에서는 크게 두 가지 탐색법이 존재한다. 깊이우선과 너비우선 (DFS and WFS) 탐색의 목적은 '어떤 Vertex가 있을까?'하는 'Find'가 아닌, 그래프내에서 모든 Vertex를 Edge를 따라서 '순회'하는데 있다. 즉, 빠짐없이 순회하면서 그 Vertex와 Edge로부터 정보를 얻어서 무언가를 하는데 그 목적이..

기본 구성 점(Vertex)과 간선(Edge)으로 구성 됨 ( Point와 Line이 더 편한 영어표현이나, 알고리즘 책에서 더 많이 쓰는 단어표현이 Vertex, Edge) 그래프의 정의 G(V,E) 표현 방법 3가지 표현 방법: 리스트, 행렬, 위치 1)리스트 vector<list<int>> adj; //혹은 vector<vector<int>> adj; 희소(sparse) ..

소수를 구하는 에라토스테스 체를, 비트단위로 저장하면, 메모리를 절약할 수 있다. (1/8로 줄어듬) 즉, 각 숫자 단위로 한 개의 bool 값을 지정하는 것이 아니고, 비트 1개를 써서 합성수인지 소수인지 가리키게 하는 것. 1바이트면 8비트이기에 8개의 수에 대해 지정 가능.(1~8) 따라서, int로 ..

비트로 표현해서 풀면 편한 문제들이 많다. 이 페이지에서는 비트관련된 유용한 연산들을 소개한다. 비트 연산자들 a & b :and -> a & 7 = a % 8 a | b :or a ^ b :xor -> a ^ 0 = a ~a : not a << b : a를 b만큼 left shift a >> b : a를 b만큼 right shift 비트를 이용한 집합의 표현 꽉 찬 집합을 표현하는 ..

C++관련해서, 알고리즘 문제풀이를 위해 꼭 필요한 부분만을 살펴보자. include 다음과 같은 헤더들을 포함시키는 것을 외워둬야 한다. <stdio.h> //printf, scanf, freopen 함수를 사용하려면, 이 헤더파일을 include해야 함 <iostream> //cin, cout <vector> //vector 클래스 <algorithm> //min, max 함..

이 페이지에서는 Visual Studio 2013을 이용해서 알고리즘 프로그래밍을 하기위해 필요한 설정들에 대해서 다룬다. 다운로드 무료로 사용가능한 Visual Studio Express for Desktop을 다운받아 사용하면 된다. https://www.visualstudio.com/en-us/downloads/download-visual-studio-vs.aspx (설치 시 특이사항 없기에 별도 설..