천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

스패닝 트리 (Spanning Tree) ? 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 아래와 같은 예시들이 스패닝 트리라고 할 수 있다. 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 또한, 트리 형태여야 한다는 말은 선택된 간선이 사이클을 이루지 않는다는 의미여, 정점들이 부모-자식 관계로 연결될 필요는 없다는 것이다. 최소 스패닝 트리 (MST, Minimum Spanning Tree) ? 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다. 최소 스패닝 트리를 구할 수 있는 알고리즘은 두 가지가 있다. 크루스칼 (Kruskal) 알고리즘 : Kruskal Algorithm 프림 (Prim) 알고리즘 프림 (Prim) 알고리즘 크루스..

스패닝 트리 (Spanning Tree) ? 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 아래와 같은 예시들이 스패닝 트리라고 할 수 있다. 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 또한, 트리 형태여야 한다는 말은 선택된 간선이 사이클을 이루지 않는다는 의미여, 정점들이 부모-자식 관계로 연결될 필요는 없다는 것이다. 최소 스패닝 트리 (MST, Minimum Spanning Tree) ? 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다. 최소 스패닝 트리를 구할 수 있는 알고리즘은 두 가지가 있다. 크루스칼 (Kruskal) 알고리즘 프림 (Prim) 알고리즘 : Prim Algorithm 크루스칼 (Kruskal) 알고리즘 크..

오픈채팅방 문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들..

소수 (Prime Number) ? 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다. 소수의 반대말로는 합성수가 있다. 합성수 (Composite Number) ? - 세 개 이상의 양의 약수를 갖는 자연수. 소수 판별 주어진 수 n이 소수인지를 판단하는 가장 단순한 방법은 2부터 n - 1 까지의 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인하고, 약수가 없다면 소수란 사실을 알 수 있다. 여기에 합성수 n이 p x q로 표현될 때 한 수는 항상 √n 이하, 다른 한 수는 √n 이상이라는 점을 이용하면, n - 1 까지 순회하지 않고 √n까지만 순회하도록 최적화할 수 있다. O(√n)의 시간복잡도로 동작하는 소수 판별 알고리즘 1과 2는 예외로 처리한다. 2를 제외한 모든 짝수는 소수..

접미사 배열 (Suffix Array)? 어떤 문자열 S (아래의 경우 "alohomora") 의 모든 접미사를 사전순으로 정렬해 둔 자료구조이다. 접미사들을 그대로 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 보통 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. i A[i] S[A[i]] 0 8 a 1 0 a l o h o m o r a 2 3 h o m o r a 3 1 l o h o m o r a 4 5 m o r a 5 2 o h o m o r a 6 4 o m o r a 7 6 o r a 8 7 r a 접미사 배열을 이용한 문자열 검색의 핵심은 '짚더미 H'가 '바늘 N'을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한다. ex) "al..

문제 입출력 형식 입출력 예제 솔루션 KMP 알고리즘을 그대로 구현하면 되는 문제이다. KMP : https://soobarkbar.tistory.com/80?category=824428 제출할 때 주의할 점은 인덱스가 1부터 시작하므로, 패턴 인덱스를 찾았을 때 +1이 아닌 +2를 해준다. 피드백 pi배열을 만들 때 (getPi의 for 반복문), i는 1부터 수행 해야 한다 (0부터 수행 했음). KMP에서 pi배열을 만들기 위한 파라미터로 패턴 문자열 (pattern) 전달 해야 한다 (전체 문자열인 text를 전달했음). Code 전체 코드 : Code 실패 함수 (Failure Function) 인 pi 배열을 얻는 함수 (getPi). 문자열에서 특정한 패턴이 위치한 인덱스를 얻는 함수 (KM..

문제 조건 입출력 예제 솔루션 Trie (트라이) 자료구조를 사용한다. 트라이 : https://soobarkbar.tistory.com/71?category=824429 Why 트라이 ?) 검색속도가 빠르기도 하고, 문자열의 끝을 알려주는 isEndofNumber를 통해 접두사인지를 확인할 수 있기 때문. 위 URL과의 차이점 TrieNode 클래스의 isExistedChildren() 함수. Trie 클래스의 isPrefix(String key) 함수. 코드 설명 Trie 객체를 생성한다. Trie에 입력으로 주어진 phone_book 문자열들을 모두 삽입한다 (Insert). 모두 삽입된 Trie에 대해 다시 처음부터 phone_book의 문자열들에 대해 접두사 (Prefix) 인지 확인하는 작업 ..

문제 조건 입출력 예제 솔루션 본인이 생각한 방법은 아래와 같다. 모든 문자열이 알파벳 대문자로만 구성되어 있으므로, 길이가 26 (알파벳 갯수) 인 boolean 배열을 만들어서 처리해보자. 유저들이 만든 스킬트리의 문자를 조회하며, 이 스킬이 가능한지를 possible 배열을 조회한다. 가능하다면 문자열 끝까지 여부를 확인하고, 가능하지 않다면 중단한다. 코드 설명 길이 26의 배열 possible을 만들고, 모두 true로 초기화한다. skill (순서가 정해진 스킬) 의 첫 번째 문자를 제외하고 나머지 skill 문자의 possible을 false로 바꾼다. skill_trees (유저가 만든 스킬트리) 길이만큼 반복문을 수행한다. ispos는 스킬트리가 가능한지 여부를 체크하는 변수이며, cpp..