hs-archive

dist는 distributable(배포 가능한)의 약자로, 재사용되는 소스 코드를 컴파일하거나 축소할 필요 없이 다른 사람이 직접 사용할 수 있는 파일이 저장되는 디렉터리를 의미합니다. Java 라이브러리의 경우, 누군가 작성한 소스 코드를 사용하려면 먼저 소스를 컴파일해야 사용이 가능합니다. 그러나 라이브러리 작성자가 이미 사전 컴파일된 버전을 저장소에 넣어두면, 사용자는 컴파일 과정 없이 바로 사용할 수 있습니다. 이러한 이미 컴파일된 버전이 dist 디렉터리에 저장됩니다. JS 모듈의 경우에도 비슷한 원리가 적용됩니다. 보통의 경우 JS 코드는 프로덕션에서 사용하기 위해 축소되고 난독화됩니다. 따라서 JS 라이브러리를 배포할 때는 일반 소스 코드를 src 디렉터리에, 축소 및 난독화된 버전을 di..

CLI란 Command Line Interface의 약자로 이름 그대로 명령어를 입력해서 컴퓨터를 동작시키는 것이다. CLI 말고 GUI라는 단어도 있다. GUI는 Graphic User Interface의 약자로 우리가 흔히 사용하는, 아이콘을 클릭하거나 터치하여 컴퓨터를 동작하는 형식을 말한다. 그냥 편하게 GUI만 쓰면 되지 CLI를 왜 사용할까? 1. CLI로만 할 수 있는 작업이 있다. 예를 들어 Git에서 제공하는 기능을 100% 사용하려면 CLI를 사용해야 한다. GUI도 지원을 하지만 CLI보다 지원되는 기능이 작다. 게다가 배치 잡 스케쥴러, 애플리케이션 서버 가동, 빌드 및 배포 등등은 보통 CLI로만 할 수 있다. 2. 프로그램 설치가 쉽다. 브라우저 열어서 홈페이지 찾은 뒤, 다운 ..

회문이란 왼쪽부터 읽는 것과 오른쪽부터 읽는 것이 같은 문자를 뜻한다. ex) 기러기, 토마토, aba, abba, aa, a 등등... 가장 긴 부분 회문이란 "babad"에서 "bab"와 "aba"이고 "cbbd"에서 "bb"이다. 회문의 특성을 생각해보면 회문 안에 회문이 있다는 것을 찾을 수 있다. 이를테면, "cabbac"는 "abba"를 포함하고 있고 "abba"는 "bb"를 포함하고 있으며 "bb"는 "b"를 포함하고 있다. 이를 보면 다음과 같은 생각을 가질 수 있다. 1. 양쪽 끝에 있는 문자들이 서로 같고 2. 양쪽 끝에 있는 문자를 제외한 글자가 회문이면 3. 해당 글자는 회문이다. (ex. "abba"일 때 1. 양쪽 끝에 있는 문자들이("abba") 서로 같고 2. 양쪽 끝에 있는..

우리는 알고리즘의 속도를 예측할 수 있어야 합니다. 그래야 무엇이 더 빠른 알고리즘인지 감별할 수 있기 때문입니다. 만약, 제가 만든 알고리즘의 시간 복잡도가 n^2/2 * e + 1.345n + 32이라면 n이 증가함에 따라 시간 복잡도가 어떻게 증가할지를 한눈에 파악하는 것은 매우 어렵습니다. 게다가 100000000n + 12345의 시간 복잡도를 갖는 또 다른 알고리즘과 속도 비교를 하기란 더더욱 어렵습니다. 그러나 위 두 식이 n^2과 n처럼 단순화된 형태라면 각각의 증가량과 두 식 간의 차이를 단숨에 파악할 수 있을 것입니다. 이를 가능하게 해주는 것이 바로 점근 표기법입니다. 우리는 점근 표기법을 사용하여 식을 단순화할 수 있습니다. 점근 표기법은 최고차 항의 차수만 남기고 다른 모든 항과 ..

해시 해시는 값이 저장될 위치(index)를 간단한 연산으로 구하는 것이다. 해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스 삼아 데이터의 값을 키와 함께 저장하는 것이다. 이때 데이터가 저장되는 곳을 버킷 혹은 슬롯이라 한다. 해시 테이블의 크기는 보통 소수로 설정하는데 이는 해시 함수 내부 과정이 해싱을 한 뒤 그 값을 해시 테이블의 크기로 나눈 나머지를 리턴하기 때문이다. 해시 테이블의 크기가 소수가 아니라면 나머지 값이 한 곳으로 치우지기 쉽다. 이를 방지하기 위해 테이블의 크기는 소수로 한다. 그냥 리스트 쓰면 되지 해시 함수를 통해서 숫자를 만들고 그것을 key로 사용하는 해시라는 개념을 왜 굳이 만들었을까? 만약 List에 위 정보를 저장했다고 가정해보자. a_list = ..

수많은 마라톤 선수들이 마라톤에 참여했습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. list를 사용해 풀 수도 있겠지만 list의 경우 검색의 시간 복잡도가 O(n)인데 반해 dict는 O(1)이다. 따라서 list보다 dictionary를 사용하여 문제를 푸는 것이 더 짧다는 생각을 갖고 문제를 풀어보자. dictionary를 사용하여 푸는 방법은 다음과 같다. for문으로 participant을 하나 씩 방문한다. hash() 함수를 사용해 참가자 이름을..

수열 규칙성이 있는 숫자들의 나열로 일정한 규칙에 따라 한 줄로 배열된 수의 열을 뜻한다. 첫 번째 수열(a1)부터 n 번째 수열까지 있을 때 아래와 같이 나타낼 수 있다. 등차수열 연속된 두 항의 차가 모두 같을 때 이를 등차수열이라 하고 그 둘의 차이를 공차(공통된 차이)라 한다. 공차는 d로 표시한다 (common difference) 3의 배수로 만든 수열 {3, 6, 9, 12, 15,...}에서 연속된 두 항의 차는 3으로 모두 같으니 이 수열은 공차가 3인 등차 수열이다. 첫 번째 항 3이고 두 번째 항은 6이다. 뒤로 한 칸씩 갈 때마다 공차를 더한 형태다. 따라서 위 수열의 n 번째 항은 3 + (n - 1)d이다. 일반화하면, 첫 번째 항이 a일 때 n 번째 항을 구하는 식은 아래와..

3의 배수 판별법 N의 자릿수를 모두 더한 값이 3의 배수이면 N은 3의 배수이다. 예를 들어, 432인 경우 432 = 4*(1+99) + 3*(1+9) + 2 = 4 + 3 + 2 + 4*99 + 3*9 이때 9와 99는 3의 배수이므로 4*99와 3*9는 더하지 않아도 된다. = 4 + 3 + 2 = 9 9는 3의 배수이므로 432는 3의 배수이다.

최대공약수 (Greatest Common Divisor - GCD) 두 수의 공약수 중 가장 큰 수를 뜻한다. 최소공배수 (Least Common Multiple - LCM) 두 수의 공배수 중 가장 작은 수를 의미한다. lcm = 두 수의 곱 / gcd로 구할 수 있다. 유클리드 호제법 두 양의 정수의 최대공약수를 구하는 방법이다. 두 양의 정수 a, b(a > b)에 대하여 a = bq + r일 때 a와 b의 최대공약수는 b, r의 최대공약수와 같다. r = 0이라면, a, b의 최대공약수는 b가 된다. 이를 파이썬으로 구현해보면 다음과 같다. def Euclidean(a, b): while b != 0: r = a % b a = b b = r return a 내부 과정을 확인해보면 아래와 같다. d..

ArrayList 내부적으로 데이터를 배열에서 관리하며, 요소 삽입 시 배열의 크기를 넘어설 경우 새 배열을 만들고 기존 배열의 데이터를 모두 새 배열로 복사하기 때문에 O(n)이 걸린다. 따라서 많은 양의 자료를 추가/삭제하는 경우 데이터 복사가 빈번히 일어나므로 성능 저하를 일으킨다. 데이터를 배열로 관리하므로 인덱스를 통한 검색의 경우 O(1)이 걸린다. LinkedList 한 개의 노드에 내가 갖고 있는 데이터와 다른 노드에 대한 정보를 갖고 있다. 단방향 링크드리스트의 경우 다음 노드에 대한 정보만 갖고 있고 양방향의 경우 이전 노드에 대한 정보도 갖고 있다. LinkedList는 시작 요소나 가운데 요소를 삭제/삽입할 때 O(n) 시간이 걸리는 ArrayList와는 달리 다음 노드, 이전 노드..