컴퓨터의 '눈'을 통해 세상을 보기

김영현(kipa00)

김영현(kipa00)
solved.ac staff
ICPC Sinchon 알고리즘 강사
...

무슨 얘기를 할까?
"내 얘기"를 해야 – 나는 어떻게 인생을 살아왔나?

프로그래밍은 19년 전부터, PS는 13년 전부터 시작
그 전까지는 (그리고 PS를 시작하고 나서도) 수학 공부를 열심히 함
대학에서도 미련을 놓지 못하고 수학을 복수전공
코로나 중 운 좋게 들어간 회사에서도 2년 반을 일함

이중 얘기할 만한 부분은 두 가지 정도:

나는 어떻게 PS를 시작했나?
나는 어떻게 회사를 다녔나?

솔직히 말하면 그다지 얘기하고 싶지 않았습니다
크게 세 가지 이유:

회사 생활이 그리 좋지만은 않았음 – 좋은 사람들이 있었지만 그와 별개
지금은 복학생 신분으로, 회사 생활의 많은 부분을 까먹음
여러분과 제가 다른 사람처럼 보임

제가 이 자리에 서서 얘기하는 것은 뭐 크게 잘나서가 절대 아닙니다
그저 조금 일찍 시작하고 시간을 조금 더 갈아넣은 것

이걸 얘기해 보도록 합시다
크게 두 가지 이유:

듣는 여러분들에게 더 재밌을 것이라 생각

회사 얘기는 "그렇구나" 하며 들어야 하는 부분이 많음
"재밌다"를 바꾸어 얘기하면 여러분이 생각할 것이 많다는 뜻

"PS 커뮤니티"에 PS 얘기를 하는 것만큼 기여 방향이 뚜렷한 것이 또 없음!

발표 준비를 하면서 다소 걱정인 부분 – 제 말을 법처럼 따르려 하지 말아 주셨으면
다음 사항을 명심해 주시면 감사하겠습니다:

여러분과 저는 목적지가 다를 수 있습니다

저는 뚜렷한 목적지가 없는 상태에서 재미를 추구하기 위해 한 것이 많음
여러분의 목적지 – 코테, 대회 입상, … – 를 잘 생각하시길

제 길이 유일하게 올바른 길은 아닙니다

다른 사람들의 얘기도 많이 들어 보세요
제 이야기를 한 사람의 경험으로만 들어 주셨으면

제 길이 올바른 길이 아닐 수도 있습니다

위험한 숲속을 헤쳐 살아돌아왔다고 해서 그 사람이 간 길을 또 갈 이유는 없음
특히 저는 쌓아온 시간이 길기 때문에 더욱 그럴 가능성이 높음

초등학생의 키파

궁금한 것을 해결하는 수단으로서의 컴퓨터

초등학생 때 '산수'에 관한 유명한 밈(meme)이 세 개 정도 있었습니다

"일 더하기 일은 🪟", "사 빼기 빼기 영은 💩", "\(1 + 1 = 2\), \(2 + 2 = 4\), …"
첫 두 개는 기하적 배치에 의한 농담이지만, 마지막 것은 기하적 증가에 대한 농담

마지막 것을 대답하기 위해 "좀 외워 보자"라는 생각을 갖게 됨

이 방법의 유일한 문제점: 아무도 참값이 뭔지 모름

2005년의 인터넷은 야생이었습니다

첫 발상: 계산기를 쓰자

매번 더하기를 입력할 필요 없이 곱하기 2를 하면 됨
집념의 초등학생은 결국 이런 화면을 보고야 맙니다…

35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
1.801439850948198e+16

결과는 재구성된 이미지

초딩키파에게도 명확하게 보이는 두 가지 의문

정수를 곱해서 정수밖에 나올 수가 없는데 갑자기 웬 소수점?
뒤에 붙은 e+16은 뭐야?

두 가지의 의문을 해결하지 못한 채 계산기가 틀렸다고 생각하게 됨
믿을 것은 컴퓨터밖에 없다!

플래시 게임을 만들던 '재주'로 C언어를 이용해 코딩을 시작

다행히도 제가 배우던 C언어 책에는 int의 최대 크기가 10자리라고 잘 가르쳐 주었음

계산을 하려면, 내가 하려던 곱셈 방법을 컴퓨터에게 가르쳐 주면 되겠다!
약간의 시행착오 끝에 다음과 같은 결과를 얻게 됨

1
2
4
8
16
32
64
128
256
512
124
248
496
8192
16384
32768
65536
13172
262144
524288
148576
297152
419434
838868
16777216
33554432
6718864
134217728
268435456
53687912
173741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
27487796944
549755813888
199511627776
219923255552
43984651114
8796932228
1759218644416
3518437288832
7368744177664
14737488355328
28147497671656
562949953421312
112589996842624
2251799813685248
45359962737496
9719925474992
181439859481984
362879718963968
725759437927936
14411518875855872
28823376151711744
5764675233423488
11529215466846976
2358439213693952
46116861842738794
92233723685477588
184467447379551616
3689348814741913232
7378697629483826464
147573952589676412928
29514795179352825856
592958135875651712
1185916271741133424
236118324143482266848
4722366482869645213696
944473296573929427392
1888946593147858854784
3777893186295716179568
75557863725914323419136
151115727451828646838272
3223145493657293676544
64462998731458735388
12892581961462917476176
2417851639229258349412352
48357327845851669882474
9671465569173339764948
1934281311383466795298816
3868562622766813359597632
77371252455336267181195264
154742549167253436239528
3948598213456872478156
618971964269137449562112
1237943928538274899124224
247588785776549798248448
49517615714152199596496896
9935231428342199192993792
1987462856684398385987584
3961481257132168796771975168
7922816251426433759354395336
15845632528528675187879672
3169126557573537417581344
6338253114114774835162688
1267656228229414967325376

결과는 재구성된 이미지

열심히 옮겨 적다가 무언가 이상한 것을 발견

512 다음 수가 124 – 512보다 작아질 수 있나?
전체 결과를 보았을 때에도 중간에 움푹 들어가는 곳이 있음
자릿수가 작아지는 것은 불가능함!

곧 원인을 발견하게 됨

맨 앞의 0을 출력하지 않으려고 모든 0을 출력하지 않았던 것
이 부분을 고쳐 맨 앞 0만 출력하지 않도록 만들어 다시 돌림

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904
9223372036854775808
18446744073709551616
36893488147419103232
73786976294838206464
147573952589676412928
295147905179352825856
590295810358705651712
1180591620717411303424
2361183241434822606848
4722366482869645213696
9444732965739290427392
18889465931478580854784
37778931862957161709568
75557863725914323419136
151115727451828646838272
302231454903657293676544
604462909807314587353088
1208925819614629174706176
2417851639229258349412352
4835703278458516698824704
9671406556917033397649408
19342813113834066795298816
38685626227668133590597632
77371252455336267181195264
154742504910672534362390528
309485009821345068724781056
618970019642690137449562112
1237940039285380274899124224
2475880078570760549798248448
4951760157141521099596496896
9903520314283042199192993792
19807040628566084398385987584
39614081257132168796771975168
79228162514264337593543950336
158456325028528675187087900672
316912650057057350374175801344
633825300114114700748351602688
1267650600228229401496703205376

결과는 재구성된 이미지

열심히 옮겨 적어서 열심히 외움

당시에는 50승까지 외우고 포기, 지금은 30승도 안 외워질 듯합니다 😅

컴퓨터를 돌려 얻은 결과에서 몇 가지 이상한 점을 발견할 수 있었음

관찰 1: 수를 적어 놓은 형태가 선을 따라 가는 것 같음

무슨 선을 따라갈까?
정말로 선을 따라가는 것이 맞다면, 몇 배인지 어떻게 알 수 있을까?
선분이 원점을 지나지 않지만 대충 그래 보이니 그렇다고 과격하게 가정

이를 위해서 아주 큰 2의 자승만을 빠르게 계산할 필요가 있었음

100만 승을 계산해 보기로 결정 – 잘 안 됨
1만 승을 계산한 결과로 2의 \(n\)승의 길이는 \(n\)의 \(0.3011\)배라고 잠정적 결론
비슷한 생각을 한 사람이 있을까 싶어 \(0.3011\)로 열심히 검색해 보았지만 잘 안 나옴

⋮
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
⋮

결과는 재구성된 이미지

관찰 2: 끝 자리가 반복되는 것 같음

2, 4, 8, 6, …
2를 곱할 때의 "계산 과정"을 통해 쉽게 증명할 수 있었음

더 일반적인 것 – \(n\)으로 나눈 나머지 – 도 가능할까?

진법을 바꾸면 가능!
\(n\)으로 나눈 나머지를 연산하는 것은 \(n\)진법에서 비슷한 짓을 하는 것

인류는 계산을 못하도록 발전함

인류는 극도로 사회적인 동물
누구 얼굴/목소리인지 알아보는 것은 배우지 않아도 익히게 됨
20년 간의 수련을 거쳐도 233 곱하기 67을 순식간에 계산하는 것은 힘듦

눈에 보이지 않는 것을 상상하기 위해서는 먼저 눈에 보여야

폭우가 쏟아지면 왜 "하늘이 노했다"라고 하는가?
– 비가 하늘에서 떨어지기 때문!
인류의 상상력은 볼 수 있는 것에 극도로 제약되어 있습니다

컴퓨터는 과학 세계를 들여다보는 "사진기"

과학 세계의 기초 능력인 "계산"이 빠름
각 물체를 직접 보고도 관계를 유추하는 "추론" 능력이 없음

이 "사진기"를 과학 세계를 들여다보는 "눈"처럼 사용할 수 있다면 좋을 것입니다!

뛰어난 "사회적 관계" 지능을 통해 과학적 대상들을 정복해 나가자!
어릴 때 했던 행동들이 (당시에는 몰랐으나) 정확히 그런 행동

고등학생 이후의 키파

과학 세상을 탐색하는 수단으로서의 컴퓨터

고딩키파는 수학을 재밌어하기 시작했음

그새 log를 배워 \(\log_{10} 2 \approx 0.3010\)을 통해 의문을 해소함
선행 및 미적분학, 선형대수학, 해석개론 책을 사서 공부함
당시 학교에 Taylor expansion을 "전도"하고 다님

탐색의 도구 및 방향이 훨씬 넓어짐

WolframAlpha, desmos 등의 도구를 사용할 수 있게 됨
백준도 알게 되어 시작하게 됨

고등학생 때는 큐브에 빠져 있었음

특히 "최소 회전"을 하며 면의 이동이 제약된 경우에 관심이 있었음
마주 보지 않는 두 면만 돌리는 경우가 까다로웠음

구체적으로, 귀퉁이의 위치를 놓는 제약이 대단히 까다로웠음

세 개의 귀퉁이를 아무데나 넣을 수 있어서 가능한 위치는 120가지 이상
그러나 세 개의 코너를 지정하면 나머지 세 개의 귀퉁이가 자동으로 결정되는 것처럼 보임
어디에서 이런 차이가 발생하게 된 걸까?

두 개의 회전을 오른면 회전(R)과 윗면 회전(U)로 잡고 가능한 경우를 중복 없이 전부 열거

구현을 하려고 보니 큐브 회전을 다 구현하는 것은 귀찮음
귀퉁이에 대해 회전은 \(\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}\)과 \(\begin{pmatrix}3&4&5&6\\4&5&6&3\end{pmatrix}\)처럼 볼 수 있었음

코딩을 하고 열심히 돌려 보았는데…

120
123456
124563
125634
126345
132546
134625
135462
136254
⋮

결과는 재구성된 이미지

총 120개인 것을 확신함

사실 모두 열거했으므로 이대로 끝내도 되긴 함
수학적인 관찰을 좀 더 해 보고 싶었음

세 개의 귀퉁이를 잡으면 이중 0개가 변하는 경우가 없음

아무거나 세 개의 귀퉁이를 잡음
원래대로 돌아왔을 때 얘네들이 영향을 받는 이동의 개수를 세어 보자!

1-v 2-v 3-v
26  86  42
37 134  43
40 142  32
15  58  15
32  74  36
28  32  14
⋮

결과는 재구성된 이미지

몇 가지 사실을 관찰할 수 있었음

2개의 영향을 받는 무브는 항상 짝수 번?
1개 혹은 3개의 영향을 받는 무브는 합쳐서 항상 짝수 번?

놀랍게도 이 관찰만으로 원하던 사실을 증명해내는 데에 성공함

고등학교 2학년 때 이 관찰만으로 고등학교 소논문 상을 휩쓸었음
자세한 내용이 궁금하신 분들은 이곳에서…

우리 모두는 무엇을 찾아야 하는지 잘 모른다

"카메라"로 세상을 보는 것의 한계 – 렌즈에 맺힌 상밖에 보이지 않음
앞 두 슬라이드를 순식간에 설명했지만, 두 장 사이에는 3개월의 시간이 있음
다양한 도구를 익힌 것은 좋았지만, 눈이 보이지 않으면 무슨 쓸모?

보고자 하는 것은 찾아야 보인다

빨간 차 이론 – 찾고자 하는 것이 있어야 비로소 눈에 들어온다
무엇을 찾아야 하는지 어떻게 훈련할 수 있을까?

PS키파

무엇을 보아야 하는지를 찾는 실력을 키우자

중학교 3학년 때부터 백준을 시작함
컴퓨터로 세상을 들여다보는 "관찰 능력"을 키우는 데에 문제풀이만한 것이 없음

내가 머리 쥐어짜 만들어낼 필요가 없는 문제 상황
명확하게 정의된 입력 및 시간 제한
맞았는지 틀렸는지에 대한 즉각적인 평가

제가 개인적으로 훈련하는 데 좋겠다고 생각한 문제를 소개합니다

길이 \(N\)인 수열 \(\{a_{i}\}\)에 대해 \(\gcd(a_{i}, a_{j})\)의 \(N^{2}\)개 항이 순서 없이 주어짐
원래 수열로 가능한 것을 아무거나 하나 복원
벌써 아이디어가 잡히시나요? 저도 솔직히 잘 모르겠었습니다
이럴 때는 무작정 해 보기가 가능

일반적인 것을 해 볼 수도 있고, 특이한 것을 해 볼 수도 있음
손으로 해 볼 수도 있고, 코드로 해 볼 수도 있음

앞서 설명하였듯 사람은 계산을 너무 못함
이걸 뇌로 빠르게 잘 하면 사실 대회 성적이 올라요

import random, math

def main():
  n = 4
  for _ in range(10):
    l = [random.randint(1, 30) for _ in range(n)]
    r = [math.gcd(x, y) for x in l for y in l]
    print(l, r)

if __name__ == '__main__':
  main()

수열이 주어지면 문제의 \(N^{2}\)개 항을 뽑아 주는 코드 작성

[28, 26, 25, 10] [28, 2, 1, 2, 2, 26, 1, 2, 1, 1, 25, 5, 2, 2, 5, 10]
[26, 15, 12, 27] [26, 1, 2, 1, 1, 15, 3, 3, 2, 3, 12, 3, 1, 3, 3, 27]
[27, 3, 1, 27] [27, 3, 1, 27, 3, 3, 1, 3, 1, 1, 1, 1, 27, 3, 1, 27]
[11, 5, 13, 25] [11, 1, 1, 1, 1, 5, 1, 5, 1, 1, 13, 1, 1, 5, 1, 25]
[4, 10, 22, 14] [4, 2, 2, 2, 2, 10, 2, 2, 2, 2, 22, 2, 2, 2, 2, 14]
[17, 2, 12, 23] [17, 1, 1, 1, 1, 2, 2, 1, 1, 2, 12, 1, 1, 1, 1, 23]
[3, 3, 8, 5] [3, 3, 1, 1, 3, 3, 1, 1, 1, 1, 8, 1, 1, 1, 1, 5]
[28, 11, 16, 3] [28, 1, 4, 1, 1, 11, 1, 1, 4, 1, 16, 1, 1, 1, 1, 3]
[6, 3, 30, 6] [6, 3, 6, 6, 3, 3, 3, 3, 6, 3, 30, 6, 6, 3, 6, 6]
[29, 22, 7, 14] [29, 1, 1, 1, 1, 22, 1, 2, 1, 1, 7, 7, 1, 2, 7, 14]

계산 결과에서 관찰할 수 있는 것이 있을까요?

가장 큰 수가 눈에 띕니다

이 사실을 정당화할 수 있나요?
\(\gcd(a_{i}, a_{j}) \leq a_{i}\)이고 \(\gcd(a_{i}, a_{i}) = a_{i}\)이므로!

변환된 수열의 수의 크기와 관련이 있을 것 같다는 아이디어를 얻을 수 있습니다!

그러면 가장 큰 \(N\)개 항을 뽑으면 그게 답일까요?

예제가 그렇지 않아 보입니다: \(6\)과 \(3\)이 있으면 얘네들끼리만 \(6\), \(3\), \(3\), \(3\)을 만들어내므로.

그러면 현재까지의 정보로 만들 수 있는 수를 수열에서 제거하면 되지 않을까요?

\(6\)과 \(3\)을 알게 되었다면 그 정보로 \(6\), \(3\), \(3\), \(3\)을 제거

여기서 조금만 더 발전하면 맞을 수 있는 풀이가 나옵니다!

관찰을 사람이 하기 힘들 때, 관찰하는 단순한 코드를 짜서 컴퓨터에게 시킬 수 있습니다

2의 자승을 계산하게 했던 초딩키파와 큐브를 돌리게 했던 고딩키파처럼

실제 PS 상황에서 확신을 갖고 정답을 제출하고 싶다면 수학적 귀납법이 강력합니다

재귀가 강력한 이유와 같습니다 – 부분문제가 옳다는 가정 하에 이를 신경쓰지 않을 수 있게 해 줌
수학적 귀납법의 유일한 단점이 "옳은 명제"가 하늘에서 뚝 떨어진다는 것 – 이를 관찰로 보완하는 구조

열심히 코드를 짰는데 "틀렸습니다"를 받으면 얼마나 속상한가요 😔
스트레스는 어렵게 짠 코드의 버그를 잡기 위해 쉽게 짰지만 느린 구현과 배틀시키는 것
참고: 출제자로서는 문제를 만들 때 더 쉬운 풀이가 있다면 필수로 해 주어야 하는 작업

출제자는 본인이 짠 코드가 맞는지 아닌지를 확인할 방법이 극히 적음
가능하다면 스트레스를 포함해 다양한 방법으로 확인하는 것이 좋음

사실 이것은 "PS 지식"이 아니어서 대부분 이미 알고 계실 거라 생각했는데, 많이들 모르시는 것 같습니다
방법 1: 프로그램 안에서 모든 것을 해결하기

배열 초기화 등을 굉장히 잘 해 준 상태에서, 원래 코드를 solve 등의 함수로 감쌉니다
같은 파일에 naive 등의 함수를 작성합니다
입력을 잠시 주석 처리한 다음, solve와 naive의 결과를 비교하는 코드를 짭니다

생각할 것은 많지만, 스트레스 속도가 빠릅니다

방법 2: system call을 적극 활용하기

C++의 system, Python의 os.system을 적극 활용합니다
프로그램 실행은 다음과 같이 가능합니다:

윈도우의 경우 .\program.exe < input.txt > output.txt
맥 및 리눅스의 경우 ./program < input.txt > output.txt

입력 파일의 단순 비교는 맥 및 리눅스의 경우 diff file1.txt file2.txt

윈도우는 직접 짜야 합니다

중요한 것은 컴퓨터와 협업하려는 마음가짐

빠른 연산이 필요한 것이 있으면 컴퓨터에게 물어보기
계산 결과로부터 유의미한 결론을 도출해 내려고 노력하기

발표가 문제풀이에 컴퓨터를 적극적으로 활용하려는 데에 도움이 되었으면 좋겠습니다

감사합니다!