문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 예상 행: 인덱스, 열: 값 으로 나타내는 1차원 배열로 2차원 체스판을 구현할 것이다. 0번째 행부터 각 칸에 체스를 놓고 놓아도 되는지 확인 후 가능하다면 다음 행을 진행한다. check함수에서는 현재 행에 놓은 체스말의 위치가 세로로 같은지 확인과 대각선에 체스가 있는지 확인해야한다. 세로로 같은지는 배열값으로 확인할 수 있고 대각선에 있는지는 기울기가 1인 걸로 확인할 수 있다. 풀이방법 (접근..
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 예상 N의 범위가 1~80 까지 여서 모든 수의 조합을 만들고 계산하면 안된다고 생각했다. 그래서 수를 만들어가면서 좋은 수열 일 때만 계속되도록 진행하는 방법을 생각했고 check함수를 통해서 확인하고, 좋은 수열 이라면 perm함수를 계속 이어나갔다. 좋은 수열인지 확인하는 방법은 문자열길이의 절반만큼까지만 비교하면 되는데 뒤에서부터 한자리, 두자리, 세자리 ...문자열 길이의 절반 자리 까지 ..
문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 예상 k의 범위가 9까지밖에 안되고, 중복되는 숫자가 없기 때문에 완탐이 가능하다고 생각했다. 모든 숫자를 perm으로 돌리고, 부등호에 맞다면 정답을 갱신하는 방법을 생각했다. 부등호 자리가 일치하면 계속 진행하는 식으로도 짤 수 있을 것 같은데 귀찮아서 조합 다 만들고 체크했다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(N!* N) import java.io.BufferedRea..
문제 https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 풀이 예상 아무리 이분탐색 인걸 알아도.. 생각한 방법들은 시간초과 날 게 뻔하고.. 고민을 너무 오래해서 결국 답을 보고 풀었다. 이 문제에서 이분탐색의 범위를 나누는 조건은 mid 값 이하인 수를 전부세서 count한 개수가 홀수인지 짝수인지 판별하는 것이다. 예제를 예시로 들면, 아래처럼 개수가 카운트 된다. 1 2 3 4 5 6 7..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYxCRFA6iiEDFASu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이방법 (접근 방법 & 시간복잡도) 가격 배열과 사용했는지 여부를 확인하는 check 배열을 선언한다. 가격배열 뒤에서부터 순회하면서 해당 가격의 3/4 인 가격이 나올때까지 앞으로 가고, 해당 배열에 사용했다는 표시를 해준다. 위와같은 과정을 반복하여 끝까지 순회하다보면 check 배열에는 할인된 가격만 true 표시가 되어있다. 시간복잡도 => O(N^2) import java.io.Bu..
문제 https://www.acmicpc.net/problem/14224 14224번: 작은 정사각형 2 문제의 조건에 맞는 정사각형 중에서 가장 넓이가 작은 것의 넓이를 출력한다. www.acmicpc.net 풀이 예상 정사각형 한 변의 길이를 기준으로 이분탐색을 실행하고, 해당 길이에서 모든 범위와 모든 좌표를 순회하면서 K개수를 넘는지 확인한다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(N^3 * log M) - M: 2_000_000_002 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 K의 범위가 너무 커서 일반적인 방법으로는 절대 안되겠다고 생각이 들었다. 그래서 K를 이분탐색을 통해 줄여가면서 최솟값을 찾아내는 풀이 방법을 생각했다. 풀이방법 (접근 방법 & 시간복잡도) 1. 사람들의 능력치를 내림차순으로 정렬하고, 음식 난이도를 오름차순으로 정렬한다. 2. start = 0, end = 곱해서 최대가 나오는 수 로 설정하고 이분탐색을 시작한다. 3. mid값이 최소가 되기 위한 트레이닝 횟수를 count 한다. ..
문제 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 풀이 예상 NxN 의 최대가 10의 10승이므로 이걸 전부 나열할 수 는 없다고 생각했다. 그래서 규칙을 찾아 보려고 정렬한 숫자를 나열해 보았다. N = 3 인 경우 index 1 2 3 4 5 6 7 8 9 i x j 1 2 2 3 3 4 6 6 9 여기서 index 값을 가지고 ixj의 값을 만들거나 ixj의 값으로 index값을 만들어야 해야 하기 때문에..
