나무늘보의 연구실

아래는 LeetCode에서 Binary Tree를 배열 형태(JSON)로 표현하는 예제이다. 위와 같은 트리를, [5,4,8,11,null,13,4,7,2,null,null,null,1] 로 표현한다. Root node에서부터 시작해서 위에서부터 & 왼쪽에서부터 순서대로 5 -> 4 -> 8 -> ... 채워넣는 식이고, 만약 상단 노드가 null 이면 null, null 을 명시적으로 쓰지 않고 그냥 생략할 수 있다. 이렇게 해도 모호성이 생기지는 않기 때문이다. 이런 표기 방식이 Python 등에서는 큰 문제는 안되는데, C++에서는 정말 귀찮아진다. 문자열 trim부터 split, 그리고 stoi로 변환한 다음 한땀한땀 tree를 만들어야 하기 때문이다. 파이썬의 간결함에 게을러진 나머지 C++가 ..

아마 언어 문법책에서 조건문을 다룰 때 예시로 나오나 보다. 누군가 물어보아서 잠깐 생각해보았다. 일단 가위바위보에서는 물고 물리는 관계가 존재한다. (상성 관계라고도 하는데, 정확한 단어인지는 모르겠다) 영어로는 circular relationship이라고 부르면 좋을 것 같다. 가위 < 바위 < 보 < 가위 이제 가위에 0, 바위에 1, 보에 2를 대응시키고, 다음 표를 만들어보자. 내가 낸 것을 a라 정하고 다른 사람이 낸 것을 b라 정하면, a - b의 값이 가위바위보의 결과가 된다. 비김 = 0 이김 = 1 or -2 짐 = 2 or -1 그런데 음수가 들어가면 지저분해지므로 a - b + 3 을 하여 shifting을 시키자. modulo 연산 (% 3)을 적용시키고 싶은데, 프로그래밍 언어마..

어떤 배열이 주어졌을 때 가장 큰 수를 구하려면 어떻게 할까? Python의 built-in함수인 max를 사용하면 된다(...). 관습적으로 어떤 임시 변수를 잡아놓고, 임시 값보다 더 큰 값이 들어올 때마다 업데이트를 하는 방식을 주로 쓴다. 파이썬 코드로는 다음과 같다. -INF (INF는 아주 큰 값)를 사용할 수도 있지만 정수의 범위에 제한을 없애는 것이 추세인 것 같아서 None을 사용하였다. def get_first_largest(arr): first_largest = None for e in arr: if first_largest is None: first_largest = e else: if e > first_largest: first_largest = e return first_larg..

문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. (문제 링크) 최대 "연속" 부분합을 구하는 문제다. 코드 답안만 보면 간단하지만, 최적 부분 구조 (optimal substructure)..

(문제 링크) 말 그대로 n! = 1 * 2 * ... * n 을 계산해주는 프로그램이다. 반복문이나 재귀 함수를 사용하는 것이 가장 흔한 솔루션이고, 또 다른 솔루션은 reduce 함수를 사용하는 방법이다. reduce 함수는 functools 모듈에서 정의된 함수다. 함수 모양은 다음과 같다. functools.reduce(function, iterable[, initializer]) 파이썬의 reduce 함수는 OCaml의 fold_left와 역할이 같다. 이 함수가 하는 일은 다음과 같다. List [1,2,3,4,5]에 대해서 fold_left 를 적용하면 그림처럼 f(f(f(f(f(z,1),2),3),4),5) 의 모양으로 계산 해준다. 우리가 구하고 싶은 것은 팩토리얼인데, 그렇다면 f를 어..

문제 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. A와 B는 공백 한 칸으로 구분되어져 있다. 출력 첫째 줄에 다음 세 가지 중 하나를 출력한다. A가 B보다 큰 경우에는 '>'를 출력한다. A가 B보다 작은 경우에는 '

(문제 링크) 대부분의 프로그래밍 언어에서 역슬래시(backslash)는 확장열(escape sequence)의 시작을 의미한다. 키보드 상에서 입력하기 애매한 글자들을 표기할 때 "\ + 문자" 조합을 사용한다. 컴파일러는 이러한 escape sequence를 발견하면 그에 대응되는 특수 문자로 치환한다. "\" 글자 자체를 입력하고 싶으면 "\\"으로 쓴다. print 함수에 들어가는 문자열에 "\\"을 쓰면 된다. 이 포스트에서는 그렇게 하기보다는 base64 인코딩을 사용해서 고양이를 문자열 안에 알파벳과 숫자의 조합으로 저장할 것이다. :) 잠깐 확장열(escape sequence)에 대해서 알아보자. C에서 사용되는 escape sequence의 목록을 아래 표에 나타냈다. 다른 프로그래밍 언..

문제 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original da..

동적 계획법(Dynamic Programming)은 큰 문제를 작은 문제로 쪼개서 푸는 방법이다. 어떤 문제가 Optimal substructure를 가지고 있으면 부분 문제들의 조합으로 큰 문제의 최적해를 구할 수 있다. 오픈 채팅방의 어떤 분이 (백준-2156-포도주 시식) 문제를 푸는데, 자신이 세운 점화식이 왜 동작하지 않는지 물어봤다. “올바른 점화식을 세우면 됩니다”라는 답변 대신에, 점화식이 틀렸을 때 반례를 어떻게 찾으면 좋을지에 대해서 고민해보았다. 틀린 점화식 문제에서의 핵심 조건은 "연속해서 포도주 3잔을 마실 수 없다"이다. (틀린) 점화식은 다음과 같았다. \[ dp_{wrong}[i] = max(w[i]+w[i-1]+dp_{wrong}[i-3], w[i]+dp_{wrong}[i-..