문제 algospot.com/judge/problem/read/GALLERY algospot.com :: GALLERY 감시 카메라 설치 문제 정보 문제 전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 algospot.com 풀이 종만북 난이도: 중 이번 문제를 해결하는 힌트는 문제 속에 있다. 미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며, 모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다. 방문한 갤러리(노드)를 다시 가기 위해서는 지나왔던 복도(간선)를 지나야 한다는 것은 미술관 구조(그래프 구조)에 사이클..

문제 https://algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 algospot.com 풀이 종만북 난이도: 하 DFS로 오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)을 구현하는 문제. 오일러 서킷(Eulerian curcit) 오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시작 노드로 돌아오는 경로를 의미한다. 오일러 서킷을 만족시키는 그래프는 모든 노드가 짝수의 간선(edge)를 갖는 경우이다..

문제 https://algospot.com/judge/problem/read/DICTIONARY algospot.com :: DICTIONARY 고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 algospot.com 풀이 종만북 난이도: 하 책에서는 쉬운 난이도로 분류되었지만 사실 위상 정렬(topological-sort) 자체는 난이도 있는 알고리즘이라 생각한다. 특히 책에서는 간단히 DFS방식의 위상 정렬을 다루었지만 큐를 사용한 위상 정렬 방식이 좀 더 자주 사용되는 듯하니 둘 다 알아 두자. 일단 이번 문제는 DFS방식의 위상 정렬로 해결해보자. 입력은 사전 순..

문제 https://algospot.com/judge/problem/read/EDITORWARS algospot.com :: EDITORWARS 에디터 전쟁 문제 정보 문제 에디터 전쟁은 가장 유명한 자유 소프트웨어 텍스트 편집기인 vi와 Emacs 중 어느 쪽이 더 우월한가를 놓고 인터넷에서 자주 벌어지는 논쟁을 말합니다. 이 논쟁에 참 algospot.com 풀이 종만북 난이도: 중 분리 집합(Disjoint Set, 종만북에서는 상호 배타적 집합으로 해석되어 있다.) 문제는 처음이라 상당히 애먹었다. 분리 집합 문제들에서 사용하는 자료구조인 유니온-파인드(Union-Find)를 적절히 수정해서 풀어야 하는 문제이다. 파티에 올 수 있는 사람수를 구하기 위해 집합의 크기를 저장하는 것은 set_siz..

문제 https://www.algospot.com/judge/problem/read/MEASURETIME algospot.com :: MEASURETIME 삽입 정렬 시간 재기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 www.algospot.com 풀이 종만북 난이도: 중 세그먼트 트리와 같은 기능을 하지만 비트 연산을 이용해 좀 더 간단히 구현이 가능한 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)로 해결하는 문제이다. 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는 데 특화되어 있다. 만..

문제 https://algospot.com/judge/problem/read/FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 algospot.com 풀이 종만북 난이도: 상 최소 공통 조상(Lowest Common Ancestor, LCA)를 세그먼트 트리로 풀어보는 문제이다. LCA의 구현에는 단순한 구현과 최적화를 거친 구현이 존재한다. 단순 구현: 백준 - LCA(11437) - Gold 3 최적화 구현: 백준 - LCA 2(11438)★ - Platium 5 하지만 이번에는 세그먼트 트리를 이..

문제 https://algospot.com/judge/problem/read/NERD2 algospot.com :: NERD2 너드인가, 너드가 아닌가? 2 문제 정보 문제 대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 algospot.com 풀이 종만북 난이도: 중 STL의 map 자료구조를 이용하면 직접 이진 검색 트리를 구현하지 않아도 풀 수 있다. map은 key와 value 쌍을 pair자료구조로 저장한다. 이때 value들은 key값을 기준으로 이진 검색 트리에 정렬되어 저장된다. 너드 지수를 구하는 값 p와 q를 아래와 같이 2차원으로 나타내 보자. 참가자 4명의 너드 지수가 (p,q) 1.50,..

문제 https://algospot.com/judge/problem/read/FORTRESS algospot.com :: FORTRESS 요새 문제 정보 문제 중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로 algospot.com 풀이 종만북 난이도: 중 기하적인 문제 같아서 어려워 보이지만 성벽들은 서로 겹치거나 닿지 않기 때문에 모든 성벽들은 서로의 포함관계로 즉, 계층구조인 트리로 나타낼 수 있다. 성벽을 트리로 나타내면 문제의 답은 간단히 보인다. 바로 서로 가장 먼 두 노드 사이의 간선 수(경로)가 두 지점을 이동하기 위해 가장 많이 넘어야하는 성벽 수이다. 성벽을 가장 많이 넘..

문제 https://algospot.com/judge/problem/read/ITES algospot.com :: ITES 외계 신호 분석 문제 정보 문제 수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000 algospot.com 풀이 종만북 난이도: 중 큐를 사용하여 해결하는 문제. 신호의 기록은 입력값으로 주어지는 것이 아니라 직접 생성하는 문제이다. 특이 신호의 개수 N은 최대 50,000,000이므로 생성하여 저장하기보단 각 테스트 케이스마다 다시 생성하여 사용하는 것이 메모리를 절약할 수 있다. 우리는 신호의 수열에서 부분 연속 수열의 원소합이 K인 부분 수열의 개수를 찾아야..

문제 https://algospot.com/judge/problem/read/PASS486 algospot.com :: PASS486 비밀번호 486 문제 정보 문제 재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 "no-smok**X**" 와 같이 정하는데, 여기서 X algospot.com 풀이 종만북 난이도: 중 에라토스테네스의 체를 활용한 소인수 분해를 이용해야해서 어려웠던 문제이다. 특히 소인수 분해까지는 구현해도 수학적인 최적화를 진행하지 않으면 제 한 시간 안에 맞출 수 없다. 해당 문제에서 사용되는 에라토스테네스의 체와 소인수 분해는 아래 링크에서 확인하자. 에라토스테네스의 체와 소인수 분해 어떤 수n의 약수의 개수를 ..