[알고리즘] 알고리즘의 개념과 기본 자료구조 1. 알고리즘의 정의와 조건 1) 알고리즘의 정의 주어진 문제를 풀기 위한 명령어들의 단계적 나열 2) 알고리즘의 조건 입력 : 0개 이상의 외부 입력 출력 : 1개 이상의 출력 명확성 : 각 명령은 모호하지 않고 명확해야 함 유한성 : 한정된 수의 단계를 거쳐 반드시 종료됨 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함 알고리즘의 조건을 합쳐서 정의하자면 알고리즘이란 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이다. 2. 알고리즘 생성 단계 3. 알고리즘의 표현/기술 방법 알고리즘은 크게 일상 언어, 의사 코드(Pseudo code), 순서도의 세 가지 방법으로 표현할 수 있..

Minimum Spanning Tree(MST) 문제는 그래프에서 모든 정점을 연결해주는 최소 간선의 집합 중 가중치의 합이 가장 작은 간선의 집합을 찾는 문제입니다. MST를 구하는 방법은 크게 2가지가 있습니다. Prim algorithm과 Kruskal algorithm이죠. Prim과 Kruskal의 기본적인 아이디어는 다음과 같습니다. Prim algorithm은 각 정점을 방문하며 그 정점에 연결된 가장 가중치가 작은 간선들을 선택하여 MST를 구합니다. Kruskal algorithm은 각 간선들을 탐색하여 가장 가중치가 작은 간선들을 택하면서 MST를 구합니다. 지금부터, 아래와 같은 그래프를 가지고 Prim algorithm과 Kruskal algorithm의 동작과정을 알아보고 각 알고..

Floyd-Warshall(플로이드-워샬 알고리즘)은 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘입니다. 시간 복잡도는 O(V^3)을 가지죠. 이 알고리즘은 음의 사이클이 없는 그래프에 대해서 모든 정점 사이의 최단거리를 구하는 것이 가능합니다. 그래프의 간선 중 음의 가중치가 존재해도 잘 실행되죠. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 됩니다. 이 2차원 배열을 이용하여 플로이드-워셜 알고리즘은 동적계획법으로 최적의 값을 계산합니다. 이 알고리즘의 기본 컨셉은 정점 i, j사이 모든 경유지를 탐색해서 그 중 최단 경로를 찾아내는 것입니다. 그래프의 정점이 1~V까지이면, 경유지 K는 이 모든 정점들을 경유지로 하는 경로를 탐색합니다. dp[i][j] = ..

Bellman-Ford(벨만포드) 알고리즘은 음수 가중치가 있는 그래프에서 특정 시작점 Vs에서 다른 나머지 정점(Vi, i=1, N)까지의 최단거리를 구할 수 있는 알고리즘입니다. 이 벨만포드 알고리즘을 그래프의 음수 사이클의 존재 여부도 알 수 있죠. 1. 음수 가중치가 있는 그래프에서 시작점에서 다른 정점까지의 최단거리를 구할 수 있다. 2. 음수 사이클 존재 여부를 알 수 있다. Bellman-Ford 알고리즘의 동작과정은 각 정점들을 차례로 돌아 가면서 해당 정점의 간선들을 탐색합니다, 단 맨 처음은 시작점부터 탐색합니다. 그리고 그 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작으면 업데이트합니다. 식으로 나타내면 다음과 같습니다. d[T]

LCS(Longest Common Subsequence)는 문자열 A,B가 있을 시, 가장 길이가 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이라는 것은 연속된 문자열이 아닌 부분 문자열을 뜻합니다. 예로들어, 'HAYOUNG'과 'AONG'이라는 문자열이 있을 시, 공통된 부분문자열은, {A}, {A,O}, {A,N}, {A,G}, .. ,{A,O.N,G} 가 있죠. 그리고 여기서 가장 긴 부분 문자열은 'AONG'입니다. LCS를 푸는 알고리즘은 Dynamic Programming을 이용하며 O(mn), (m = len(A), n = len(B)) 의 시간복잡도를 가지고 해결할 수 있습니다. 푸는 절차는 다음과 같습니다. 먼저, Dynamic Programming을 적용하기 위해 ..

알고리즘에서의 네트워크 유량(Network Flow) 문제는 그래프에서 각 노드들 간의 용량(Capacity)이 정의되어 있을 시, 시작점(source)에서 끝점(target)까지 흐를 수 있는 최대 유량을 구하는 문제입니다. 이 네트워크 유량 문제를 해결하는 일반적으로 많이 쓰이는 방안으로는 크게 두 가지가 있습니다. 첫 번째는 DFS로 구현하는 포드 폴커슨 알고리즘(Ford-Fulkerson Algorithm), 두 번재는 BFS로 구현하는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)이 있습니다. 여기서는 에드몬드 카프 알고리즘으로 네트워크 유량 문제를 푸는 방식과 구현 코드를 설명하도록 하겠습니다. 위와 같이 용량에 대한 정보가 명시된 그래프에서, 1(source)에서 7(si..

소수란 1과 자기 자신만으로 나눠 떨어지는 수를 말합니다. 그리고 그 소수를 구하는 가장 간단한 방식은 에라토스테네스의 체라는 알고리즘을 이용하는 것입니다. 알고리즘은 다음과 같습니다. 1. 0,1은 소수가 아님 2. 2는 소수임, 그리고 2의 배수가 되는 수들 (2,4,6,8,10,12 ...) 목록에서 제외 3. 3은 소수임, 그리고 3의 배수가 되는 수들 (9,15,21....) 목록에서 제외 *(6, 12, 18 ... 등은 이미 제외) 4. 4는 이미 제외됨 ... 다음은 이 알고리즘을 구현한 코드입니다. 각 숫자를 표현하는 데 있어서 비트마스크를 이용한 것과 2가지 최적화 방법이 적용되 있는 걸 눈여겨 보세요. 첫 번째 최적화는 어떤 N이 소수인지 판별하는 데 있어서 N까지의 모든 수를 따지는..

비트마스크는 정수의 이진수 표현을 자료 구조로 쓰는 기법입니다. 비트마스크를 사용하는 코드는 다음과 같은 장점이 있죠. 1. 더 빠른 수행 시간 : 보통 O(1)에 실행됨 2. 더 간결한 코드 : 복잡한 코드를 한 줄에 작성 가능 3. 더 적은 메모리 사용량 : 예시로, 32개의 아이템의 유무를 나타내는 배열을 32bit 자료형으로 대체 가능 4. 연관 배열을 배열로 대체 : c++ 경우, map를 사용한다고 하면 이를 단순 int[] 배열로 대체 가능 만일 비트마스크로 코드를 작성 시, c++이나 java같은 자료형의 데이터 범위가 정해져 있는 언어에서는 오버플로우나 언더플로우에 주의해야합니다. bool is_bit_set(unsigned long long a, int b){ return ( a & (..

[알고리즘] 알고리즘 수행시간 유형 N 알고리즘 분석의 결과는 입력되는 자료의 수 N에 대하여 수행 시간을 함수 관계로 표현한 것이다. 1. 1 - 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘이다. 프로그램에서 대부분의 명령들은 한 번만 실행되거나, 단지 몇 번만 실행이 된다. 전체적인 프로그램이 이런 경우라면 실행 시간은 상수가 된다. 이 유형은 알고리즘의 설계시 도전해 볼 만한 것이다. 2. log N - 만약 입력 자료의 수에 따라 실행 시간이 log N의 관계를 만족한다면 N이 증가함에 따라 실행 시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다. log의 성질상 밑(base)의 값에 따라 결과는 달라지지만 그렇게 크..

기술 면접 대비 문제 대비 훈련법1. 직접 풀도록 노력해야합니다. 진실로 노력해야합니다. 많은 문제들은 까다롭게 만들어졌습니다. 문제를 풀때는 공간과 시간 효율에 대해서 반드시 생각해야 합니다. 공간효율을 희생해서 시간 효율을 높일 수 있는지, 아니면 반대로 할 수 있는지 자문해 보아야 합니다.2. 알고리즘 코드를 종이에 적어봅니다. 여러분은 아마 지금껏 컴퓨터 앞에서 코딩을 해왔을 것이고, 컴퓨터가 주는 편리함에 익숙해져 있을 것입니다. 하지만 면접을 보는 동안에는 문법 강조 기능이나 코드 완성, 컴파일링 기능이 갖추어진 도구의 도움을 받을 수 없습니다. 종이에 코딩하면서 같은 상황에 대비하여야 합니다.3. 코드를 테스트해봅니다. 역시 종이 위에. 일반적인 경우뿐 아니라, 기본 조건 그리고 오류 발생 ..