1. [BOJ 4435] 중간계 전쟁 https://www.acmicpc.net/problem/4435 4435번: 중간계 전쟁 첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, www.acmicpc.net 문제에서 요구한 대로 아래 내용에 맞게 점수를 곱해 더해주면 되는 문제입니다. 간달프 호빗 - 1 인간 - 2 엘프 - 3 드워프 - 3 독수리 - 4 마법사 - 10 사우론 오크 - 1 인간 - 2 워그(늑대) - 2 고블린 - 2 우럭하이 - 3 트롤 - 5 마법사 - 10 t = int(input()) for i in range(t): a1, a2, ..
분류 전체보기
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제 풀이 첫번째 줄에 얻은 값들을 num이라는 리스트에 저장하고, 두번째 줄부터 입력되는 정사각형의 각 숫자들을 rec라는 2차원 리스트를 생성하여 값을 저장한다. 네 꼭짓점의 수가 모두 같은 가장 큰 정사각형의 크기를 출력해야 하므로, 해당 정사각형 내에서 만들 수 있는 가장 큰 정사각형 변의 길이에서 시작하여 변의 길이를 하나씩 줄여가는 반복문을 만든다. 반복문을 사용하여 위와 같은 방식으로..
https://www.acmicpc.net/problem/10178 10178번: 할로윈의 사탕 할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈 www.acmicpc.net 문제분석 정수 입력을 받아 그 정수만큼 loop 문을 돌려서 2개의 정수를 입력 받고 그 몫과 나머지를 출력하는 문제이다. 몫과 나머지를 출력할 때, 문자열을 함께 출력해야 한다. C++ 언어에서는 단순히 입출력 함수를 쓰면 되지만, 파이썬에서 이 문제를 풀기 위해서는 format이나 print(f) 함수를 사용해야 한다. 코드 a = int(input()) for _ in range(a): n, m ..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 해당 문제는 주어진 k개의 숫자를 사용해서 6개의 숫자 조합을 만들어 내는 것이 포인트입니다. 6가지의 숫자 조합을 만들기 위해서 두가지 방식으로 접근을 해봤습니다. ① C++ STL의 prev_permutation() 함수를 이용한 조합 만들기 더보기 더보기 더보기 변수 k의 범위가 6 < k < 13 으로 작은 편이어서 prev_permutation 알고리즘을 사용해도 시간제한 1초..
링크 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 키가 같은 사람이 연속해서 줄을 설 경우를 생각하는데 오래 걸려서 많이 고민한 문제였습니다. 5555 (4C2) 65555 같은 경우만 생각해서 33332333 같은 경우를 고려하지 못했습니다. 스택에 차례대로 줄에 선 사람들을 넣으면서 1. top 보다 작으면 push를 하고 2. top 과 같으면 push 할 때 second를 top의 second += 1 (..
링크 https://www.acmicpc.net/problem/15654 문제 풀이 입력받은 수를 사전 순으로 출력하는 것이 문제의 조건이다. 수 들이 임의의 순서로 주어지므로 이를 정렬하고, 완전 탐색을 이용한다. j 번째 인덱스를 참조할 때마다 visit[j]를 true로 설정하여, 중복으로 입력되는 것을 방지한다. 재귀가 끝난 이후 false로 설정하여, 해당 index를 참조할 수 있도록 한다. 코드 결과
링크 https://www.acmicpc.net/problem/2798 풀이 N개의 카드중 3개를 뽑아 더하여 구하는 조합 문제이다. 이번에 배운 next_permutation을 이용한 조합알고리즘을 사용해보았다. 3중첩 for문, next_permutation, dfs를 이용하여 구현하였으며 이중 for문의 성능이 가장 우수하였고 dfs는 시간초과로 인하여 틀렸다. 코드 for문을 이용한 코드 #include using namespace std; int main() { int n,m; int card[100]; cin >> n>>m; for (int i = 0; i > card[i]; } int result = 0; for (int i = 0; i < n; i++) { f..
링크 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 채널 N으로 이동할 때 100번에서 +, - 로만 이동하는 방법과 고장나지 않은 버튼으로 누를 수 있는 번호를 누르고 필요시 +, -로 이동하는 방법 중 최소의 값을 구했습니다. 처음 제출할 때 초기 ans값을 초기화 하는 과정에서 아무 생각 없이 0으로 잡아 틀렸는데 문제를 풀 때 멍때리지 말고 차근 차근 생각하면서 풀어야 겠다고 느꼈습니다 (자의적인 해석 ❌ 문제 꼼..
링크 https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net 풀이 문제를 처음 보자마자 떠올린 풀이는 nC3으로 세 점을 뽑는 방법이였지만 시간복잡도 때문에 두 점을 뽑고 이진탐색으로 나머지 한 점이 찍혀있는지 확인하는 방법으로 풀었습니다. 하지만 위 방법으로 풀어도 시간초과가 떠서 이리저리 코드를 바꿔보면서 한참 해맸는데 (분명 시간복잡도 계산해 보면 시간 초과가 뜰리가 없는데...) 이진 탐색을 구현하는 함수 코드에서 ..
링크 : https://www.acmicpc.net/problem/1969 입력 첫 줄에 DNA의 수 N과 문자열의 길이 M 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 출력 첫째 줄에 Hamming Distance의 합이 가장 작은 DNA를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다. 예제 입력 : 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 예제 출력 : TAAGATAC 7 첫째 줄 T T A T T T4개, A1개 T출력 후 Hamming Dist..
https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net * 한 게시글에 코드블럭 언어를 하나로 통일해야 하나봐요ㅜㅜ Swift 외 코드는 하이라이트가 정상적이지 않을 수 있습니다.. Intro 처음에는 sort를 한 뒤 nC3으로 3개 조합을 뽑고 x[0]+x[2] = 2*x[1]라는 식을 통해 검증하려 하였으나 시간 초과가 발생하였습니다. 결론적으로 sort를 사용하지 않고 nC2의 조합을 사용하여 시간 초과 문제를 해결했습니..
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제분석 N개의 수가 주어지고, 이를 오름차순으로 정렬하는 문제이다. 입력으로는 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력으로는 둘째 줄부터의 입력들을 오름차순으로 정렬하면 된다. 예를 들어, 첫째 줄에 5가 주어지고 두번째 줄부터 차례로 3 6 9 3 6 이 주어졌다고 했을 때, 출력으로..
