친구를 맺어주는 소셜 네트워크를 만든다고 하자. 친구 관계는 상호적이다. 이런 데이터를 가장 잘 조직하는 방법은 무엇일까? 한 가지, 매우 간단한 접근 방식은 2차원 배열로 친구 관계 리스트를 저장하는 것이다. 그러나 2차원 배열로는 A의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록을 전부 확인해야 하므로 O(N)이 필요하다. 그래프를 사용하면 A의 친구를 O(1)만에 빠르게 찾을 수 있다. 1. 그래프 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 1.1 그래프 대 트리 그래프는 앞서 다뤘던 트리와 비슷하다. 사실 트리도 그래프의 한 종류다. 모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다. 트리로 규정되는 그래프는 사이클이 없어야 하며, 모든 ..
스마트폰의 자동 완성 기능은 어떻게 동작할까? 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.(!) 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다. 1. 트라이 트라이는 프리픽스 트리Prefix tree 혹은 디지털Digital tree 트리라고도 부른다. 트라이는 명쾌하게 설명되지 않는다. 교재마다, 설명마다 트라이를 조금씩 다르게 구현한다. 1.1 트라이 노드 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다. 트라이 노드는 이진 트리와 다르게 자식 노드 개수에 제한이 없다. 이 교재의 구현에서는 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 키는 알파벳이고 값은 트라이의 다른 노드다. 즉, 해시 테이블에서 키는 개개 문자열이고 ..
안녕하세요. 3월 4일에 쓰는 2월 회고입니다. 원래는 2월 28일에 쓰려고 했는데 좀 아프기도 했고 바쁘기도 했어요. 날도 따뜻해지는데 감기에 걸리다니... 에이펙스 레전드 냅다 게임얘기로 서두를 열어볼까요? 지난 1월에 로스트아크를 결국 접었다고 했었는데요. RPG를 접으니까 시간이 갑자기 복사가 되기 시작했어요. 공부랑 스터디 이것저것 해도 시간이 남더라고요... 마침 에이펙스 레전드가 갓겜이 되었길래(원래 갓겜이었지만) 남는 시간에 열심히 하고 있습니다. 라이프라인 버프 체감이 엄청 크네요. 다시 다이아를 찍어볼까 했는데 그때 같이 랭겜을 돌렸던 듀오가 저를 브로큰문에 버려두고 현생을 살러 가버렸어요. 친구든 연애든 마음 맞는 사람 구하기가 쉽지 않죠. 게임친구도 그렇습니다... 아쉽지만 당분간은..
안녕하세요? 알고리즘 문제를 풀다가, 혹은 코딩 테스트를 보다가 얘네는 대체 어떻게 시간을 재는 건지 궁금했던 적이 있었어요. 아니 시간 초과라니 서버 CPU 구려서 그런 거 아니야? 내 로직에는 잘못이 없다! 방금 코테보고 킹받아서 쓰는 글 아닙니다. 아무튼 과연 어떻게 시간을 재는 걸까요? 오늘은 Kotlin에서 코드의 실행 시간을 어떻게 측정하는지에 대해 알아보도록 하겠습니다. Java 왜 갑자기 Java 꺼내오냐고요? Java나 Kotlin이나 어차피 바이트코드로 변환되어 JVM에서 돌아가는 건 똑같기 때문에 Kotlin에서 하고자 하는 것들은 대부분 Java에 먼저 구현되어 있답니다. Java에서 실행 시간을 측정하기 위해서는 두 가지 방법을 쓸 수 있습니다. 1. System.currentTi..
질문의 배경 최근 면접스터디를 진행 중인데요. 자료구조와 알고리즘 파트를 진행하면서 트리와 그래프의 차이, 이진 탐색 트리와 완전 이진 트리에 대한 질문이 나오면서 얘네한테 방향성이랄 것이 있는지에 대한 토론을 했답니다. 명확하게 결론이 날 줄 알았는데 구글링을 해 보니 그렇지 않았습니다. 한 다섯 개 정도의 블로그에서는 방향이 있다고 하고, 네 개 정도 블로그에서는 방향이 없다고 하더라고요. 진짜에요 이럴 수가… 아니 이런 Mr.애매모호가 싫어서 컴퓨터공학 왔다고 결론을 후다닥 말씀드리도록 하겠습니다. 트리는 방향 그래프로 볼 수도 있고, 무방향 그래프로 볼 수도 있다. 이딴 게 결론? 입니다. 정말 열받는 부분이죠? 이유에 대해 알아봅시다. 그래프 이론에서의 “트리” In graph theory, a..
