전체 글

저수지 샘플링 Reservoir Sampling

어떤 array에서 random한 i번째 element를 뽑고 싶다고 하자. 일반적으로 전체 배열의 size를 알아내고 rand () % size를 한 후 해당 index를 가져오는 방식을 택할 것이다. 그러나 모종의 이유로 전체 배열 size를 알 수 없는 상황에서도 무작위 추출을 할 수 있다. 예를 들어 array가 아니라 singly linked list여서 끝을 모르고, 단 1번 순회해야 한다는 조건이라면? 1번의 순회로 size를 알아내도 index에 접근하는 데 O(n)이 걸리기 때문에 해결할 수 없다. 이런 상황에서 Reservoir sampling을 사용한다. Reservoir Sampling 정의 Reservoir sampling은 어떤 배열을 1번에 1개의 element만 보며 순회할 ..

23.03.09. 풀었던 문제들

Leetcode 142. Linked List Cycle II 어떤 linked list의 head가 주어졌을 때 cycle이 없으면 NULL, cycle이 있으면 cycle의 시작 vertex를 리턴하는 문제. space를 O(n)으로 쓰면 set같은 걸 써서 중복검사를 통해 쉽게 풀 수 있다. 그러나 O(1)로 풀어야 하는 게 진짜인 문제. 2개의 pointer를 이용해 답을 구할 수 있다. 한 번에 2개 뒤로 이동하는 fast pointer, 한 번에 1개 뒤로 이동하는 slow pointer 이렇게 2개를 둔다. 만약 cycle이 없다면 fast는 진행 중 NULL을 만난다. 이 경우 return NULL cycle이 있다면 fast는 slow보다 항상 빠르기 때문에 k바퀴를 돈 후 slow po..

[OOP] SOLID - Liskov Substitution Principle

이 글은 객체지향 5대 원칙, SOLID principle 중 L인 Liskov Substition Principle을 다룬다. 정의 subtype이 항상 supertype로 치환할 수 있어야 한다는 원칙이다. 이 원칙은 polymorphism에 관련된 이야기이다. 다르게 설명하자면 supertype을 사용하는 위치에 subtype을 넣어도 프로그램 수행에는 변화가 없어야 한다는 말이다. 따라서 supertype에서 사용하는 method는 subtype에서도 사용할 수 있어야 한다. polymorphism을 공부했다면 method overriding과 upcasting에 대해 이미 알고 있을 것이다. Liskov Substitution Principle를 따른다면 upcasting한 상태에서 parent..

23.03.08. 풀었던 문제들

Leetcode 875. Koko Eating Bananas 어제와 동일한 문제. 문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제였다. 구해야 하는 값(k)의 범위는 넓지만 k가 정해졌을 때 array를 순회하면서 다 먹을 수 있는지 여부는 쉽게 구할 수있고(O(n)) 정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다) 모든 binary search문제가 그렇듯 상한을 어떻게 두느냐가 중요하다. 여기서는 piles[i]의 max값이 상한인데, k가 piles[i]보다 크더라도 모든 piles를 먹는 데 걸리는 시간은 동일하기 때문이다. 따라서 상한은 max of piles array이다. 순회하며 계산해도 되지만 명시적인 값을 두는 게 더 빠를 것 ..

[OOP] SOLID - Open Closed Principle

이 글은 객체지향 5대 원칙, SOLID principle 중 O인 Open Closed Principle에 대해 알아본다. 정의 class, function, module 등 프로그램의 구성 요소는 확장에는 열려 있고 수정에는 닫혀 있어야 한다는 원칙이다. 조금 풀어 설명하면 코드를 변경하지 않으면서 기능 변경 또는 확장할 수 있도록 설계되어야 한다는 것이다. Open Closed Principle가 준수되지 않은 경우 요구사항이 변화하거나 새로운 요구사항이 생길 때 기존 코드를 수정해야 한다. 반면 완벽하게 준수되었다면 요구사항의 변화 또는 확장 시 기존 코드를 수정할 필요 없이 새로운 코드만 추가하면 된다. 따라서 이 원칙은 프로그램의 유지보수성을 높여주며 코드의 확장성을 높이는 데 크게 기여한다...

23.03.07. 풀었던 문제들

Leetcode 2187. Minimum Time to Complete Trips 문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제. time의 범위는 아주 넓지만 time이 정해졌을 때 totalTrips는 구하기 쉽고(O(n)) 정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다) 다만 유의해야 할 점은 time의 상한을 어떻게 두느냐이다. totalTrips가 $10^{7}$, time[i]가 $10^{7}$일 때 정답은 $10^{14}$, 만약 time.len이 더 커지면 정답은 더 작아진다. 따라서 상한을 $10^{14} + 1$로 두었다. (근데 이렇게 안하고 LLONG_MAX로 두어도 된다. 다만 이 경우는 overflow 나지 않게 sta..

23.03.06. 풀었던 문제들

Leetcode 1539. Kth Missing Positive Number 증가수열 arr과 숫자 k가 주어질 때 arr에 있지 않은 k번째 배열을 찾는 문제. O(n)으로 풀면 바로 풀린다. O(n) solution // Runtime 6 ms Beats 53.33% // Memory 9.7 MB Beats 38.5% class Solution { public: int findKthPositive(vector& arr, int k) { vector missings; int num = 1, arridx = 0; while(1){ if(arridx < arr.size() && num == arr[arridx]){ // not missing num++; arridx++; } else{ // missing ..

[OOP] SOLID - Single Responsibility Principle

이 글은 객체지향 5대 원칙, SOLID principle 중 S인 Single Responsibility Principle 단일 책임 원칙에 대해 알아본다. 정의 Single Responsibility Principle은 모든 class는 단 하나의 책임을 가져야 한다를 의미한다. 여기서 책임이란 단어가 조금 애매한데, 해당 class가 수행하는 역할이라고 이해해도 된다. 따라서 class가 단 하나의 역할만 가져야 한다고 이해해도 무방하며, 즉슨 class 변경의 이유가 맡고 있는 역할에 대한 변경 단 하나뿐이어야 한다는 것도 의미한다. 예를 들어 class teamA, class teamB가 Data class의 getData()라는 method를 사용한다고 가정하자. getData() method..

23.03.05. 풀었던 문제들

Leetcode 1345. Jump Game IV 어디선가 DP로 많이 본 문제. 첫 접근은 아래와 같이 dijkstra로 풀었다. 그러나 이 경우 for문 때문에 worst case $O(n^{2})$이 날 수 있다. 예를 들어 [1, 1, 1, 1, 1, 1, 1,1 ,1 ,1 ,1 ,1, 2]인 경우 1이 있는 부분을 계속 탐색하기 때문이다. dijkstra는 O(ElogV)인데, 위와 같은 경우 E가 $V^{2}$이 되기 때문이다. typedef pair pii; // .first : index, .second : dist struct cmp{ bool operator()(const pii&a, pii&b){ if(a.second == b.second) return a.first > b.first..

[Java] Collection

이 글에서는 java의 collection에 대해 알아볼 것이다. Collection Collection은 object group을 나타내는 object이다. 편하게 data sturcture 집합이라고 이해하면 된다. Java collection에는 위와 같은 많은 interface와 class가 있는데, 이들에 대해 알아볼 것이다. List 순서가 있으며, 데이터 중복이 허용된다. ArrayList index를 가지고 있어 조회 시 성능이 빠르다. O(1)이다. erase나 insert 시 해당 위치 앞/뒤에 있는 모든 element 위치를 조정해야 하므로 O(n)이다. 따라서 삽입/삭제 성능이 느리다. thread-safe하지 않다. object array로 구현되어 있다. LinkedList 조회..

23.03.04. 풀었던 문제들

프로그래머스 디펜스 게임 앞에서부터 priority queue를 써서 제일 큰 값을 줄여가면 되는 문제. 단순 구현이다. typedef long long ll; int solution(int n, int k, vector enemy) { priority_queue pq; int i = 0; ll sum = 0; while(1){ if(i = sum + enemy[i]){ // 이번 wave 감당 가능하면 넣음 sum += enemy[i]; pq.push(enemy[i]); i++; } else if(k > 0){ // 이번 wave 감당 불가면 무적건 써야 함. 없으면 불가 sum += enemy[i]; pq.push(enemy[i]); i++; k--; sum ..

[Java] Multi Thread

이 글에서는 java에서 사용하는 thread와 multi-thread의 개념만 간략히 짚고 넘어 간다. Thread Thread는 process 내에서 작업의 흐름 단위이다. 하나의 thread는 하나의 작업만 처리하지만, 여러 개의 thread는 병렬로 여러 개의 작업을 처리하기 때문에 더 빠르다. Concurrency & Parallelism 모든 작업은 컴퓨터의 CPU가 작업하며, CPU의 core가 thread를 실행한다. 하나의 core가 여러 개의 thread를 수행할 수도 있고(concurrency), 여러 개의 core에서 여러 개의 thread를 수행할 수도 있다.(parallelism) 하나의 core가 여러 개의 thread를 작업할 때는 각 thread를 조금씩 실행하고 다른 th..

[Java] String vs StringBuffer vs StringBuilder

Java에서는 문자열을 사용할 때 String, StringBuffer, StringBuilder 이렇게 3개의 class를 사용한다. 이 글에서는 이 세가지 class의 차이를 알아볼 것이다. String 앞선 포스팅에 언급했듯 String은 reference type이자 immutable이며 다음 과정을 거쳐 address를 받아온다. literal로 할당 시 intern() method를 호출한다. string constant pool에 해당하는 값이 있으면 그 address를 받아온다. string constant pool에 해당하는 값이 없으면 그 값을 string constant pool에 할당하고 address를 받아온다. new String()과 같이 constructor로 할당 시 hea..

[Java] Primitive Wrapper Class

이 글에서는 java의 primitive wrapper class에 대해 알아본다. Primitive Wrapper Class Primitive Wrapper Class는 primitive type을 object로 다뤄야 할 때 사용한다. 대표적으로 collection이나 generic에 들어가야 하는 값은 모두 object여야 하는데 primitive type의 collection이 필요할 수도 있는데 이 때 primitive wrapper class를 사용한다. 참고로 primitive type는 byte, char, short, int, long, float, double, boolean 이렇게 8종류밖에 없으며 다음과 같이 wrapping한다. byte - Byte char - Character ..

23.03.03. 풀었던 문제들

프로그래머스 덧칠하기 많이 본 greedy / simulation 문제. 앞 또는 뒤에서부터 채워가는 게 optimal이다. // n : 구역, m : 롤러 길이 int solution(int n, int m, vector section) { int answer = 0; int size = section.size(); for(int i = 0; i

[Java] Generic

이 글에서는 java의 generic에 대해 다룬다. Generic Generic이란 java에서 class, interface 또는 method를 정의할 때 type을 pameter화하는 것이다.(type을 parameter로 사용해 일반화하는 것이다.) Generic은 compile time에 object type을 확인하기 때문에 casting을 줄여주고 type 안정성을 보장받을 수 있다, type별로 작성해야 하는 코드의 양을 크게 줄여준다. 사용 방법 : class, interface 아래와 같이 class나 interface를 선언 시 이름 뒤에 keyword를 이용한다. 1개 이상의 type을 넣을 수 있다. method의 parameter type이나 return type으로 해당 gen..

23.03.02. 풀었던 문제들

Leetcode 443. String Compressiong 어디선가 많이 본 string 압축 문제이다. 추가 공간을 할당하고 indexing 실수만 없다면 쉽게 문제를 해결할 수 있지만 이 문제는 in-place 방식으로 풀어야 한다는 추가 제약사항이 있다. 문제는 주어진 대로 구현하면 된다. 어떤 시점 i부터 chars[i]와 같은 마지막 index인 end를 저장하고, i부터 end까지 length를 계산해 넣어주면 된다. class Solution { public: int compress(vector& chars) { int n = chars.size(), cur = 0; for(int i = 0; i

[Java] Java Virtual Machine

이 글에서는 java가 실행되는 환경인 Java Virtual Machine에 대해 알아볼 것이다. Java 8 이후에 변경된 점을 포함하기 때문에 기존 PermGen 영역에 위치하던 Method Area를 Metaspace라고 표기했으며, static과 constant pool이 heap으로 옮겨졌다는 것을 반영한다. JDK, JRE, JVM Java의 구동에는 여러가지가 필요하다. Java Development Kit - Java 개발 도구 Java Runtime Environment - Java용 실행 환경 Java Virtual Machine - Java 실행 프로그램 Java는 여러가지 OS에서 사용 시 java platform indepence를 보장받기 위해 virtual machine을 사..

23.03.01. 풀었던 문제들

Leetcode 912. Sort an Array 문제는 STL 없이 O(nlogn)의 정렬 함수를 만드는 것이다. - 대표적으로 구현하기 쉬운 merge sort를 쓰면 된다. class Solution { public: vector arr; void merge(int start, int end){ if(start == end) return; int mid = (start + end) / 2; // left : mid 포함, right: mid 포함 x vector left(arr.begin() + start, arr.begin() + mid + 1), right(arr.begin() + mid + 1, arr.begin() + end + 1); int leftlen = left.size(), righ..

[Java] Exception Handling

이 글에서는 Java에서 사용하는 예외 처리 방법을 알아볼 것이다. Error vs Exception Java에서 Error는 치명적인 오류이며 프로그램 내에서 수습이 불가능하다. Stack overflow나 Out of memory같이 JVM의 실행에 문제가 생겼다는 것이므로 대처할 수 없다. 반면 Exception은 Error보다는 경미한 오류이며 프로그램 내에서 수습할 수 있다. Java의 exception은 runtime-error과 compile error로 나뉘며 runtime error는 unchecked exception, compile error는 checked exception으로 부른다. (이 문장에서의 error는 Java에서 사용하는 Error와는 다르다! runtime error..