Coding Diary

0. 도커를 왜 사용하게 되었나 맨 처음 프론트엔드와 백엔드로 나누어 프로젝트를 진행하려고 했을 때, 내가 백엔드로서 만든 api를 프론트엔드 개발자가 어떻게 사용해야 하는 것인가에 대해 엄청나게 궁금했던 적이 있다. 일단 팀원 모두 프엔 백엔 나누어서 개발하는 것이 처음이었고, 구글에 검색을 해 봐도 관련 지식이 아예 없다보니 뭔 솔? 이러면서 이해하기가 어려웠다. 그래도 지금은 대략적인 프로세스를 알게 되었다. 내가 인텔리제이로 만든 스프링 프로젝트를 프론트엔드 개발자의 노트북에서 실행하여 프론트엔드 개발자가 해당 api를 사용하면 되는 것이다. 물론, 백엔드 개발자는 cors 제한을 풀어놔야 하며, 데이터베이스는 동시에 접근 가능 하도록 ec2에 만들어 두거나 프론트엔드 노트북에 데이터베이스 설정을..

1. 개념 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 2. 특징 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제들이 반복되고, 작은 문제들의 결과값은 항상 같아야 한다. 작은 문제들은 한 번만 계산해 DP 테이블에 저장한다. 이후에 재사용할 때는 DP 테이블에 있는 것을 사용한다. 이는 메모이제이션 기법이다. 톱 다운 방식과 바텀 업 방식으로 구현 가능하다 3. 원리 피보나치 수열을 통해 원리를 알아보자. 피보나치 수열 공식: D[N] = D[N-1] + D[N-2] 1) 동적 계획법으로 풀 수 있는지 확인하기 피보나치 수열의 3번째 값은 1번째 값과 2번째 값의 합이다. 그리고 이는 수열이 진행되면서 반복된다. 즉 큰 ..

1. 개념 n개 중 r개를 선택하는 경우의 수를 뜻한다. 이때, 선택한 것들의 순서가 달라도 같은 것이라고 처리한다. 예를 들어 1 2 3 4 5 중 2개를 뽑았을 때 1 2 를 뽑은 것과 2 1 을 뽑은 것을 같은 것이라고 보는 것이다. 2. 공식 3. 점화식 1) 조합 공식보다 점화식을 사용하면 좋은 이유 조합 공식의 경우 팩토리얼 연산을 사용해야 하는데 큰 수의 경우 계산 비용이 높다. 팩토리얼 연산을 재귀로 구현할 경우 스택 오버 플로우 문제가 발생할 수 있다. 점화식을 사용하면 반복 계산을 피할 수 있다. 이전에 계산된 것을 동적 계획법의 방식으로 사용하기 때문에 계산 비용을 줄일 수 있고 더 효율적으로 접근할 수 있다. 2) 점화식 개념 점화식을 세울 때는 모든 부분 문제가 해결된 상황이라고 ..

1. 개념 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상이라고 한다. 2. 원리 1) 일반적인 최소 공통 조상 구하기 4번과 15번 노드의 최소 공통 조상을 구한다고 가정. 루트 노드에서 탐색을 시작해 4번의 부모 노드와 깊이를 저장, 루트 노드에서 탐색을 시작해 15번의 부모 노드와 깊이를 저장 선택된 두 노드의 깊이가 같은 경우 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복 - 1 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 올려서 같은 깊이로 맞추기 그리고 1을 진행 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다..

1. 개념 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리이다. 2. 종류 1) 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진트리 이렇게 저장된 이진 트리는 탐색 속도가 저하되고 공간이 많이 낭비된다 2) 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리 3) 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리 4) 이진 탐색 트리 루트보다 작은 값은 왼쪽에 위치, 루트보다 큰 값은 오른쪽에 위치하도록 하여 노드를 저장 데이터를 효율적으로 저장하고 검색, 삭제할 수 있다. 3. 트리의 노드와 배열 인덱스의 상관관계 루트 노드 인덱스 = 1 부모 노드 인덱스 = 현재 노드 인덱스 / 2 (현재 노드가 루트가 아니..

1. 개념 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조. 각 노드는 문자 혹은 문자열의 한 글자를 나타낸다. 또한, 각 노드는 자식을 가지고 있을 수 있는데, 이는 각 노드의 다음 문자를 나타낸다. 2. 특징 루트 노드는 항상 공백이다. N진 트리의 형식을 가진다. 문자 종류에 따라 N이 결정된다. 알파벳은 26개의 문자로 이루어져 있기 때문에 26진 트리 형태를 갖게 된다. 즉 부모 노드가 자식을 최대 26개까지 가질 수 있다는 것이다. 각 문자의 접두사를 공유하기 때문에 검색이 빠르다. 트리 형태로 문자를 저장하기 때문에 삽입과 삭제 연산이 빠르다. 조건을 만족한다면 상수시간 안에도 가능하다. 3. 구현 // 트라이에서 사용하는 노드 정의 class tNode{ tNode[] ..

1. 개념 노드와 에지로 연결된 그래프의 특수한 형태. 2. 특징 순환 구조를 가지고 있지 않다. 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리도 트리의 모든 특징을 따른다. 3. 트리의 구성 요소 1) 루트 노드 2) 부모 노드 3) 자식 노드 4) 에지 5) 리프 노드 6) 서브 트리 4. 구현 1) 그래프 이용 그래프 구현을 이용해서 구현하면 된다. 인접 리스트 사용. 동적으로 크기 조정이 가능하다. 연결리스트로 구현되기 때문에 노드의 삽입과 삭제가 쉽다. 특정 위치의 노드에 접근하기 위해서 연결리스트를 순회해야 해서 접근 시간이 오래 걸린다. 다음 노드를 가리키는 정보를 저장해야 해서 메모리 사용량이 증가할 수 있다. adjList = ..

0. 왜 카카오페이 api를 사용하게 되었나? 현재 진행하고 있는 프로젝트에서 상품을 주문한 후 결제하는 기능이 필요했다. 실제로 결제가 되는 과정을 거치면서, 사용자들이 편하게 결제할 수 있는 방법에는 뭐가 있을까 생각하다 api를 가져다 쓰면 좋겠다는 생각이 들었고, 주위에서 사용빈도가 높은 카카오페이 api를 사용하면 사용자들이 편하게 결제를 진행할 수 있겠다는 생각을 하게 되었다. 그래서 카카오페이 api를 프로젝트에 적용해보고자 하였다. 아래는 카카오페이 api를 스프링 및 스프링부트에서 사용하기 위한 방법이다. 흐름 정리 프론트엔드가 백엔드에게 결제 정보를 담은 후 api1를 요청한다. 그러면 백엔드는 api1에 대한 처리로 카카오페이 서버에게 결제를 하고 싶다는 요청을 보내고 응답으로 결제를..

1. 개념 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 2. 특징 사이클은 없어야 한다. 사이클이 있으면 가중치의 합이 최소가 될 수 없기 때문이다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. 에지 리스트의 형태로 구현하는 것이 간단하다. 3. 종류 1) 크루스칼 모든 에지를 가중치 기준으로 오름차순으로 정렬한 후, 가중치가 작은 간선부터 선택하면서 사이클을 형성하지 않도록 하여 최소 신장 트리를 만든다. 2) 프림 시작 노드부터 출발하여 가장 가까운 노드를 선택하며, 해당 노드와 연결된 에지 중 가장 가중치가 작은 간선을 선택하는 방식으로 최소 신장 트리를 만든다. 4. 크루스칼 1) 원리 에지 리스트를 생성한다. 에지 리..

1. 개념 그래프 상에 있는 모든 경로의 최단 경로를 구할 수 있는 알고리즘이다. 즉, 노드 1 2 3 4 5 가 있을 때, 노드 1과 노드 2사이의 최단 경로, 노드 1과 노드 3 사이의 최단 경로....노드 4와 노드 5 사이의 최다 경로를 모두 구할 수 있다. 출발 노드로부터 각 노드까지의 최단 경로를 구하는 다익스트라나 벨만포드 알고리즘과는 살짝 다르다. 2. 특징 모든 노드 간의 최단 경로를 탐색할 수 있다. 음수 가중치 에지가 있어도 수행할 수 있다. 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간 복잡도가 O(V3)이다. V는 노드의 수. 인접 행렬을 이용하면 구현이 간단하다. 3. 원리 동적 계획법의 원리 시작 노드부터 도착 노드까지의 최단 경로는 시작 노드부터 중간 노드까지의 최단..