문제동전 N 개가 금액을 기준으로 오름차순으로 주어질때, K 금액을 만들 수 이있는 최소한의 동전 개수를 구한다. 동전은 중복될 수 있다.제약사항: (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000), 동전 금액은 (1 ≤ N_i ≤ 1,000,000)출처: https://www.acmicpc.net/problem/11047접근전형적인 그리디 알고리즘 문제이다. 핵심 아이디어는 동전이 동전의 금액 (N_i) 에 따라 오름차순으로 주어지므로 가장 큰 동전부터 K 에 몇개 들어가지는지 세는 것이다. 두가지 접근 방법이 있을것이다.(1) 덧셈을 이용하여 계산한다.(2) 나눗셈을 이용하여 계산한다. 덧셈을 이용하는 경우 최악의 경우 (N_i = 1, k = 100,000,000) 일때 총 연산횟수 10..

이전 글에서 SprinbBoot 3.3.4 코드를 분석할 순서를 정했다.spring-boot-autoconfigure:http 를 까보던중 SpringBoot 를 이용해 코드를 쓸때 직접적으로 사용하지 않았던 생소한 어노테이션들이 있어서 우선 이 어노테이션들을 정리한다. 그 목록은 다음과 같다.@AutoConfiguration@AutoConfigurationBefore, @AutoConfigurationAfter@ConditionalOnClass, @ConditionalOnMissingBean그리고 이렇게 공부한 내용이 실무에서는 어떤식으로 영향을 끼치고 있는지 살펴본다.어노테이션 살펴보기1. @AutoConfiguration설명이 어노테이션이은 해당 클래스가 클래스 스프링 부트 프레임워크에 의해 자동으..

문제9x9 스도쿠 판이 입력으로 주어지면 이 이 스도쿠 판을 다음의 규칙에 따라 완성해서 출력하는 문제이다. *(반드시 완성이 가능한 스도쿠만 입력으로 주어진다.)(1) 각각의 가로줄과 세로줄에 1부터 9까지의 숫자가 한번씩 나타나야한다.(2) 3x3 정사각형 안에도 1부터 9까지의 숫자가 한번씩 나타나야한다.접근이렇게 풀면 되지 않을까?(1) 판을 순회하면서 1 ~ 9 까지의 숫자가 해당 판에 가로조건, 세로조건, 3x3 조건을 충족하면 놓는다.(2) 그 다음으로 이동한다.(3) 만약 모든 숫자에 대해서 가로조건, 세로조건, 3x3 조건을 충족하지 못한다면 가능한 최소한의 경우의 수로 롤백한다. 그리고 이러한 문제 풀이는 백트래킹의 일종인 깊이우선 탐색을 통해 풀 수 있다. 풀이import java.i..

이분탐색은 아이디어는 쉬운데 구현에서 헷갈려서 글을 남겨놓는다.이분탐색 이란 이분 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 탐색 범위를 절반씩 줄여가며 원하는 값을 찾기 때문에, 시간 복잡도가 O(log n)으로 매우 효율적입니다.이분 탐색의 원리이분 탐색은 다음과 같은 절차로 진행된다.탐색 범위 설정: 시작점(left)과 끝점(right)을 지정하여 탐색 범위를 정한다.중간 값 계산: left와 right의 중간 인덱스(mid)를 계산한다.중간 값 비교:중간 값이 찾고자 하는 값(target)과 같으면 탐색을 종료한다.중간 값이 target보다 작으면 left = mid + 1로 탐색 범위를 중간 이후로 좁힌다.중간 값이 target보다..

아무래도 백트래킹 문제가 약한거 같아서 GTP 에게 문제를 좀 내달라고 했다.  쉬운 문제 2개는 부분 수열의합 문제와 모든 순열 출력하기를 내줬고, 이는 백준에서 풀었던 문제와 비슷해서 복습하는 개념으로 풀었다. 그리고 중간 나이도 문제로 N Queen 문제를 내줬다. 문제  해결하기 재귀 호출 설계재귀를 잘못 설계하면 Stackoverflow 에 빠질 수 있다. NQueen 경우의 수를 구하는 문제일 때 재귀 횟수를 줄이려면 다음과 같이 해야한다. (1) 하나의 기준을 정하고 순회한다.'각 퀸이 서로 공격할 수 없다.' 라는 조건에 따라 Row, Col 을 기준으로 하나의 queen 을 넣을 수 있나? 만 고려하면 되고 그렇게 되면 순회 횟수가 N*N 에서 N 으로 줄어든다. (2) 기준 에 따라 놓..

문제문제 링크: https://www.acmicpc.net/problem/15649 백준 알고리즘 단계별로 풀어보기를 하는 중이다.DP 및 백트래킹에서 다소 약한 모습을 보이는 중이므로 이러한 문제들 위주로 풀이를 기록하고자 한다. 접근문제를 다 풀고 다른 사람들의 풀이를 보니 깊이우선탐색을 통해 이 문제를 많이 푸는 것 같다.깊이 우선 탐색 (DFS)(1) 백트래킹의 일종으로(2) '각 node 를 순회할때 하나의 node 에 도달하면 간선을 통해 인접 노드를 계속 파고들고, 끝까지 간 뒤에 다시 첫 노드로 돌아와 같은 레벨의 노드로 옮겨가는 탐색 방법이다.' (3) 넓이 우선 탐색 (BFS) 과 자주 함께 소개된다. 말로하면 잘 이해가 안되지만 그림으로 보면 이해가 잘되더라   이 문제에서는 인접 숫..

왜 DB 테이블 파티셔닝을 도입했나프롭테크 회사에서 부동산 중개사들이 사용하는 솔루션, 내부 부동산 투자 개발팀이 사용하는 솔루션을 만들고 운영주입니다. 이러한 솔루션을 위해 부동산 공공데이터 베이스를 구축, 운영중인데 아직 경험이 부족하여 더 나은 서비스를 제공하기 위해 DB 에 대해 공부하고 있습니다. 고작  1+a 년동안 부동산 데이터를 다룬 제가 파악한 특성은 (1) 데이터 양(Volume)이 많다, (2) 그렇게 양이 많은 데이터가 다양하다는 점입니다.얼핏보면 빅데이터의 3V(Volume, Velocty,  Variety) 가 생각나는 특징이죠? 하지만 엄연히 말하자면 다릅니다. 양이 많은 것은 맞지만 TB 단위로 많은 것은 또 아니고, 다양하지만 데이터의 형태(정형, 반정형, 비정형) 가 다양..

프롭테크 회사를 다니다보니 지도 서비스를 자주 다룹니다.당연히 클라이언트 개발자가 지도 서비스를 더 많이 다루고 고생하는 분야이지만 필지, 행정동, 법정동의 모양정보(이하 공간데이터)를 뿌려주는 역할은 백엔드에서도 해야할 일이 있습니다. 백엔드 개발자라면 공간데이터 타입을 어떻게 DB 에 보관할지 궁금하는지, 내부 처리 성능은 어떠한지 궁금할 것입니다.이것 역시 다루고 싶은 주제지만 이 글에서는 공간데이터를 지도에 뿌리는 정도가 관심사이기 때문에 어떻게 보관하든 큰 문제는 아니겠죠.  Geometry 정보를 전달하는 방식그렇다면 DBMS 에 보관된 공간데이터를 어떤식으로 뿌릴까를 이야기해보겠습니다.여러 부동산 서비스의 클라이언트-서버 통신을 분석해보면 공간데이터를 뿌리는 방식은 크게 두가지로 나뉘는것 같..