![]()
문제 https://www.acmicpc.net/problem/9202 Algorithm 보드판의 각 지점에 대하여 DFS를 진행해 문자열을 만들어나간다. 현재까지 만들어진 문자열이 사전에 등재되어 있는 단어라면 최대 점수, 가장 긴 단어, 찾은 단어의 수를 갱신한다. 사전에 등재되어 있는 단어인 것은 어떻게 파악하는가? 사전의 단어들이 정렬되어 있을 필요는 없으므로, unordered_map 자료구조를 활용한다. 탐색 종료 조건은? 문제의 조건에 따라 단어의 길이는 최대 8글자이므로, 만들어진 문자열의 길이가 8을 초과한다면 종료한다. b개의 보드판을 탐색하게 되므로, 초기화에 주의한다. 또한, 이미 발견한 단어에 대해서는 map의 bool 값을 true로 표시한다. Code #include #incl..
문제 분석 해당 문제의 경우, 서로 다른 폰켓몬의 종류가 내가 선택해야 할 폰켓몬 보다 작을 경우에는 폰켓몬의 종류를 모두 고르고 부족한 폰켓몬은 중복된 종류의 폰켓몬을 선택하고, 내가 선택해야 할 폰켓몬 보다 크거나 같은 경우 서로 다른 폰켓몬을 모두 고르면 된다. 집합에 해당 배열의 폰켓몬을 넣어줌으로써 중복을 제거했다. 중복을 제거하면 입력받은 폰켓몬의 종류를 알 수 있다. 시간복잡도의 경우 set에 집어넣는 O(n)이 소요되므로, nums 길이의 최대값인 10,000 들어와도 충분히 시간안에 돈다. 문제 풀이 import java.util.*; class Solution { static Set set; public int solution(int[] nums) { int choiceNumber = ..
![]()
1718번: 암호 Vigenere cipher이라는 암호화 방법은 암호화하려는 문장 (평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변 www.acmicpc.net 문제코드 10, 11번째 코드를 작성하지 않고 실행했을 때 공백이 나와야 할 자리에 온점(.)이 나와 조건을 하나 추가해주었습니다.
완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..
![]()
1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 코드 코드 설명 n개 문서들의 중요도를 차례로 나열한 것을 큐인 dq에 받아 저장 dq를 복사한 큐 dqc 생성 몇 번째로 출력되는지 궁금한 문서의 위치가 m이므로 dqc 큐에 있는 m위치에 있는 문서의 중요도를 -1로 변경 중요도는 1이상 9이하 정수이고, max 함수를 사용할 것이기 때문에 중요도 변경 시 max 값에 걸리지 않기 위해 -1로 설정 중요도가 같은 문서가 있을 수 있으므로 dqc의 중요도만 변경하고 ..
![]()
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 작성하시오. 오목에서 승리했다는 것은 자신의 돌이 5개 이상 연속한다는 것이다. 연속은 가로, 세로, 대각선 방향 모두 가능하다. 입력 총 10개의 줄에 바둑판의 상태가 주어진다. ..
![]()
https://www.acmicpc.net/problem/15820 15820번: 맞았는데 왜 틀리죠? '테스트케이스(TestCase)'란 사용자가 제출한 코드가 옳은 답을 출력하는지 판단하기 위한 데이터다. 한 문제는 여러 개의 테스트케이스를 가지며, 문제를 '맞았다'는 것은 해당 문제의 모든 테스 www.acmicpc.net 문제 '테스트케이스(TestCase)'란 사용자가 제출한 코드가 옳은 답을 출력하는지 판단하기 위한 데이터다. 한 문제는 여러 개의 테스트케이스를 가지며, 문제를 '맞았다'는 것은 해당 문제의 모든 테스트케이스를 통과했다는 것을 의미한다. 즉, 하나의 테스트케이스라도 틀린다면 해당 문제는 틀린 것이 된다. 그림1. 실제 대회 시스템의 채점 방식을 나타내는 그림 테스트케이스 중 일..
![]()
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..
https://www.acmicpc.net/problem/7117 7117번: Sevens, twos and zeros The number s as described above must be output on the screen. If it is not possible to find the corresponding value of s to the given value of n, output one word "NAV". www.acmicpc.net 문제 분석 난이도 플래티넘5 분류 중간에서 만나기(MITM), 그래프 탐색, 너비우선탐색 들어가기 전에 중간에서 만나기 알고리즘을 알고 있어야 쉽게 풀 수 있는 문제 문제 최대 길이가 20이고 2, 7, 0으로 이루어진 0으로 시작하지 않는 수가 있다. 이 수들..
![]()
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 코드 문제 풀이 문제에서 가장 앞에 있는 문서의 중요도가 가장 높으면 바로 인쇄한다 = popleft 를 사용해야 하므로 deque 를 사용. for 문을 활용하여 T 만큼 반복, 반복문 내에서 N,M 과 N개의 문서 중요도 a를 입력. whlie을 활용하여 원하는 문서 a[M] 을 출력할 때 까지 반복. 1) a[M] 이 a의 맨 앞에 있을 때, 1-1) 이를 a의 가장 큰 수와 비교하여 a[..
문제 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생이 인접한..
![]()
문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 코드 풀이 입력되는 숫자를 모두 받아서 정렬하는 방법으로 코드를 짰는데 메모리초과만 나서 heapq를 쓰는 방안을 찾게 되었다. ㅇheapq의 크기가 5보다 크면 최솟값을 빼내고 입력받은 값을 집어넣고, 아니면 그냥 넣고 크키가 5일때와 그 이상일때로 나누어 뒤에서 5번째인 수를 출력한다.
