GitHubSeob

문제 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/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/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 문제풀이 전에 백준에서 풀었던 16496번 문제와 거의 같은 문제이다. 16496번 문제와 다른 점은 입력에 0이 없다는 점과 입력받은 수보다 뽑아야 하는 수가 더 많을 수도 있다는 점이다. 1~9까지는 큰 수가 무조건 좋고, 9와 10 같은 경우도 자릿수가 늘어나므로 어느 수가 들어오든 큰 수를 여러 번 뽑는 것이 좋다. 먼저 숫자를 입력받는다, 만약 숫자가 더 필요..

문제 https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 문제풀이 Compare함수를 만들어 조건대로 정렬하게 했다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다. 라는 문장인데 0이 딱 한번만 주어진다는것으로 이해했다. 하지만 0이 여러개 주어질수도 있다.0이 여러개면 0만 출력하고 끝나야하지만 문제를 잘못 이해해 0의 개수만큼 0을 출력했었다.그걸 고치고 나니까 바로..

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 문제풀이 버블 소트는 https://terms.naver.com/entry.naver?docId=2270437&cid=51173&categoryId=51173 버블 정렬 버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다. 버블 정렬의 동작 과정을 [그림 8-3]의 데이터를 이용해서 살펴보자. ① 첫 번째 term..