'Algorithm'에 해당되는 글 6건

- 펌: https://cscscs.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%B6%99%EB%8A%94-%EB%B2%95

알고리즘 트레이닝을 하는 방법

알고리즘 트레이닝시, 코딩테스트를 "붙어서 면접을 보는 수준"에 집중해서는 안됩니다.
코딩테스트 점수를 면접에 반영하지 않을까요? 지원자의 능력을 회사/팀에서 정한 문제를 통해 측정한 귀중한 정보입니다. 코딩테스트를 "붙는 수준"까지만 "합리적인 추론 능력"을 키우면.. 다른 outstanding한 스팩이 없는 경우 서류 및 면접에서 채용될 확률이 낮습니다. (물론 코테만 높고, cs가 부족해도 동일하게 채용될 확률이 낮습니다.)

알고리즘 트레이닝의 관점에서 4개 범주로 나눌 수 있습니다.

1. 문법을 모르는 단계
   예를 들어 2중 반복문을 자유롭게 사용하지 못하는 단계가 해당 단계에 속합니다.
2. 동작 원리를 정확히 모르는 단계
   call stack에 대한 이해도가 부족하고, 적절한 상황에 재귀를 사용할 수 없는 단계가 해당 단계에 속합니다.
3. 추론 능력이 부족한 단계
   문법은 알지만 문제를 보았을 때 못 본 유형에 대해 부분 문제도 손도 못대는 경우가 해당 단계에 속합니다.
4. 경험이 더 필요한 단계
   추론해서 문제를 풀 수 있지만, 종종 풀 수 없는 유형의 문제가 있는 경우가 속합니다.

각각에 대해 공부방법을 제시해드리겠습니다.

1. 문법을 모르는 단계 / 2. 동작 원리를 정확히 모르는 단계

우선 해당 언어의 문법을 완벽히 숙지하고, 본인이 사용하는 언어가 메모리를 어떻게 관리하는지 이해해야 합니다. os와 같은 지식은 필요 없지만, 포인터와 function call에 대한 완벽한 이해가 될 때 까지 우선 문법을 공부해야 합니다.

그 후 codeup.kr에서 관계기반 설계까지 모든 문제를 풀어주시면 됩니다.
(* 교육시에는 문제들을 제가 선별해서 진행했지만, 문제 선별은 해당 단계의 개인이 하기 어렵습니다.)

너무 쉬운 문제들은 건너뛰어도 되지만, 아래 문제집에 해당되는 문제들은 건너뛰지 말고 꼭 다 풀어주셔야 합니다.

• 중첩 반복문
• 2차원 배열
• 재귀함수
• 탐색 기반 설계
• 관계 기반 설계

3. 추론 능력이 부족한 단계

많은 사람들이 위 단계 이후에 "잘못된 방향"으로 공부 방향을 설정합니다.

일반적으로 설정되는 잘못된 방향은 다음과 같습니다.

1. DFS, BFS 문제들을 유형화
2. 해당 유형의 문제들을 암기

해당 방법은 아래 소개드리는 방법보다 시간이 더 오래걸리고, 문제도 더 못풀고, 인생에 도움이 1도 안되는 행위 입니다. 코딩테스트가 욕을 먹는 이유중 하나입니다.

제가 제시하는 공부 방법은 본인에 수준에 맞는 알고리즘, 자료구조를 습득하고, 해당 자료구조 알고리즘을 사용하는 능력을 기르는데 초점을 맞춥니다.

방식은 USACO / COCI 문제를 푸는 것 입니다. 방법은 아래와 같습니다.

1. USACO 브론즈, COCI 1번 문제를 선택한다.
2. 해당 문제에 대회 공식 페이지에서 제공하는 답 (solution)이 있는지 확인한다.
   • 솔루션을 찾는 방법은 COCI의 경우 COCI 2019/2020와 같이 해당 연도를 구글에 검색하면 공식 페이지가 뜹니다.
   • USACO의 경우 USACO 2020 February Contest와 같이 현재 보고있는 contest의 연도 / 월을 포함해 구글 검색을 하면 공식 페이지가 뜹니다.
3. 타이머를 재고, 문제당 풀이를 완벽히 정리하는데 30분의 시간을 할당한다.
   이때 풀이를 생각할때 시간복잡도를 생각하지 않고 무조건 답이 나오는 풀이(백트래킹) 풀이를 먼저 생각하고,
   문제 제한에 맞게 한 단계씩 최적화해나간다. 
   1. 정리가 성공한 경우 > 해당 시간 내 문제 풀이가 나온 경우 코딩을 시작한다.
      • 코딩을 한 후 틀린 경우 디버깅에 5분(타이머) 사용한다. 5분이 지난 경우 주저하지 않고 solution을 확인한다.
   2. 정리에 실패한 경우 > 솔루션을 보고 이해하고, 코딩을 시작한다.
      • 솔루션에 본인이 모르는 자료구조 / 알고리즘이 있는 경우 해당 자료구조 알고리즘을 찾아서 학습한다.
      • 본인이 생각했던 부분에서 어떻게 해당 풀이로 넘어가는지에 집중해서 솔루션을 읽는다
4. 1번 반복 (너무 쉽다는 인상을 받으면 한단계 위 문제를 푼다)

초반에는 속도가 느려서 한 문제 한 문제가 굉장히 고되지만, 점점 가속도가 붙습니다. 믿고 진행해보세요.

연도가 넘어갈 수록 난이도가 올라가는 경향이 있기 때문에, 2010년도 정도의 대회를 선택하는 것을 추천드립니다.

USACO와 COCI를 선택한 이유는 solution에서 단순히 최적해만 알려주지 않습니다. 어떤 유도 과정을 통해 느린 솔루션에서 빠른 솔루션으로 최적화 과정을 설명합니다. 즉 이를 통해 어떤 과정으로 문제를 접근해야하고, 생각하는 힘이 길러집니다.

위 단계가 끝났으면 고등부 정보올림피아드 기준 운에 따라 동상은 받을 수도 있는 수준에 도달했습니다.
위 단계에서 USACO 실버, COCI 3~4번 문제를 동일하게 진행함을 병행합니다. 해당 수준까지 쉽게 풀리는 상황이 됐다면, 그 이후는 취업을 위해서 준비로써는 굳이 추천드리지 않습니다.

4. 경험이 더 필요한 단계

그래도 너무 알고리즘 문제풀이가 재밌고, 더 실력을 올리고 싶다면, 추천드리는 방법중 하나는 Codeforces를 사용하는 것 입니다. 방식은 아래와 같습니다.

1. 300~400라운드의 div2 대회의 A, B, C 문제에 대해 USACO, COCI에서 진행했던 방식을 동일하게 진행
2. 400~500라운드의 div2 virtual round를 돌고, editorial을 보고, upsolving을 진행합니다. 한 라운드당 3시간 내지 4시간의 시간이 소요됩니다.

위 과정 중간 중간 실제 대회도 진행해보고 본인 수준을 체크해보면 됩니다. 이 상태면 아마 웬만한 코딩테스트 대회 5시간 대회 문제를 2시간 안에 해결하게 됩니다.

그 이후 공부 방식은 Codeforces의 실제 대회도 참여중이라는 가정하에, [본인 레이팅, 본인 레이팅 + 200] 에 해당되는 문제를 필터링 해서 3에서 제시한 방법을 반복하면 꾸준히 성장하실 수 있습니다. 이후 근본적인 사고력이 부족하다는 느낌이 들 때, koosaga님의 OI Checklist를 활용해보시면 좋습니다. 보통 1900이후 구간에서 해당 작업을 병행하시면 좋습니다.

다만 4에서 제시하는 방식은 굉장히 효율이 안나오는 작업입니다. 취업이 안 된 상황에서 진행하는 것은 매우 비추천합니다.

출처: https://cscscs.tistory.com/entry/알고리즘-코딩-테스트-붙는-법 [CS BLOG:티스토리]

* @참고: https://www.youtube.com/watch?v=2MdsebfJOyM

레드-블랙 트리: 자가 균형 이진 탐색 트리
숫자 등의 비교 가능한 자료를 정리하는데 쓰임.

레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다... NIL 로 리프노드를 가진다.

내 자료는 나보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고,
나보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다.

장점: worst-case guarantees
삽입, 삭제 시 O(log n)만큼의 시간이 필요

연산: 색 전환(color-flipping), 회전(rotation)

레드-블랙 트리의 가장 중요한 특성: 루트 노드로부터 가장 먼 리프노드 경로까지의 거리 < 가장 가까운 리프노드 까지의 거리 * 2
-> roughly 하게 균형 잡힘!!

** 레드 노드의 자식노드는 언제나 블랙!! 레드는 연달아 나타날 수 없고, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있음.


1. 노드는 레드 또는 블랙
2. 루트 노드는 블랙
3. 리프 노드들은 블랙
4. 레드 노드의 자식노드 2은 모두 블랙
5. 어떤 노드로부터 리프 노드에 도달하는 모든 경로에서 자기자신을 제외하고 모두 같은 개수의 블랙 노드 존재


* 삽입 노드의 색: red -> 이유: 5번을 만족하기 위해 

- @참고: https://vmpo.tistory.com/106

양수에서 가장 큰 수가, 음수에서 가장 작은 수다!!!

11111111111111111111111111111111 = -1
11111111111111111111111111111110 = -2
11111111111111111111111111111101 = -3
11111111111111111111111111111100 = -4
11111111111111111111111111111011 = -5
11111111111111111111111111111010 = -6
11111111111111111111111111111001 = -7
11111111111111111111111111111000 = -8

//음수는 not 연산에 1을 더한 값이다.
-1*n == ~n + 1

- @참고: https://blog.naver.com/jihogrammer/222314445259

아래와 같은 형태로 입력되는 입력값을 빠르게 받기는 법

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

- 코드

private static int read() throws Exception {

    int c, n = System.in.read() & 15;

    while ((c = System.in.read()) > 32)
        n = (n << 3) + (n << 1) + (c & 15);

    if (c == 13) System.in.read();

    return n;

}
[출처] [Java] System.in.read() - 3|작성자 jihogrammer

코드 주석

# n = System.in.read() & 15;

15 = 1111(2) 이고

n = System.in.read() 일 때, 한글자의 수를 읽으면 48 <= n <= 57

48 = 32 + 16 = 2^5 + 2^4 이므로 4, 5번째 자리를 제외한 하위비트만 읽어오면 48를 빼는것과 같아진다.

뺄셈을 연산하지 않고도 단순 비트 연산을 통해 읽을 수 있다.

Char	ASCII	Binary
'0' ==	48	== 11_0000
'1' == 	49  == 11_0001
'2' ==	50  == 11_0010
...
'9'	== 	57	== 11_1001

n & 15 연산을 수행하여 뒤 4자리 비트만 읽을 수 있다.

# n = (n << 3) + (n << 1) + (c & 15);

위 식은에서 (c & 15) 앞쪽은  n = n * 8 + n * 2 

= n * 10 이다.

왜 이렇게 표현했는가 하면,

* 연산은 생각보다 ALU에서 처리하는 양이 많다. (내부적으로 shift 연산과 add 연산을 반복적으로 수행하기 때문에)

최적화 되어있는 방식으로 표현하여 수행속도를 빨리하기 위함이다.

- @참고: https://scshim.tistory.com/267

1. 선택 정렬: 가장 작은걸 조사하면서 맨앞부터 순서대로 차곡차곡 보내기 //O(N^2)
2. 삽입 정렬: 현재 카드의 앞쪽 한칸씩 조사하며 더 작은 수를 만나면 그 뒤에 삽입한다. //O(N^2)
3. 퀵 정렬: 피벗을 선정해(호어Hoare 분할 방식은 첫번째 원소가 피벗!) 왼쪽부터 오른쪽으로는 피벗보다 큰 데이터 찾고, 오른쪽에서 왼쪽으로는 피벗보다 작은 데이터를 찾아서, 서로 엇갈리지 않을 땐 <- 로 찾은 수와 -> 로 찾은 수를 서로 교환. 서로 엇갈릴 땐 <- 로 찾은 수와 피벗을 교환. <- 로 모두 찾아도 피벗이 가장 클 땐 -> 맨 마지막과 피벗을 교환. // 평균 O(NlogN), 최악은 o(N^2)
4. 계수 정렬: 모든 데이터가 양수일 때, 데이터 크기가 제한적(1,000,000)일 때 

- @참고: https://st-lab.tistory.com/243

Comparable, Comparator와 정렬의 관계

- 양수일 경우: 두 원소의 위치를 교환함

- 음수일 경우: 두 원소의 위치를 교환 안함

따라서 o1, o2 를 비교할 때

val(o2) - val(o1) 을 리턴하면, 뒤의 값이 컸을 때 위치를 교환하므로 내림차순이되고,

val(o1) - val(o2) 를 리턴하면, 앞의 값이 컸을 때 위치를 교환하므로 오름차순이 된다.