![]()
암호화 알고리즘암호화 알고리즘은 말 그대로 어떤 데이터를 특정 알고리즘을 사용하여 암호화시켜 보안을 높이는 것으로 개발을 공부하면서 중요하다고 생각되는 부분이다.요즘 거의 대부분의 업무나 연락은 PC 혹은 스마트폰으로 처리하게 된다. 중요하지 않은 내용도 주고받지만 공개되서는 안 되는 중요한 내용이나 문서, 파일 등을 다른 사람이나 시스템으로 보내는 일이 자주 생기게 된다.이때 필요한 것이 데이터 암호화로 악의적인 목적을 가진 사람이 정보를 탈취하거나 몰래 훔쳐보는 등의 공격을 방지할 수 있게 해 준다.본격적인 암호화 알고리즘에 대해서 알아보기 전에 간단히 용어를 먼저 살펴보고 정리해 보자.평문(Plaintext): 평문은 해독이 가능한 형태의 데이터 즉, 암호화를 하기 전 원본 데이터를 의미한다.키(K..
완전 탐색 알고리즘완전 탐색 알고리즘은 모든 경우의 수를 시도하는 기법으로 가장 기본적이고 간단한 유형의 알고리즘이다.될 수 있는 모든 조건 혹은 모든 조합을 다 대입해보며 해답을 찾는 알고리즘이다.모든 경우의 수를 전부 탐색하기 때문에 100% 정확성을 보장하지만 반대로 높은 시간 복잡도를 가진다. 완전 탐색 알고리즘에는 선형 구조와 비선형 구조로 나눌 수 있다.선형 구조브루트 포스모든 경우의 수를 다 검사하여 원하는 값을 탐색하는 방법경우의 수가 적을 때 사용하는 것이 좋다.비트마스크이진수의 비트 연산을 통해 경우의 수를 줄여가며 탐색하는 방법비트 마스크를 사용하여 하나의 변수에 여러 개의 상태 정보를 저장할 수 있으며 이를 통해 복잡한 조건문을 간단하게 처리할 수 있다. 경우의 수가 많을 경우에 유..
알고리즘알고리즘을 공부하면 정말 여러 가지 알고리즘이 있다는 것을 느끼게 된다.나 또한 최근에 계속 알고리즘을 공부하며 코테 문제를 풀고 있는데 하면 할수록 알고리즘의 본래 목적과 멀어지고 그냥 문제를 푸는 용도로만 쓰고 있었다.코테 문제를 푸는 것도 중요하지만 그보다 알고리즘을 왜 사용하고, 배워야되는지가 더 중요하다고 생각했다. 알고리즘이란 뭘까?알고리즘의 사전적 정의를 먼저 보면 아래와 같다.알고리즘은 어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는 명확하게 정의된 계산 절차사전적 정의를 보면 코딩 테스트에서 사용하는 알고리즘이랑 의미가 같다고 생각할 수 있다.하지만 잘 생각해보면 어떤 웹 서비스를 개발한다고 했을 때 API 호출을 통해서 어떤 요청이 들어오고 DB..
![]()
우선순위 큐(Priority Queue) 우선순위 큐는 우선순위에 따라 값을 정렬하는 큐의 유형이다. 우선순위 큐 생성하기 PriorityQueue queue = new PriorityQueue(); PriorityQueue queue = new PriorityQueue(Collections.reverseOrder()); PriorityQueue를 생성하는 것을 살펴보면 두 가지 경우가 있다. 첫 번째로 우선순위 큐를 기본으로 생성하게 되면 우선순위가 낮은 값이 Queue의 맨 앞에 위치하게 된다. 두 번째로 Collections 클래스에 reverseOrder() 메서드를 사용하면 우선순위가 높은 값부터 맨 앞에 위치하게 된다는 차이가 있다. 우선순위 큐에 데이터 삽입하기 queue.add(1); qu..
그리디(Greedy)그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.장기적인 결과보다 즉각적인 이익을 우선시하여 미래의 영향을 고려하지 않고 현재 상황을 기반으로 결정을 내린다.그리디 알고리즘을 사용하면서 조심해야 될 부분은 그리디 알고리즘은 항상 최적의 해를 보장하지 않는다는 것이다.그리디 알고리즘을 사용할 때 잘 따져보지 않으면 반례가 생길 수 있으니 조심해서 접근해야 된다.그리디 알고리즘을 적용하기 위해서는 두 가지 조건이 성립해야 한다. 1. 탐욕 선택 조건그리디 알고리즘을 적용하기 위해서는 탐욕적인 선택 즉, 선택지 중에서 최선의 선택을 했을 경우 전체 문제의 최적해를 반드시 도출할 수 있어야 한다. 2. 최적 부분 구조 조..
![]()
이진 탐색(Binary Search)이진 탐색은 정렬된 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.시간 복잡도는 O(logN)으로 빠른 시간 복잡도를 가진다.이진 탐색 알고리즘을 적용하기 위해서는 데이터가 정렬되어 있어야 하고 데이터 구조의 모든 요소에 액세스 하려면 일정한 시간이 걸리게 된다. 이진 탐색 과정(오름차순 기준)1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값과 타깃 데이터를 비교하여 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.현재 타깃 데이터는 50, 중앙값은 37로 서로 비교해보면 타깃 데이터가 더 크기 때문에 왼쪽 데이터셋은 선택하..
![]()
세그먼트 트리(Segment Tree)세그먼트 트리는 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태가 바로 세그먼트 트리다.세그먼트 트리를 사용하는 이유는 구간 합을 할 때 데이터 업데이트가 느리기 때문이다.구간 합을 통해 만들어진 합 배열에서 중간에 데이터가 바뀌는 순간 기존 데이터와 바뀌는 데이터의 차이 만큼 바뀌는 데이터 뒤에 위치한 값들에게 모두 더해줘야 하는 문제가 생긴다. 이러한 업데이트 시 시간이 오래걸린다는 문제점을 세그먼트 트리로 해결할 수 있다. 세그먼트 트리 핵심 이론1. 트리 초기화 하기리프 노드의 개수가 데이터의 개수 이상이 되도록 트리 배열로 만든다.샘플 데이터로 {5, 8, 4, 3, 7, 2, 1, 6}이 주어진다면 먼저 트리의 크..
![]()
최소 공통 조상(LCA, Lowest Common Ancestor)최소 공통 조상은 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 뜻한다.일반적으로 구하는 방법과 빠르게 구하는 방법이 있다. 일반적인 최소 공통 조상 구하기먼저 일반적인 최소 공통 조상 구하기를 사용하려면 트리의 높이가 크지 않은지 판단해야 한다.최소 공통 조상은 트리의 높이가 시간 복잡도에 많은 영향을 주기 때문에 트리의 높이가 높지 않은 경우에 사용한다.예시로 4번 노드와 15번 노드의 공통 조상을 찾는다고 해보자먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장해야 한다. 여기서 트리라는 특징을 잘 활용하면..
![]()
동적 계획법(DP, Dynamic Programming)동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 동적 계획법의 원리와 구현 방식1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용한다. 이를 메모이제이션(Memoization) 기법이라고 하고, 시간 복잡도 측면에서 유리하다.4. 동적 계획법은 탑-다운 방식과, 바텀-업 방식으로 구현할 수 있다. 아래의 핵심 이론은 동적 계획법의 기초적인 예제인 피보나치 수열로 설명..
![]()
조합(Combination)조합은 코딩 테스트에 자주 출제되는 주제이며 동적 계획법(DP)을 이해하는데 기초가 되는 부분이다.조합 점화식 도출 방법에 대해 깊이 학습하면 조합은 물론 동적 계획법의 점화식 도출 부분에 많은 도움이 된다.조합과 비슷한 순열을 비교하면 조합은 순서를 고려하지 않고, 순열은 순서를 고려한다는 부분이 다르다.위 사진과 같이 순열은 순서를 고려하기 때문에 1,2,3과 3,2,1을 각각 다른 것으로 구분하지만, 조합은 순서를 고려하지 않기 때문에 두개 다 같은 것으로 생각한다.왼쪽은 순열의 수학적 공식, 오른쪽은 조합의 수학적 공식이다. 다른 점으로는 조합은 순서를 고려하지 않기 때문에 r!를 추가하여 순서가 다를 경우의 수를 제거해준다.조합의 공식을 살펴보면 n개의 숫자에서 r개를..
![]()
최소 신장 트리(MST, Minimum Spanning Tree)그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리다.MST를 사용하는 대표적인 알고리즘으로 크루스칼, 프림 알고리즘이 있다. MST 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구헝하는 에지의 개수는 항상 N - 1개다. 아래의 예제는 크루스칼 알고리즘을 기준으로 한다.MST 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기MST는 데이터를 노드가 아닌 에지를 중심으로 저장하기 때문에 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.유니온 파인드를 사용하는 이유는 사이클이 발생하면 안되기 때문에 사이클..
![]()
플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘 중 하나로 다른 최단 거리를 구하는 알고리즘과 차이는 모든 노드 간에 최단 경로를 탐색한다는 것이다.음수 가중치 에지가 있어도 수행할 수 있지만 음수 사이클이 있으면 안 된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V³) 으로 느린 편에 속하기 때문에 주어진 노드가 적을 경우에 사용한다. 플로이드-워셜의 핵심 이론A 노드에서 B 노그까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 결국 최단 경로는 각 노드간 최단 경로가 합쳐졌다는 것을 의미한다.플로이드-워셜 점화식: D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E..
![]()
벨만 포드(Bellman-Ford)그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.특정 출발 노에서 다른 모든 노드까지의 최단 경로를 탐색한다.다익스트라와 비슷하지만 다른 점은 벨만 포드 알고리즘은 음수 가중치 에지가 있어도 수행할 수 있다는 점이다.따라서, 벨만 포드 알고리즘은 최단 경로를 구하는 문제 보다는 전체 그래프에서 음수 사이클의 존재 여부를 판단하는 문제로 출제된다.시간 복잡도는 O(VE) V: 노드 수, E: 에지 수벨만 포드 핵심 원리1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기벨만-포드 알고리즘은 에지를 중심으로 동작하므로 에지 리스트로 구현한다.최단 경로 리스트(정답 리스트)에서 출발 노드는 0, 나머지는 무한대로 초기화한다. (출발 노드는 무한대가 되면 안된다..
![]()
다익스트라(Dijkstar)그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.시간 복잡도는 O(ElogV) E: 에지 수, V: 노드 수에지는 모두 양수로 이루어져 있어야 되며 출발 노드와 모든 노드 간의 최단 거리를 탐색한다. 다익스트라 알고리즘의 핵심 이론1. 인접 리스트로 그래프 구현하기인접 행렬보다 인접 리스트로 구현하여 탐색하는 시간을 줄여야 한다.2. 최단 거리 배열 초기화 하기최단 거리 배열을 초기화 하고 1은 가중치가 없기 때문에 0으로 초기화한다.컴퓨터는 무한대가 없기 때문에 큰 수로 지정해서 초기화 해준다. (예시는 편하게 무한대로 처리)3. 값이 가장 작은 노드 고르기가중치가 없어 0의 값을 가지는 1번 노드를 선택하여 해당 노드가 가리키는 다른 노드를 탐색하고 최단 거리를 구한다...
![]()
위상 정렬위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.시간 복잡도 - O(V + E) V: 노드 수, E: 에지 수위상 정렬은 노드 간의 순서를 결정해준다.※ 항상 유일한 값으로 정렬되지 않는다. 즉, 정답이 여러 개 일수도 있다.위상 정렬의 핵심 이론1. 인접 리스트를 만들고 진입 차수를 초기화해준다.2. 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.3. 노드가 가리키는 노드들의 진입 차수를 1씩 빼준다.※ 진입 차수(자기 자신을 가리키는 에지의 개수)
