GitHubSeob

문제 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 문제풀이 위상정렬을 이용하여 풀었다. 진입차수 벡터를 만들어 진입차수가 0인 노드를 큐에 집어넣는다. 큐에서 pop을 하면서 해당 노드에서 다른 노드로 가는 간선들의 개수를 제거한다. 제거하는 도중, 다른 노드의 진입 차수가 0인 다른 노드가 있으면 큐에 집어넣는다. 노드 개수만큼 반복이 되지 않으면 사이클이 존재한다는 의미인데, 문제에서 A가 B앞..

문제 https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 문제풀이 색상은 트라이, 닉네임은 set을 이용해 풀었다. 처음에는 둘 다 해시로 풀어서 안되길래 라빈카프로 바꿔서 풀어봤는데도 안 됐다. 그래서 트라이 + 해시로 풀어봤는데 15%에서 계속 틀리길래 검색을 해봤는데 반례가 하나도 없길래 직접 생각해 봤다. 처음에는 트라이로 검색해 나가면서 isEnd가 true이면 break를 통해 색상은 더 이상 찾지 않고 나머지 문자열이 닉..

문제 https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 문제풀이 트라이 + DFS(백트래킹)로 풀었다. 입력이 들어오면 문자열들을 트라이로 구성한다. 그다음 DFS로 모든 경우의 수를 따지면 된다. unordered_setdict; unordered_settarget; int max_score; string max_str; vectorboard; vectorvisited; int dy[8] = { -1,-1,-1,0,0,1,1,..

문제 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제풀이 트라이 문제이다. 첫 글자를 제외하고 전 글자와 연결되는 이번 글자가 하나뿐이라면 버튼 입력 없이 자동으로 입력해 준다. 모든 단어를 입력할 때 버튼을 총 몇 번 눌러야 되는지를 단어 개수로 나누어 소수점 둘째 자리까지 출력하면 된다. 문제를 풀면서 메모리 초과와 출력 초과를 겪었다. 메모리 초과문제는 테스트케이스가 여러 개이기 때문에 한 테스트케이가 끝나면 소멸자를 통해 delete를 ..

문제 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 문제풀이 트라이 문제이다. 입력으로는 알파벳 대문자로만 이루어진 string이 들어온다. 트라이는 map을 이용하여 자녀 트라이를, 깊이를 나타내는 depth, 문자열의 끝 여부를 나타내는 isEnd로 구성하였다. void insert(vector& v) { Trie* now = this; for (int idx = 0; idx < v.size(); ++idx) { if (..

문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제풀이 최근에 swea에서 풀어본 문제랑 비슷해 보여서 도전해 봤다. 크루스칼 알고리즘을 이용해 풀었다. 메모리 초과가 발생해서 질문글을 보니 행성의 개수가 최대 100,000개라 N^2의 간선이 아닌 3*N의 간선으로 풀어야 한다고 했다. 해당 질문글을 참고하여 간선을 구하는 방법을 바꿨다. 터널을 연결할 때 드는 비용은 두 행성 간의 x의 차, y의 차,..

문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제풀이 다른 글을 보니 덱으로도 풀 수 있다고는 하는데 우선순위 큐로 풀었다. 이게 되나 싶었는데 통과가 됐다. 1부터 N까지 입력을 받으면서 idx-L+1번 숫자부터 현재 인덱스의 숫자까지 중에서 최솟값을 출력하기만 하면 된다. 우선순위큐를 이용해 항상 오름차순으로 정렬을 하도록 한다. 우선순위큐의 top부분의 인덱스가 필요한 부분의 인덱스가 아니라면 po..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제풀이 왼쪽 위를 1면, 오른쪽 위를 2면, 왼쪽 아래를 3면, 오른쪽 아래를 4면으로 둔다고 가정한다. 면을 계속 나누면서 해당 면의 최솟값을 더해 값을 구했다. N값을 입력받으면 시프트 연산을 통해 N을 2^N으로 바꾼다. 그다음 함수에서 N을 반으로 나누고 시작한다. (N을 가로 or 세로로 두어 y와 x의 위치를 비교하기 위함) 4면이 있기 때문에 네 가지 조건을 통해 어느..

문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제풀이 가장 작은 수 + 그다음 가장 작은 수를 더한다. 파일이 하나가 남을 때까지 반복만 하면 된다. 우선순위 큐를 이용해서 가장 작은 수가 top부분에 오도록 하면 편하다. 파일을 입력받고, 바로 우선순위 큐에 push 한다. 입력이 끝나면 우선순위 큐에 파일이 하나 남을 때까지 파일을 두 개씩 꺼내 더한 값을 다시 큐에 push 한다. 합칠 때 필요한 최소비용을 구해야 하므로 답 ..