BFS (너비 우선 탐색) 트리나 그래프를 탐색하는 방법으로 시작 정점에서 가장 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. BFS를 구현할 때는 Queue를 활용하는데 왜 Queue를 쓰는지 아래의 과정을 통해 알아보자. BFS 탐색 과정 1. 루트 노트 방문 2. 큐에서 A를 제거 후 방문 처리, 다음 인접 노드들 큐에 삽입 3. queue 에서 요소 하나 pop(B) 후 방문 처리, B의 인접 노드 큐에 삽입 4. queue 에서 요소 하나 pop(C) 후 방문 처리, C의 인접 노드 큐에 삽입 5. queue 에서 요소 하나 pop(D) 후 방문 처리, D의 인접 노드 큐에 삽입 6. queue에서 남아있는 요소들을 위와 같은 방법으로 방문 및 표시하면서 큐가 완전히..
순차 탐색 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 데이터 크기에 따라 효율이 다르기 때문에 데이터가 많다면 비효율적인 방법 최악 : O(n) 이진 탐색 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는다 분할 정복 알고리즘 - 리스트 개수 0,1개일 때 처리하고 2개 이상일 때 재귀 호출로 구현 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료 (mid=key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key) 중간 값보다 검색 값이 작다면 중간값 기준 배열의..
재귀호출 함수안에서 동일한 함수를 호출하는 방식 시간복잡도 : O(n) 스택 기반 방식 동적계획법, 분할 정복 DP : 입력 크기가 작은 부분 문제들을 해결후 memoization 기법을 사용해 보다 큰 크기의 문제를 해결, 상향식 분할 정복 : 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘, 하향식 공통점 : 문제를 잘게 쪼갬 차이점 : 동적 : 상위 문제 해결시 재활용, 부분 문제 중복 분할 : 부분 문제를 서로 중복되지 않음 재귀호출은 계속 계산하지만 DP는 이전 계산한 값을 저장하기 때문에 계속 쓸 수 있다. 시간복잡도 비교적 나아진다. 대신 공간 복잡도는 희생된다
배경 Spring을 공부하고 있다면 어쩔 수 없이 마주치는 것이 .yml과. properties이다. 겉으로 보기엔 별 차이가 없어 보여서 도대체 무슨 차이가 있는 건지 궁금해서 찾아해보았다. 개념 먼저 둘의 공통점을 말하자면 포트, 데이터베이스 연결 정보 등의 프로그램이 실행되는데 필요한 구성 속성을 갖고 있는 파일이다. 이것을 사용하는 이유는 타 시스템과 연동할 때 생기는 문제를 방지하기 위해서이다. 개인마다 변수명을 정하거나 메서드를 만드는 것처럼 데이터를 표현하는 방식은 다르기 때문에 이러한 서로 다른 방식들을 통일시키고 관리하기 쉽게 그리고 가독성을 높이기 위해 사용한다. 차이 YAML(.yml) .properties 스펙을 찾을 수 있다(링크) 자체적으로 스펙을 알 수 있는 사이트가 없다. 그..
개념 Spring Cloud Eureka는 Client-Side Service Discovery라고도 부른다. 이는 호스트, 포트 하드코딩 없이 서비스가 서로를 찾고 통신할 수 있으며 서비스들의 로드 밸런싱, 장애 조치에 도움을 주는 미들웨어이다. 기본적으로 서버-클라이언트 구조로 서버는 서비스들의 가용성을 등록하는 레지스트리이다. 이때 레지스트리란 서비스 연결 정보를 말한다. 서버에 등록될 때는 서비스 ID, URL이 등록되며 서비스는 서비스 ID를 통해 접근 가능하다. 기본적인 흐름은 아래와 같다. Eureka Client 서비스가 시작되면 Eureka Server에 정보가 등록된다 Eureka Client는 Server로부터 다른 Client의 레지스트리를 받아 저장한다. 30초마다 Server로부..
배경 그동안 스프링 부트 프로젝트 생성 시 패키지 생성 부분에서 무작정 Jar를 선택해왔다. 갑자기 가만 보니 저 둘은 무슨 차이가 있는지 잘 모르고 있다는 것을 알았다. 그래서 각 용어의 개념들을 보고 Spring Boot 기반의 프로젝트는 어떤 걸 선택하는지 알아보겠다. 개념 JAR(Java ARchive, 자바 아카이브) 여러 개의 자바 클래스 파일과 클래스들이 이용하는 관련 리소스(텍스트, 그림 등) 및 메타데이터를 하나의 파일로 모아서 자바 플랫폼에 응용 소프트웨어나 라이브러리를 배포하기 위한 소프트웨어 패키지 파일 포맷 데스크톱 애플리케이션에서 구동 WAR(Web application ARchive, 웹 애플리케이션 아카이브) JSP, Servlet, Class, XML, 태그 라이브러리, 정..
배경 사내 업무 중 테이블 여러 개 join 후 SELECT를 하여 특정 테이블에 insert 해야 하는 상황이 나왔는데 이때 중복된 데이터 즉 이미 들어가 있는 데이터는 중복처리를 해야 하는 상황이 왔다. 해당 테이블에 PK가 데이터를 구분할 PK는 아니였기 때문에 관련 정보를 찾아봤다. 방법 index 설정 먼저 index를 설정하여 중복을 피하는 방법인데 PK를 설정하거나 UNIQUE INDEX를 설정한다. ALTER TABLE TableName ADD PRIMARY KEY (Column Name..) ALTER TABLE TableName ADD UNIQUE INDEX (Column Name..) ignore 말그대로 중복된다면 무시한다. 즉 insert를 하지 않는다. 이때 중복을 구분하려는 칼..
시간복잡도 : 얼마나 빠른지 - 핵심 공간복잡도 : 얼마나 많은 공간이 필요한지 파라미터 n 에 따라 계산 시간과 공간은 반비례 공간복잡도 - 빅데이터를 다룰 때 고려 - 고정 : 코드 저장 구간 - 가변 : 실행 중 동적으로 필요한 공간 스왑시 collections.swap 활용 버블정렬 - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 - 오름차순으로 1회전시 가장 큰 수가 가장 오른쪽에 - for 진행 끝날때마다 n번 계산 줄이기 선택정렬 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 정하는 알고리즘 - 기준값 하나 반복하며 기준값을 제외하고 가장 작은 수를 찾아 교환 - 1회전을 수행하고 나면 가장 작은 값의 자료가 맨앞에 삽입정렬 - 자료 배열의 모든 요소를 앞에서..
