성장하는 서버 개발자 도라프의 블로그 성장하는 서버 개발자 도라프의 블로그

DFS : 깊이 우선 탐색 그래프 전체를 탐색하는 방법 중 하나. 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법. 스택이나 재귀함수를 사용하여 구현(코딩테스트에서는 보통 재귀를 사용) 재귀함수로 사용하여도 시스템 스택에 쌓이게 되므로 스택이라고 생각할 수 있다. 시작 정점의 한 방향으로 갈 수 있는 곳 까지 깊이 탐색한다.(가면서 지나가는 것들을 하나씩 담는다) 가다가 더 이상 갈 곳이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다. 다른 방향의 정점으로 탐색을 계속 반복하며 결국 모든 정점을 방문한다. 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야하므로 후입 선출 구조의 스택을 사용한다. 알고리즘 시작..

.DS_Store 파일의 정체 DS_STORE 파일이란 Desktop Services Store의 약자로 애플에서 정의한 파일 포맷이다. 애플의 맥 OS X 시스템이 finder로 폴더에 접근할 때 자동으로 생기는 파일로 해당 폴더에 대한 메타데이터를 저장하는 파일이다. 윈도우의 thumb.db 파일과 비슷하다. 분석해보면 해당 디렉토리 크기, 아이콘의 위치, 폴더의 배경에 대한 정보들을 얻을 수 있다. 맥 OS 환경에서만 생성 및 사용되지만, 파일을 공유하는 과정에서 이 파일도 같이 공유되는 경우가 있다. DS_store 파일은 프로젝트와 관련없는 파일이며, git status를 사용했을 때 발견되는 파일이니, github로 넘기지말고 삭제해도 된다. .DS_Store 삭제 방법 저장소 상위 디렉토리에..

11. DSL 만들기 DSL은 영역 특화 언어(Domain-Specific Language)를 의미한다. 즉, 특정 도메인에 특화된 언어이다. "문제 영역의 해결에는 그 영역의 언어를 전제로 둬야하며, 거기에서 프로그래밍 솔루션을 꺼내는 것이 중요하다" 라고 말한 Dave Thomas가 한 말을 생각하면 이해하기 쉽다. 특정 언어의 문제 해결에는 그 영역에 맞는 특화된 도구를 사용하자라는 것이다. 아래에 DSL에 대해 더 자세히 나오니 지금은 이정도만 알고 넘어가자. 코틀린의 DSL 설계는 코틀린 언어의 여러 특성을 활용한다. 그 중 두가지 특성을 살펴보면 수신 객체 지정 람다 수신 객체 지정 람다를 사용하면 코드 블록에서 이름(변수)가 가리키는 대상을 정할 수 있었다. 이러한 방식을 변경해서 DSL 구..

문제 출처 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 우리나라 화페, 특히 동전의 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. (1원짜리 30개) 또는 (10원짜리 2개와 5원짜리 2개) 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램 작성 입력 t : 테스..

Map, Hash_Map 톺아보기 1.1 시퀀스 컨테이너와 연관 컨테이너 STL 컨테이너는 크게 시퀀스 컨테이너와 연관 컨테이너로 나눈다. 시퀀스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 보관한다. 연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관한다. 그래서 자료를 넣거나 빼고 찾을 때는 Key가 필요하다. 1.2 연관 컨테이너 연관 컨테이너로 map, set, hash_map, hash_set이 있다. 이것들은 Key로 사용하는 값이 중복되지 않은 때 사용한다. 만약 중복되는 key를 사용할 때는 컨테이너 앞에 "multi"를 붙인 multi_map, multi_set, hash_multimap, hash_multiset을 사용한다. 1.2.1. map, set과..

어떤 함수를 호출하려면 그 함수가 정의된 클래스의 이름과 함수 이름, 파라미터 이름 등을 알아야만 했다. 애노테이션과 리플렉션을 사용하면 그런 제약을 벗어나서 미리 알지 못하는 임의의 클래스를 다룰 수 있다. 애노테이션을 사용하면 라이브러리가 요구하는 의미를 클래스에게 부여할 수 있고, 리플렉션을 사용하면 실행 시점에 컴파일러 내부 구조를 분석할 수 있다. 10.1 애노테이션 선언과 적용 애노테이션을 사용하면 추가 메타데이터를 선언과 연결할 수 있다. 메타데이터는 애노테이션 구성 방식에 따라 소스 코드, 컴파일된 클래스 파일 또는 런타임 시 작업하는 도구에서 액세스할 수 있다. 메타데이터란 애플리케이션이 처리해야 할 데이터가 아니라, 컴파일 과정과 실행 과정에서 코드를 어떻게 컴파일하고 처리할 것인지 알..

다이나믹 프로그래밍(Dynamic Programming, DP) 여러개의 하위 문제를 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 ex) 분할 정복 기법으로 피보나치 수열을 구현한다고 생각해보자. 피보나치 수열에서 f(4)를 계산할 때 f(2)를 중복 계산하는 비효율이 발생한다. 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하고 있는 큰 문제에서도 동일하다. 메모이제이션 사용. 메모이제이션이란? 이미 계산한 결과는 배열에 저장함으로서 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면된다. ex) 다이나믹 프로그래밍(동적 계..

Generics(제네릭스) Generics를 사용하면 타입 파라미터(type parameter)를 받는 타입을 정의할 수 있다. 제네릭 타입의 인스턴스를 만들려면 타입 파라미터를 구체적인 타입 인자(type argument)로 치환해야 한다. 예를 들어 List라는 타입이 있다면 그 안에 들어가는 원소의 타입을 안다면 쓸모가 있을 것이다. 타입 파라미터를 사용하면 “이 변수는 리스트다”라고 말하는 대신 정확하게 “이 변수는 문자열을 담는 리스트다”라고 말할 수 있다. 자바와 달리 코틀린에서는 제네릭 타입의 타입 인자(type argument)를 프로그래머가 명시하거나 컴파일러가 추론할 수 있어야 한다. 자바는 맨 처음에 제네릭 지원이 없었고 자바 1.5에 뒤늦게 제네릭을 도입했기 때문에 이전 버전과 호환..