전체 글
10815번-숫자 카드
문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 접근방법 1) 접근 사고 n의 카드들이 있을때 m의 카드들이 n의 카드들에도 있는지도 확인하면 되는 문제였습니다. 이진 탐색을 활용하면 쉽게 해결할 수 있는 문제 입니다. 2) 시간 복잡도 n과 m의 카드의 길이가 500,000이므로 완전탐색을 돌리면 25,000,000,000,000의 연산이 일어나므로 시간복잡도를 줄여야 하는 문제였습니다. 3) 배운 점 두 ..
7453번-합이 0인 네 정수
문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 접근방법 1) 접근 사고 주어진 배열이 4개이고 탐색을 해야 하는 문제이므로 2개의 배열씩 짝지어서 n^2으로 조합을 맞춘 뒤에 문제에서 주어진 조건이 a, b, c, d의 배열 4개의 합이 0이어야 하므로 더한 배열에서 이분 탐색을 실시하면 되는 문제였습니다. 2) 시간 복잡도 가장 단순하게 4개의 배열이니까 n^4으로 문제를 풀면 n은 4000이고 N의 4승이므로 64,..
1300번-K번째 수
문제 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의 크기 때문에 완전탐색으로는 시간초과가 발생하는 문제이기 때문에 시간복잡도를 줄여야만 하는 문제였다. 이 문제의 탐색 기준은..