https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답코드 # 숫자 카드 # 복습 횟수:2, 00:10:00, 복습필요X import sys si = sys.stdin.readline N = int(si()) own_list = list(map(int, si().split())) own_list.sort() M = int(si()) check_card_list = list(map(int , si().split()))..
Koala - 11기
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 입력으로 주어지는 행 또는 열의 크기 N은 10^5 , 따라서 전체 행렬의 크기는 최대 10^10 으로, 10,000,000,000 (100억)이 된다. 이는 브루트-포스로 탐색하기에는 너무 오래걸린다는 뜻이다. 그러나 사실 위의 조건만 가지고 이 문제를 이분탐색 문제라고 생각하기는 어렵다. 문제에서 A와 B배열의 인덱스는 1부터 시작하는데, 예를 들어 B[7]=6이..
문제 https://www.acmicpc.net/problem/27278 27278번: 영내순환버스 첫 번째 줄에 승하차 지점 수 $N$과 병사 수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000)$ 두 번째 줄에 $i$번 지점에서 $i+1$번 지점으로 갈 때 걸리는 시간 $t_i$가 공 www.acmicpc.net Algorithm 운전병이 운전 업무를 마친 시간을 구하라고 했으므로 가장 마지막에 내린 병사가 언제내렸는지를 구하면 되는 문제이다. 문제에서 주어지는 거는 각 정류장 사이의 거리와 병사가 출발정거장에서 기다리기 시작한 시간이다. 그러면 우리가 따져주어야 하는 것은 다음과 같다. 병사가 탑승한 시간 병사가 내린 ..
문제링크 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) 문제풀이 입력받..
문제 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/3449 3449번: 해밍 거리 입력을 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄에는 이진수가 하나씩 주어진다. 두 이진 www.acmicpc.net 문제풀이 1.T를 입력받고 T만큼 반복되는 반복문을 작성한다. 2.2개의 이진수를 문자열로 입력받는다. 이러한 입력은 T만큼 반복되게 만들어준다. 2.해밍거리값을 hamming=0이라고 정의한다. 이 값은 T만큼 반복될때마다 초기화 되도록 만들어준다. 3.그리고 T만큼 반복되는 반복문 안에 한 이진수를 기준으로 그 이진수의 첫글자씩 다른 이진수와 비교하는 반복문을 작성해준다. 서로 다른 자리수일..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 정렬 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 ..
문제 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개의 면이 바뀌기 때문에, 인덱스를 정해놓고 방향에 따라 어떤 인덱스(면)가 어디로 바뀌는지 꼼꼼하게 살펴봐야 할 것 같습니다. 전개도는 다음과 같습니다. 이렇게 되어있을때 만약 ..
