![]()
문제 https://www.acmicpc.net/problem/2309] 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net Algorithm 입력으로 받은 값들을 중 두 개의 값을 뽑을 떄 그 두 개의 합을 입력값의 총합에서 뺏을 때 100이 되는 값들을 찾고 전체 값에서 그 두개의 값을 제거한다. Code from collections import deque from itertools import combinations as cb input = __import__('sys').stdin.readline heights ..
문제 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 설명 학생들의 국어, 영어, 수학 점수를 특정 조건에 맞게 정렬한 뒤 학생 이름을 순서대로 출력하는 문제 코드 #include #include #include #include #include #include #include using namespace std; typedef struct{ int kor, eng, math; string name; }student; bool sortFunc (student A, student B) {..
![]()
15650번: N과 M (2) (acmicpc.net) 코드 코드설명 본 문제는 '수열과 조합'에서 조합을 묻는 문제로 from itertools import combinations 을 활용해 1 ~ n 까지의 자연수 에서 m 길이 만큼의 조합을 출력하는 문제다. 하지만, 이는 '재귀함수'을 이용해서도 풀이가 가능하다. go() 함수는 리스트 arr을 입력 받았을 때 len(arr) == m 일 시 리스트 arr를 출력하고, len(arr) != m 일 시 리스트 arr에 자연수 i을 추가하는 함수이다. 여기서 리스트 arr를 출력하고 '재귀적인 방법'을 사용했기에 함수 내 함수를 출력한 곳으로 return 한다. for 문에서 재귀 함수를 이용해 풀이 시 조건문을 활용해 리스트 arr가 1) '비어 있..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 풀이 학생들이 처음 서 있는 줄은 먼저 들어온 사람이 먼저 나가는 FIFO 구조이므로 queue를 이용하면 된다.(편의상 deque를 이용하여 구현하였다.) 그리고 학생들이 순서대로 입장하기 위해 잠시 머무는 줄은 LIFO 구조이므로 stack을 이용하면 된다. 이제 준비는 끝났다. 문제에서 원하는대로, queue에서 또는 stack에서 순서(order)에 맞는 사람이 res 리스트에 입장..
![]()
문제 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개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..
