전체보기

저수지 샘플링 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..

23.02.28. 풀었던 문제들

Leetcode 652. Find Duplicate Subtrees tree 순회를 이용해 푸는 문제. 처음에는 leaf node부터 탐색하고, 이후에 올라오려 그랬다. 그러나 TreeNode struct에 parent를 가리키는 것이 없기 때문에 이렇게 풀 수 없었다. 그러다 떠올린 게 string으로 순회하고 겹치는 부분을 찾으면 되는 것 아닌가?였다. 일단 preorder로 순회 결과를 쭉 적고 거기서 겹치는 걸 어떻게 찾을지 고민했다. 그렇지만 이렇게 하면 너무 많은 탐색을 해야 한다. 그래서 고민하다 어떤 점부터 traverse 결과를 map에 넣어두면 똑같은 순회 결과가 몇개인지 알 수 있다를 생각했다. 그리고 이 접근이 맞았다! value가 똑같을 수 있으니 left와 right를 구분해 주..

[Java] abstract class vs interface

이 글에서는 java에서 사용하는 abstract class와 interace, 그리고 둘의 차이를 알아볼 것이다. Abstraction 이전 글에서 abstract를 다음과 같이 설명했다. 일반적으로 컴퓨터 과학에서 추상화라 함은 불필요한 정보(세부 구현 등)는 숨기고 중요한 정보만을 보여주는 것이다. 객체지향에서 추상화는 객체를 만들 때 사용하는 개념으로, 일반화를 통해 공통된 속성과 행위를 추출하는 것이다. 불필요한 정보(객체마다 다른 특이한 정보)는 숨기고 중요한 정보(공통된 속성과 행위)를 상위 class로 추출하는 것이다. 추상 클래스 Abstract Class abstract class는 abstract로 선언된 class이거나 abstract method가 1개 이상 포함된 class를 말..

23.02.27. 풀었던 문제들

리트코드 daily challenge - 427. Construct Quad Tree 전형적인 DFS 탐색 문제. 종료 조건을 잘 명시하면 쉽게 풀 수 있다. // Runtime 12 ms Beats 86.96% // Memory 15.7 MB Beats 66.30% /* // Definition for a QuadTree node. class Node { public: bool val; bool isLeaf; Node* topLeft; Node* topRight; Node* bottomLeft; Node* bottomRight; Node() { val = false; isLeaf = false; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRi..

23.02.26. 풀었던 문제들

리트코드 daily challenge - 72. Edit Distance LCS 비스무리한 DP 문제. LCS로 접근했는데, 안 풀려서 solution을 봤다. (문제 본 지 30분 경과..) dp[i][j]를 word1[0..i-1]을 word2[0...j-1]로 바꾸는 데 필요한 연산 횟수라고 하자. 그러면 word1[i] == word2[j]인 경우에는 dp[i][j] = dp[i-1][j-1]이다. 연산을 할 필요가 없기 때문 else, dp[i][j] = dp[i-1][j] + 1 : insert하는 경우 dp[i][j-1] + 1 : delete하는 경우 dp[i-1][j-1] + 1 : replace하는 경우 와 같은 경우의 수가 나온다. 사실상 dp 식만 세우면 바로 풀리는 문제. // R..

23.02.25. 풀었던 문제들

리트코드 daily challenge - 121. Best Time to Buy and Sell Stock 어떤 array가 주어지고, [ith element보다 뒤에 있는 것들 중 제일 큰 값 - ith element]을 maximize하는 문제. 실수했던 것은 answer가 0보다 작을 때는 0으로 출력해야 했는데, 이걸 인지하지 못했다. ith element보다 뒤에 있는 값들 중 제일 큰 값 - ith element를 모든 element에 대해 수행해야 한다. 그러나 이 접근을 flip해서, [ith element보다 앞에 있는 것들 중 제일 작은 것을 알아와서 ith element에서 그 값을 뺌]도 같은 문제가 된다. 이렇게 되면 앞에서부터 처리할 수 있어서 조금 편해진다. dp 문제인 것 같..

23.02.24. 풀었던 문제들

리트코드 daily challenge - 1675. Minimize Deviation in Array 주어진 array에서 짝수는 2로 나눌 수 있고, 홀수는 2배할 수 있을 때, [최대값 - 최소값]의 결과를 최소화하는 문제. 이것저것 접근하다가 다음과 같이 접근했다. 홀수를 2배하면 짝수가 되기 때문에 모든 경우의 수에서 수를 2배로 하는 것은 단 1번이다.(더 이상 커질 수 없다.) 나누는 것은 홀수가 될 때 까지 나눌 수 있다. 이것에 착안해서 한쪽방향으로만 연산하고자 했다. 증명은 다음과 같다. deviation을 줄이기 위해서는 max값을 줄이거나, min값을 늘려야 한다. 모든 홀수를 2배로 해버린다면, min값을 더 늘일 수 없다. 따라서 max값을 줄이는 연산만 남게 된다. max값을 줄..

[Java] Polymorphism - static polymorphism, dynamic polymorphism, casting

이 글에서는 Java의 inheritance와 연관된 것들에 대해 알아볼 것이다. 다형성 Polymorphism 앞선 포스팅에서 상속을 다음과 같이 정의했다. 하나의 component(variable, method, class, ...)가 casting, overloading, 또는 overriding을 통해 상황에 따라 다르게 사용되는 것을 말한다. Overloading은 이름은 같지만 parameter를 다르게 해, 이름만 같은 함수로 사용하는 것이며, static binding이다. Overriding은 parent class의 method를 child class에서 재정의하는 것이며, dynamic binding이다. polymorphism을 이용하면 code reuse, 유지보수성, 유연성이 증..

[Java] Inheritance - access modifier, super, overriding

이 글에서는 Java의 inheritance와 연관된 것들에 대해 알아볼 것이다. 상속 Inheritance 앞선 포스팅에서 상속을 다음과 같이 정의했다. parent class로부터 새로운 child class를 만드는 것이다. 또한 상속받는 child class는 새로운 attribute나 method를 추가해 확장해 나갈 수 있다. 상속을 통해 class hierarchy를 만들 수 있다. access modifier에 따른 상속 parent class member의 access modifier에 따라 child class에서 사용여부가 달라진다. [public 또는 protected access modifier로 선언된 member]들만이 child class에서 바로 접근할 수 있으며, [pri..

23.02.23. 풀었던 문제들

리트코드 daily challenge - 502. IPO 오늘의 daily challenge는 hard 문제였다. 아직 medium도 시작하지 못했는데 어떻게 풀지..? 좀 막막했는데 문제를 읽다 보니 그리 어려운 것은 아니었다. 문제 조건은 k개의 프로젝트를 끝낼 수 있고, total capital를 최대화 하는 것이다. 초기 자본은 w이고 profit[i] : 순수익, capital[i] : 시작하기 위한 자본이다. 문제 제한 조건을 보았을 때 nlogn으로 풀어야 되는 문제같다. 최대한 naive하게 접근해 보자. 매 탐색 시 현재 w보다 작은 capitals 중 profit이 제일 큰 것을 빼내야 한다. (erase) 만약 profit이 같다면 capital이 작은 것을 빼내야 할 것이다. 모든 ..

[Java] static, final

이 글에서는 Java에서 사용하는 static과 final에 대해 알아볼 것이다. static class 내에서 static으로 선언된 member는 class로 정의된 모든 instance에서 같은 값을 가진다. (class와는 별도로 생성되기 때문에 class를 정의하지 않고도 사용할 수 있다) 해당 member는 class가 메모리에 로드될 때 heap에 올라가기 때문에 instance가 생성되기 전에도 사용할 수 있으며, object와는 별도로 만들어지기 때문에 class 크기에 영향을 주지 않는다. static member는 GC가 관리하긴 하지만, 해당 class가 static member를 참조하지 않는 경우가 거의 없기 때문에 계속 남아 있게 되므로 남발하는 경우 메모리 효율이 나빠진다는 ..