https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N, M = map(int, input().split()) nums = list(map(int, input().split())) left, right = 0, 1 cnt = 0 while right
Koala - 14기/코딩테스트 준비 스터디
문제 링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 접근 방법 일반적인 시뮬레이션 문제입니다. 시뮬레이션 문제는 세부사항을 잘 읽는 것이 중요하고 해당 문제에서 구현에 유의할 점을 크게 2가지로 보았습니다. 첫 번째로는 사과를 먹었을 때의 상황, 두 번째로는 움직임과 동시에 벽과의 충돌여부 검사입니다. 사과 여부에 따른 뱀 정보 최신화, 이동하는 좌표가 벽 또는 몸이라면 즉시 게임을 종료하도록 코드를 구현하였습니다. 추가적으로 N이 100이므로..
문제 요약 N개의 길이를 가진 수열에서 차가 M이상이면서 가장 작은 경우의 차를 구하는 문제 입력 N, M이 주어지고 수열이 한줄에 하나씩 입력된다 출력 M 이상인 가장 작은 차 코드 설명 sort로 크기 순으로 정렬한 후 투포인터로 앞에서부터 비교해가며 가장 작은 차를 찾는다 통상적인 투포인터와 비슷하지만 left를 0 right를 len-1로 설정했을 때에는 너무 많은 조건이 생기게 되었어서 앞에서부터 비교하는게 유리하다. 문제에 따라 left와 right를 어떻게 설정하는지가 중요한 것 같다 경우마다 최소값을 리스트에 append하고 최종적으로 최소값을 찾는 방법은 시간초과 문제를 일으킨다. 최소값만 저장해놓고 16줄처럼 비교만 하면서 더 최솟값인 경우만 저장하면 메모리도 시간도 아낄 수 있다.
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터 문제이다. 이는 두 숫자들의 합을 이용해서 절대값이 0에 가까운 값을 출력하는 것이다. 만약 절대값이 0이라면 반복문을 그만하고 해당 두 숫자를 출력하면 된다. 그렇지 않다면, 두 수의 합이(절대값 아님) 0보다 작은 음수 값이라면 왼쪽 인덱스 번호를 증가하고, 만약 0보다 큰 양수 값이라면 오른쪽 인덱스 번호를 감소시킨다. 그렇게 최종적으로 절대값이 ..
1063 킹 https://www.acmicpc.net/problem/1063 Algorithm 킹이 움직인다. 이때 체크해야할 조건은 다음과 같다. 격자 안에서만 움직여야 한다. 돌이 있는 곳으로 움직일 경우, 돌과 함께 움직여야 한다. 이때 돌 또한 격자 안에서 움직여야 한다. 돌이 격자 밖으로 나가는 경우도 체크하되, 이때 킹이 격자 내에서 움직인다면 상관없이 움직인다 Code # 행: row, 열: col row = {'8':0, '7':1, '6':2, '5':3, '4':4, '3':5, '2':6, '1':7} col = {'A':0, 'B':1, 'C':2, 'D':3, 'E':4, 'F':5, 'G':6, 'H':7} move = {'R':(0,1), 'L':(0,-1), 'B':(1,0..
https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 문제 N*N(1 n; for (int i = 0; i > arr[i]; } for (int i = 0; i = 2) r++; cnt = 0; } } if (cnt >= 2) r++; ..
문제 https://www.acmicpc.net/problem/9996 Algorithm 정규식을 활용한다. C++ 정규식에서 regex_match(str, e)는 정규표현식 e와 문자열 str이 일치함을 나타내고, 모든 문자열을 표현하기위한 정규식 e는 ".*"으로 나타낼 수 있다. input의 표현식에서 *를 .*으로 바꾸어 정규표현식을 생성한 뒤, regex_match를 수행한다. Code #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; int n; string str; void IN..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 분석 난이도 골드 5 분류 투포인터 문제 풀이 전형적인 투 포인터 문제, 투 포인터를 사용하기 위해 정렬해준 뒤 앞 포인터와 뒤 포인터의 차이를 이용해 투 포인터를 진행시키면 되는 문제이다. 소스코드 from sys import stdin input=stdin.readline n,m=map(int,input().split()) arr=[int(input()) for i i..
https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; struct Birth { string name; int month; int day; int year; }; Birth arr[100]; bool compare(const Birth& a, ..
문제 링크 문제 링크 문제 풀이 '세 용액' 문제는 '용액' 문제의 심화 문제이다. 용액 문제 링크 '용액' 문제는 두 개의 용액을 선택하여, 두 용액의 값의 합이 0에 가장 가까운 경우의 조합을 구하는 문제이다. '세 용액' 문제를 풀기 전에 '용액' 문제의 풀이를 먼저 한 뒤 '세 용액' 문제의 풀이를 해보겠다. '용액' 문제 풀이 용액을 오름차순으로 정렬하고, 그 중 가장 값이 작은 용액을 A[i]로 칭하고 가장 값이 큰 용액을 A[j]라고 하자. 그 둘의 합이 양수인 경우를 생각해보자. 문제의 최적해는 용액의 합이 0에 가장 가까운 경우의 해이기 때문에 A[i]가 아닌 A[i+k]를 A[j]와 더하면 그 값이 더 커지기 때문에 최적해를 절대 찾을 수 없게 된다. 반대로, 둘의 합이 음수인 경우를 ..
회전 초밥 !https://d2gd6pc034wcta.cloudfront.net/tier/12.svg 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 17881 6251 4435 34.223% 문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. https://upload.acmicpc.net/f29f0bd9-6114-4543-aa72-797208dc9cdd/-/preview/ 새로 문을 연 회전 초밥 음식점이 불경기로 영업..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net N = int(input()) dp = [0, 1 ,2] for i in range(3, N + 1): dp.append(dp[i - 1] + dp[i - 2]) print(dp[N] % 10007)
