04/04

HackerRank

• 오랜만의 HackerRank.
• 문제는 Roads and Libraries.
• 일단 실패하는 테스트 케이스로 뼈대 작성.
• 다음으로, isolated subgraphs가 없다고 가정하고 구현.
• 마지막으로, isolated subgraphs가 있다고 가정하고 구현.

04/05

HackerRank

• 어제의 구현을 submit 해보면 일부 케이스 timeout이 발생.
• 공간을 좀 덜 쓰는 bfs로 바꿔 봄.
• CityNode라는 별도의 값 객체 사용 대신 visited와 neibhgors를 배열 사용하는 방식도 사용.
• 사용하는 컬렉션연산을 보면 당연히 의미 없음을 알고서도 MutableSet 대신 Array로 바꿔보기도.
• 2월에 겪었던 HackerRank의 문제인가 싶어서, bfs라면 굳이 없어도 되는 CityNode의 value 필드를 제거해 보기도 함.
• 혹시나 싶어 처음의 구현을 자바 버전으로 바꿔 submit 해보니, 바로 성공함.
• Kotlin은 아직도 지원이 부족한 듯.
• 내 아까운 시간 ㅠㅠ

04/07

코딩인터뷰 완전분석

• 바쁘다는 핑계로 뜸했는데 조금씩이라도 다시 읽으려 함.
• “비트 조작” 추가.

04/14

코딩인터뷰 완전분석

• 2의 보수와 음수
• 산술 우측 시프트 vs. 논리 우측 시프트
• 기본적인 비트 조작:비트값 확인 및 채워넣기

04/30

HackerRank

Ice Cream Parlor

• Hash Tables: Ice Cream Parlor 풀이
• Kotlin 버전으로 작성했는데 Submit 하면 다 틀리다고 나옴.
• 아무리 봐도 이상해서 Java 버전으로 바꿔서 Submit 하면 성공함.
• 여러 번 문제를 겪고 나니, 다음부터는 Java로 풀기로.

Pairs

• 이번엔 그냥 처음부터 Java로 작성함.
• 깊게 생각 안 하고 일단 풀이
• 살짝 코드 개선

05/01

HackerRank

Triple Sum

• 성능 고려 안 하고 일단 구현
• 성능 개선
• 마지막으로 간단히 리팩토링

05/03

코딩인터뷰 완전분석

• 수학 및 논리 퍼즐.
• 가장 먼저 소수 이야기.
• 다음으로 확률 이야기.
• 나머지 내용은 기록 생략.

05/05

HackerRank

Minimum Time Required

• brute force로 먼저 구현.
• 매일 매일을 확인하는 것.

05/07

코딩인터뷰 완전분석

• 재귀와 동적 프로그래밍
• 피보나치 재귀
• 피보나치 하향식 동적 프로그래밍

05/08

코딩인터뷰 완전분석

• 피보나치 상향식 동적 프로그래밍

05/15

HackerRank

Minimum Time Required

• Brute Force로 구현했던 것을 Binary Search 방식으로 개선
• 시간 복잡도는 O(n * log n).

05/18

HackerRank

Swap Nodes

• 일단 트리 구성하고 탐색하는 로직 구현
• 구성된 트리를 swap 하는 로직 추가
• 중복된 원소를 포함하지 않는 트리. 그리고 균형 트리 아님.
• in-order traversal.

05/22

HackerRank

Making Candies

• 최근 들어 가장 어려웠던 문제.
• 일단 성능 고려 없이 1차 구현
• 하지만, 실패하는 케이스가 있었음.
• machine이나 worker를 늘리는 게 의미 없는 경우가 있는데, 너무 좁은 범위에 대해서만 처리하고 있어서 문제.
• 그래서 좀 더 일반화 된 판단 로직으로 수정
• 그러고 나서 곱셈이 overflow 나는 경우 고려 추가
• 여기까지 하고 나니 틀리는 문제는 없었음.
• 이제 성능 개선할 차례.
• 가장 먼저, machines과 worker 늘리는 처리를 루프 없이 가능하게 변경
• 다음으로, machine이나 worker를 늘릴 수 없는 경우의 루프를 최소화
• 그제서야 모든 케이스가 통과함.

05/28

HackerRank

Maximum Subarray Sum

• 일단 문제는 여기 참고.
• brute force로 먼저 구현.
• 다음으로 성능 개선 버전 구현.
• 핵심은 배열의 prefix sum(+modulo)을 이용.
• 더불어, 현재 루프의 prefix sum보다 큰 prefix sum 중에 최소값을 찾아야 함. 아래 규칙 때문임.
• max = A(현재 원소까지의 prefix sum) - B(현재까지 모은 prefix sum 중에 A보다 큰 최소값)
• 예컨대 아래의 경우에서, 3번째 원소에 대해 루프를 돌고 있다면, 1번째 prefix를 찾아야 함.
• balanced binary search tree 활용.
• 이를 통해, O(N * logN)을 기대할 수 있음.

modulus     = 5
array       = [7,1,3]
prefix sum  = [2,3,1]

TreeSet

HackerRank의 Maximum Subarray Sum 풀다가 TreeSet 간단히 정리.

NavigableSet

• NavigableSet의 구현체.
• TreeMap을 기반으로 함.
• NavigableSet은 SortedSet 인터페이스의 확장.

navigation method

• NavigableSet 구현체이므로 (SortedSet에는 없는) navigation methods를 추가로 제공.
• 주어진 대상과 근접한 값을 찿아내는 lower, floor, ceiling, higher 같은 것들이 그 메서드.

ordering

• 이렇게 근접한 것을 빠르게 찾아내기 위해 원소들을 정렬상태로 유지함.
• 정렬에는 2가지 방법 사용.
  • 원소의 natural ordering.
  • 생성자에 주어진 Comparator.
• 기본 연산(add, remove, contains)에 대해 log(n) 보장.
• 정렬 상태 유지를 생각하면 어쩌면 당연.

synchronization

Note that this implementation is not synchronized.

• 만약, 여러 스레드가 동시에 이 컬렉션에 접근하고,
• 한 개 이상의 스레드가 이를 수정하려 한다면,
• synchronized 처리가 필요함.
• 아래와 같이 “wrapped”로 만드는 것도 방법.
• 만약 이렇게 한다면 생성 시점에 하는 것이 가장 좋음.

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

fail-fast behavior

• 당연하게도(?) iterator가 반환하는 iterator는 fail-fast.
• 즉, iterator가 만들어지고 난 뒤, iterator 자신의 remove 메서드를 통하지 않고 수정된다면, ConcurrentModificationException 예외 던져짐.

Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

• 주의할 것은, 동기화되지 않은 동시 수정 시 fail-fast 보장이 실패할 수 있음.
• 문서에서는 단지 버그를 감지하는 메커니즘으로만 사용하라고 함.
• 이 예외에 의존해서 정확성(correctness)을 기대하는 것은 X.

06/08

코딩인터뷰 완전분석

• 정렬과 탐색
• 기수 정렬도 당연히 알아야 하는 구나 윽.

06/09

코딩인터뷰 완전분석

• 테스팅
• 면접이라는 컨텍스트를 벗어나도 의미 있는 이야기.

06/11

Vector

소개

대부분의 경우에 안 쓰는 것이 권장되는 Vector이긴 하지만 자꾸만 보여서 정리. 일단 Java Vector 문서에 따르면 첫 소개가 아래와 같음.

The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

설명만 보면 ArrayList가 떠오름. 그래서 주로 ArrayList와 비교하여 정리함.

synchronized

• ArrayList와 다르게 synchronized.
• 그 만큼 오버헤드가 따름.

CopyOnWriteArrayList

• 그런데 동기화가 얼만큼 필요한지 생각해 볼 필요 있음.
• 많은 경우에 쓰기에 대해서만 동기화가 필요하고 읽기에는 필요 없음.
• 이 때 CopyOnWriteArrayList를 고려.
• 읽기 시 성능에 유리.
• 하지만 주의할 점이 있음.
• iterator가 concurrent modification를 지원.
• 언뜻 보면 좋아보이나, 이를 위해 컬렉션 수정 시 매번 복제가 일어남.
• 잦은 수정에는 부담인 것.

Collections.synchronizedList

• 한편, 정말 모든 연산에 동기화가 필요할 수도.
• 하지만 이 때도 Collections.synchronizedList 사용을 고려.
• 이는 Vector에게 열려 있는 elements(legacy) 사용을 피할 수 있게 도와줌.
• Enumeration을 반환하기에 fail-fast 하지 않음.
• fail-fast에 대한 내용은 아래에 명시. 이 내용은 자바 컬렉션 클래스 문서마다 보이는 듯.

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the vector is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

• 여기도 함께 참고.

growable array of objects

• Vector 또한 ArrayList처럼 동적으로 크기를 늘림.
• 하지만 ArrayList가 현재 크기의 50%만 늘어나는 반면에 Vector는 100%.
• 여기서 늘어난다는 것은 vector의 size가 아닌 capacity라는 점에 유의.

Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector’s storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.

코딩인터뷰 완전분석

• 스레드와 락 추가

06/13

java.lang.Character Unicode Character Representations

자바의 Character 문서에 Unicode Character Representations 부분이 있음. 간단히 기록.

Unicode Specification

1. Character 객체가 캡슐화하는 char 데이터 타입은 오리지널 유니코드 명세에 기반.
2. 이는 문자^character를 고정 넓이의 16 비트 엔티티^{fixed-width 16-bit entitie}로 정의.
3. String과 다르게 16비트가 넘어가는 문자를 표현할 수 없음을 말하는 듯.

supplementary characters

1. char 데이터 타입은 오리지널 유니코드 명세에 기반했지만, 유니코드는 그 이후로도 계속 변화했고 현재는 16비트 이상으로 표현되는 문자를 허용.
2. 유효한 코드 포인트^{code points} 범위는 현재 U+0000에서 U+10FFFF 까지.
3. Unicode scalar value라고 부름.
4. 이 중에서 U+0000에서 U+FFFF까지의 문자 집합을 Basic Multilingual Plane(BMP)라고 부름.
5. 그리고 U+FFFF를 넘어가는 코드 포인트의 문자들은 supplementary characters로 부름.
6. 자바 플랫폼은 UTF-16을 char 배열과 String, StringBuffer 클래스에서 사용.
7. 그래서 supplementary characters를 char 값의 짝으로 표현.
8. About Supplementary Characters에 따르면 이 방식을 surrogate pair라고 부름.
9. 첫 번째 값은 high-surrogates 범위(\uD800-\uDBFF)를 갖고,
10. 두 번째 값은 low-surrogates 범위(\uDC00-\uDFFF)를 가짐.

*참고로, U+나 \u 문자들은 뒤이은 숫자들이 16진수임을 나타냄.

code point

1. int 값은 모든 유니코드의 코드 포인트를 표현할 수 있음.
2. int의 최하위 21개 비트는 유니코드 코드 포인트를 나타내는 데 쓰임.
3. 나머지 최상위 11개 비트는 0.
4. 21개 비트가 쓰이는 까닭은 위에서 코드 포인트의 최대값이 U+10FFFF이기 때문.
5. 바이너리 숫자로는 100001111111111111111 즉, 21자리.
6. 10진수로는 111411.

supplementary character behavior

1. char 값만을 인자로 받는 메서드는 supplementary characters 지원 불가.
2. 예컨대, Character.isLetter('\uD840')은 false를 반환.
3. 하지만 \uD840는 high-surrogates에 포함되는 대상. 문자열에서는 글자 표현에 사용되는 것.
4. 한편,isLetter(int codePoint)와 같이 int를 받는 메서드는 모든 유니코드 문자를 지원할 수 있음.
5. Character.isLetter(0x2F81A)는 true 반환.

code point vs. code unit

문서 읽다 보면, code point와 code unit 차이가 궁금해짐. 여기 그 차이가 잘 설명되어 있음.

For example, the snowman glyph (☃) is a single code point but 3 UTF-8 code units, and 1 UTF-16 code unit.

06/14

코딩인터뷰 완전분석

• 배열과 문자열 해법
• 그 중에서도 중복이 없는가 내용.
• 여러모로 도움되고 재밌던 내용.
• URLify도 기록.

06/15

회문 순열(palindrome permutation)

• 코딩인터뷰 완전분석에 나온 내용
• LeetCode Article에 나온 내용

06/18

문자열 압축(string compression)

• 정리 내용은 여기.

06/21

코딩인터뷰 완전분석

• 0행렬
• 문자열 회전
• 중복 없애기
• 뒤에서 k번째 원소 구하기

06/23

• 연결리스트 분할

06/24

• 연결리스트의 합
• 연결리스트의 역순 합

06/25

AMQP

• AMQP 0-9-1 Model Explained 문서를 쭉 읽고,
• 간단히 정리.

06/28

Spring AMQP

• @RabbitListener 애노테이션으로 어떤 것까지 할 수 있을지 알아보기 위해,
• Spring AMQP 문서의 Receiving Messages 부분을 읽는 중.
• 간단히 기록도 함께 진행.