Dev_Diary

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 알고리즘입니다. 다만 큐를 사용한 BFS 방식이 아닌 진입차수가 0 인 노드 하나 추가 -> 연결된 모드 노드 진입차수 -1 -> 진입차수가 0 인 노드 하나 추가 가장 작은 노드가 입력될 수 있도록 해야합니다. import sys def solution(N, M, data_list): # 위상정렬 알고리즘 # 트리, tree[i] = [[i 의 자식들], ..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬을 사용해 풀어야 하는 문제입니다. 우선 바뀐 순서를 트리에 추가하고 나머지 순서는 바뀌면 안되므로 미리 추가된 순서들을 제외하고 트리에 추가해줍니다. 그런 뒤에 위상정렬 알고리즘을 사용하면 되는데, 큐에 노드가 2개 이상 들어있다면 정확한 순서를 파악할 수 없으므로 '?' 를 출력합니다. 또 위상정렬 알고리즘을 모두 통과한 뒤에 생긴 새로운 줄에 속한 노드의 수가 전체 노드의 수와..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 알고리즘을 사용하면 풀 수 있습니다. 간단하게 설명하자면 어떤 노드를 방문하는데 조건이 있는 경우 위상정렬을 사용하게 됩니다. 특정 노드 A 를 방문할 때 B, C 를 선행 방문해야 한다고 가정하겠습니다. A와 B, A 와 C를 간선으로 연결하고, 각 노드에서의 들어오고 나가는 간선을 체크해줍니다. A : 나가는 간선 0 / 들어오는 간선 2 ..

https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조를 사용해 풀 수 있는 문제였습니다. 처음에는 현재 노드의 자식이 하나면 카운트를 스킵했지만 어떤 단어의 부분집합이 함께 사전에 포함되어 있는 경우, 예를 들어 hello 와 hell 이 같은 사전에 포함되어 있는 경우, hello 의 버튼 클릭 횟수를 카운팅 할 때 o 를 자동으로 누르게 되어 카운팅이 제대로 되지 않습니다. 그러므로 자식의 수 + (value 가 존재할 때 1 / va..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 해시를 사용하면 조금 더 쉽게 풀 수 있는 문제지만 트라이 자료구조 학습을 위해 트라이로 풀어보았습니다. def solution(N, M, S, data_list): # 트라이 trie = Trie() # 데이터 입력 for string in S: # 트라이 insert 함수 trie.insert(string) # 집합에 포함되는 데이터 수 data_count = ..

https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 트라이, Trie 라는 자료구조를 사용하는 기본 문제입니다. 트리 구조를 사용해 문자열 검색에 최적화된 자료구조 입니다. dev-diary 라는 문자열을 저장한다고 하면 d, e, v, - , d, i, a, r, y 를 순서대로 하위노드로 입력시키며 특정 문자열로 시작하는 문자열을 검색하기 쉽게 만듭니다. 구현은 클래스로 구현할 수 있으며 기본 구현과 문제를 위해 변형한 코드를..

https://www.acmicpc.net/problem/1305<figure id="og_1703250997520" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1305번: 광고" data-og-description="세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘을 사용하는 기본적인 문제입니다. 다만 시간 제한도 빡빡하고 KMP 알고리즘 자체의 난이도 때문에 플레티넘이 되어버린 문제입니다. 또 입력이 ' ' 처럼 공백으로 들어올 경우 입력을 받을 때 strip 처리를 해버리면 인덱스 오류가 날 수 있으므로 주의해야 합니다. 아래 코드에 디버깅 코드가 삽입되어 있으므로 복사해서 그래도 돌려보면 터미널에 과정이 나옵니다. 이를 코드와 비교..

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net CCW 알고리즘을 활용하면 풀 수 있는 문제입니다. def solution(x1, y1, x2, y2, x3, y3, x4, y4): # CCW 알고리즘은 기본적으로 주어진 점선들의 회전방향을 알 수 있음 # 어떤 직선을 기준으로 두 점이 양방향에 있으면 직선과 각 점을 이었을 때 회전방향은 반대임 # 각 선분을 기준으로 나머지 선분의 각 점이 이루는 회전방향이 모두 다르면 # 각 선분을 이루는 점은 나머지 선분을 ..

https://www.acmicpc.net/problem/25308 25308번: 방사형 그래프 게임 캐릭터의 능력치를 한 눈에 보기 좋게 나타내는 방법으로 방사형 그래프가 있다. 캐릭터는 8개의 능력치를 갖고 있고 각 능력치를 $a_1, a_2, \cdots, a_8$이라고 하면, 그래프는 팔각형 형태이고 www.acmicpc.net 특정 인덱스를 기준으로 왼쪽과 오른쪽의 각도 합을 통해 풀 수 있는 문제였습니다. from itertools import permutations import math def solution(data_list): # 데이터를 조합 permute_data = permutations(data_list, 8) # 카운트 count_convex = 0 # 인덱스를 돌아가면서 판단 ..