문제링크 https://www.acmicpc.net/problem/1337 1337번: 올바른 배열 첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이 www.acmicpc.net 코드 n = int(input()) data = sorted([int(input()) for _ in range(n)]) mn = float('inf') for i in range(n): cnt = 0 for j in range(data[i],data[i]+5): if j not in data: cnt+=1 mn = min(mn,cnt) print(mn) 문제풀이 입력받..
Koala - 11기/코딩테스트 준비 스터디
문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 예시 코드 // ** 2470 ** // #include #include #include #define INF 2000000000 using namespace std; int n; vector result(2); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; vector arr(n..
문제 풀이 -10억부터 10억까지 숫자가 주어지고 세 수의 합이 가장 0에 가까운 수들을 찾는 문제이다. 입력은 정렬된 상태로 주어지지 않으니, 입력을 받고 먼저 정렬을 한다. 반복문으로 배열에 접근하면서 투 포인터를 사용하였다. abs(arr[i] + arr[low] + arr[high])가 가장 0에 가까운 세 수를 찾으면 되는데, 10억 + 10억 + 10억은 int로 받을시에 오버플로가 나서 long long으로 받아주었다. 코드 #include #include #include #include using namespace std; int n; int arr[5001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(N..
풀이 누적합과 투포인터를 이용한다. 왼쪽 포인터와 오른쪽 포인터를 설정하여 구간의 합을 계산한다. 구간의 합이 M과 같으면 경우의 수를 증가시키고 M보다 작으면 오른쪽 포인터를 증가시켜 구간을 확장하고 구간 합이 M보다 크면 왼쪽 포인터를 증가시켜 구간을 축소시킨다. 오른쪽 포인터가 끝에 도달할 때까지 반복한다. 시간복잡도 O(N) 코드 #include #include using namespace std; int main() { int N, M; cin >> N >> M; vector A(N); for (int i = 0; i > A[i]; } int count = 0; int left = 0; int right = 0; int sum = A[0]; while (right ..
문제 https://www.acmicpc.net/problem/1253 풀이 입력받은 리스트(li)를 정렬한다. 반복문을 통해 선택된 수를 제외한 새로운 리스트(arr)를 만든다. 투 포인터를 이용하여 새 리스트를 양 끝에서 탐색한다. 두 수의 합과 선택한 수를 비교한다. li[i] == val이면 cnt를 증가시키고 while문을 종료한다. li[i] > val이면 l을 증가시킨다. li[i] < val이면 r을 감소시킨다. 코드 n = int(input()) li = sorted([*map(int, input().split())]) cnt = 0 for i in range(n): arr = li[:i] + li[i + 1:] l, r = 0, len(arr) - 1 while l < r: val = ..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 문제풀이 0은 빈 칸, 1은 집, 2는 치킨집이다. 최대 M개의 치킨집을 제외하고 나머지 치킨집은 폐업시켜야 한다. 치킨집의 개수가 최대일 때, 도시의 치킨 거리가 최솟값인 것은 자명하다. 도시에서 M개의 치킨집을 정하여, 각 집마다 거리의 합을 구하여, 최솟값을 갱신하면 된다. 도시에서 치킨집을 고르는 것은 조합인 것을 확인하고, 깊이 우선 탐색 방법으로 구현하였다. ..
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제의 설명을 잘 이해해야 풀 수 있는 문제라고 생각됩니다. 설명에 주사위의 전개도가 주어지는데, 주사위의 방향을 결정하는 명령어에 따라 밑면뿐 아니라 4개의 면이 바뀌기 때문에, 인덱스를 정해놓고 방향에 따라 어떤 인덱스(면)가 어디로 바뀌는지 꼼꼼하게 살펴봐야 할 것 같습니다. 전개도는 다음과 같습니다. 이렇게 되어있을때 만약 ..
Problem Solution 1) 변수 및 배열 선언 및 입력 받기 2) 두 개의 포인터를 사용하여 합이 0에 가까운 두 수를 찾기 두 개의 포인터 'left'와 'right'를 배열의 양 끝으로 초기화하고 합이 0에 가까운 두 수를 찾기 위해 'left' 포인터와 ' right' 포인터를 이동시키면서 최적의 값을 찾는다. 반복문은 'left'와 'right'가 같아질 때까지 계속 실행된다. 최솟값을 저장하는 'minVal'을 갱신하면서, 합이 0에 더 가까워질 때마다 그 때의 두 수를 'ans'에 저장한다. 3) 'ans' 벡터에 저장된 두 수를 출력한다. Answer #include #include #include #include using namespace std; int main() { int ..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net # 풀이 일반적인 이중포문으로 생각하고 돌리면 쉽지만, 시간 초과가 난다. 이럴 때 사용하는것이 투포인터인데, 투포인터를 사용하여 시간복잡도를 줄이면 된다. m=3이고 배열 1,2,3,5,4 라고 생각했을 때, 먼저 정렬을 해준다. 그러면 1,2,3,4,5인데 이때, 두수를 비교해보자 1과 1: 차이가 0이므로 틀림. 1과 2: 차이가 1이므로 틀림. 1과 3: 차이가 2이므로..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net Algorithm k개의 구간안에 있는 초밥들과 쿠폰으로 받을 수 있는 초밥중 서로 다른 초밥 개수의 최댓값을 구하는 문제이다. 구간을 정해주기 위해 투포인터를 사용하였다. 서로 다른 초밥의 개수를 구하기 위해 딕셔너리를 사용하였다. 회전초밥이므로 확인해야 하는 구간은 총 n개이고, 예제 입력1에서 25,7,9,7을 고르는 경우도 있으므로 초밥종류를 가..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net # 문제 설명 - N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다"라고 한다. - N개의 수가 주어질 때, 그 중에서 좋은 수의 개수는 몇 개인지 출력한다. 수의 위치가 다르면 값이 같아도 다른 수이다. # 풀이 방법 - 오름차순 정렬 후 각각의 수가 좋은 수인지 찾는다. - 투포인터 (s=0, e=n-1)를 통해 두 인덱스 값의 합이 목표보다 작으면 e--, 크면 s++를 해준다. -..
https://www.acmicpc.net/problem/2234 코드 # 성곽 # 복습 횟수:2, 01:30:00, 복습필요O import sys from collections import deque si = sys.stdin.readline M, N = map(int, si().split()) # 가려는 방향에도 벽이 있는지를 체크해야한다. 북남서동 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] tmp_list = [] for i in range(N): tmp_list.append(list(map(int, si().split()))) graph = [[[] for i in range(M)]for i in range(N)] def converter(i, j): val = tmp_l..
