Larshew's Diary Larshew's Diary

어느 정도 수준있는 문제에서 많이 쓰이는 문제이다. 이 알고리즘이 메인이 된다기보다는, 다른 알고리즘(Tree DP 등등)과 짬뽕해서 조미료로 쓰이는 경우가 굉장히 많다. 최소 공통 조상이란? 다음과 같이 루트(위 그림에서 1번)가 있는 트리가 있을 때, LCP(a,b)는 a와 b를 모두 자식으로 가지는 노드들 중에서 a와 b에 가장 거리가 짧은 조상을 말한다. 예를 들어 LCP(7,9)=2, LCP(10,12)=6, LCP(7,10)=1이 된다. a가 b의 조상인 경우, 혹은 그 역인 경우 LCP의 값이 a 혹은 b가 될 수 있다(ex. LCP(7,1)=1) 일반적으로 LCP(a,b)의 쿼리가 Q개 있는 경우 DFS, BFS 등 일반적인 Search Algorithm을 사용하면 O(NQ)가 걸릴 것이다..

Suffix Array란 무엇인고? 항상 String 관련 알고리즘에 자주 등장하는 바나나의 예시를 들어보자. S = "banana" Suffix라고 함은 접미사라는 뜻인데, 끝에서부터 한 글자, 끝에서부터 두 글자 이렇게 해서 전체 글자까지 나타낼 수 있다. a - 5 na - 4 ana - 3 nana - 2 anana - 1 banana - 0 이 친구들을 사전순으로 정렬하면 a - 5 ana - 3 anana - 1 banana - 0 na - 4 nana - 2 가 된다. 이 때, [5,3,1,0,4,2]를 저장한 Array를 Suffix Array라고 한다. 어떻게 구현해? 당연히, 조금만 생각하면 O(N^2 logN) (Naive Sort), O(N^2) (Trie) 정도는 바로 생각해낼 수..

말러가 피아노 4중주를 작곡했다고? 말러라고 하면 보통 교향곡을 먼저 떠올리는데, 그래서 그런지 피아노 4중주는 굉장히 생소하다. 이 곡은 말러가 유년기 때 작곡했던 것들 중 거의 유일하게나마 남아있는 곡이며(나머지는 말러가 우울증 때문에 다 불태워버림), 가족을 잃어버린 슬픔 때문에 전반적으로 굉장히 침울한 분위기이다. 화성적으로 보더라도 단9도, 감5도와 같은 선율진행이 자주 나오며, 반음계적 진행 또한 자주 나온다.

피아노 실력이 안 되는 사람이 어려운 곡을 하면 벌어지는 일 1 피아노 트리오 중에서도 아름답고 감성적인 멜로디로 손꼽히는 곡이다. 직관적인 바이올린, 첼로 선율이 처음 듣는 사람도 쉽게 이해할 수 있고, 곡의 구성도 베베 꼬인 소나타 형식이 아니라 직관적인 소나타 형식이라 고전파 음악을 들을 때 처럼 알아듣기도 굉장히 쉽다. 멘델스존의 곡들은 뭔가 "깝치는" 듯한 반주를 참 잘하는 것 같다. 멜로디는 단순한 데 반해 반주가 굉장히 정신없다. 이 곡도 (정템포 기준)오른손이 1초에 약 12번을 후갈기는 피아노 반주가 나를 반기고 있었다. 요란하고 정신없는 반주가 멜로디만으로는 부족한 불안감을 한층 더 고조시키지만, 피아노 자체가 부각되는 일은 그다지 많이 없다. 그래서 피아노 연주자들이 이 곡을 많이 싫..

문자열 알고리즘의 대표적인 알고리즘 되시겠다. Knuth–Morris–Pratt 세 명의 첫 글자를 따서 KMP라고 불린다. 어디에 쓰는 알고리즘인고? 우리가 네이버나 구글에 검색어를 치면 검색어가 포함된 게시글을 바로바로 보여준다. 세세한 것은 다르겠다만, “banana”라는 글자를 치면 바로 “banana” 키워드가 있는 게시물을 보여준다. 게시물 하나하나에 banana가 들어가있는지 검색해줄 뿐만 아니라 banana 단어에 bold로 표시하면서 게시물에 banana가 있음을 우리에게 확인시켜주고 있다. 이를 빨리 해결하는 데 쓰는 알고리즘이 바로 KMP algorithm 되시겠다. Brute Force 알고리즘 – O(NM) S1 = “I love apple and banana” S2 = “bana..

군 내에서 코딩공부를 하기란 굉장히 쉽지 않은 일이다. 기본적으로 보안 때문에 컴퓨터 등 전자기기와 접하기가 굉장히 어려우며, 선임 등 다른 사람들의 눈치도 많이 봐야 하기 때문이다. 다행히도, 공군에서는 태블릿을 학습 목적으로 반입하는 것을 허용한다. 하지만 군대에 반입하고 나서는 인터넷에 연결할 방법이 없으므로, 휴가 때 깔아놓고 오프라인 환경에서 유용하게 사용할 수 있는 앱들을 몇 가지 적어보겠다. 안타깝게도 iOS의 경우 인터넷에 연결하지 않고 태블릿 내에서만 구동할 수 있는 어플이 몇 없다. 그래도 그나마 인터넷 연결 없이 쓸만한 여러 앱들을 소개하겠다. 1. Pythonista 3 iOS에서 현재 있는 거의 유일무이한 쓸만한 IDE라고 생각한다. 만원 조금 넘었던 것 같은데, 그래도 제 값을 ..

0. 나는 군대를 너무 가기 싫었다. 대학교 2학년 때부터 나는 군대를 가는 것을 굉장히 미뤄왔었다. 가장 큰 이유는 "내 청춘을 버리는 것을 아까워서." 그렇게 나는 졸업 한 학기를 남길 때 까지도 군대를 미뤄왔었다. 물론 전문연을 가야겠다고 생각은 많이 했지만 막상 대학원이라는 큰 문을 두니 그 또한 엄두가 나지 않았다. 4년간 대학을 다녀보았을 때 공부를 하는 것은 나쁘지 않긴 하지만(어쩌면 나는 공부보다 더 잘할 수 있는 것은 없을 것 같다) 24시간 중 12시간 이상을 투자할 만한 곳은 아니었던 것 같다는 생각 때문에 결국 도피성으로 선택한 곳이 공군이었다. 결과적으로 군대를 이렇게 늦게 간 선택은 천운이 따른 것 같다! DP에서 보여준 그런 군대에 가게 되었다면 나는 백이면 백 적응하지 못했을..

0. 서론 일본 쪽 회사에 갈 것도 아니고 굳이 써먹을 데 있다면 일본어 원어로 된 만화나 소설책을 읽고 애니메이션을 자막없이 어느정도 이해할 수 있는 수준? 이라 처음에는 생각이 없었다가, 동기가 일본어 공부를 하는 것을 보고 "일본어를 공부할 수 있는 시간은 군대에서밖에 없을 것 같다!" 라고 생각하고 JLPT를 공부하게 되었습니다. 평소에 애니메이션을 조금씩 봤었기에 완전히 노베이스는 아니었지만(그렇다고 해서 자막없이 볼 수준인가 하면 그건 또 아님) 히라가나 가타카나도 안 배운 상태였기 때문에 적어도 언지(언어지식)이나 독해 쪽으로는 노베이스라고 해도 무방할 정도였습니다. 이렇게 생각했을 때가 3월말때였던 것 같습니다. 동기한테서 먼저 N5책을 달라고 했었고, 실제로 본격적으로 책을 보게 된 것은..