✔ 주몽 [백준 1940] 문제 분석하기 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정하여 문제에 접근 손으로 풀어보기 재료 데이터를 배열 A[N]에 저장한 후 오름차순 정렬 투 포인터 i, j를 양쪽 끝에 위치시킨 후 문제의 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행 A[i] + A[j] > M: j --; A[i] + A[j] < M: i++; A[i] + A[j] == M: i++; j--; count++; i와 j가 만날 때까지 반복한 후, 반복이 끝나면 count를 출력 슈도코드 작성하기 N(재료의 개수), M(갑옷이 되는 번호) 저장하기 for(N만큼 반복) { 재료 배열 저장하기 } 재료 배열 정렬하기 while(i < j) { if(재료 합 < M) 작은 번호 ..
✔ 나머지 합 [백준 10986] 문제 분석하기 구간 합 배열을 이용해 계산하며 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값을 동일하다는 것을 이용함 또한 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j) 쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어짐을 이용함 예) S[0] = S[3] = 1 이므로 A[1]부터 A[3]까지의 구간 합이 M으로 나누어 떨어짐 (1 + 2 + 3 + 1 - 1 = 6 % 3 = 0) 손으로 풀어보기 A 배열의 합 배열 S를 생성 합 배열의 S의 모든 값을 M으로 나누어줌 원소 값이 0인 경우, 원본 배열의 0부터 i까지의 구간 합이 이미 M..
✔ 구간 합 구하기 5 [백준 11660] 문제 분석하기 질의의 개수가 100000이므로 구간 합 배열을 이용해야 함 구간 합 배열이 1차원에서 2차원으로 확장되었으므로 새로 정의가 필요 D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합 손으로 풀어보기 2차원 구간 합 배열의 1행, 1열부터 구함 D[1][j] = D[1][j - 1] + A[1][j] D[i][1] = D[i - 1][1] + A[i][1] 1행, 1열을 통해 나머지 2차원 구간 합 배열을 채움 D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j] 구간 합 배열을 통해 질의에 대한 답을 구함 X1, Y1, X2, Y2에 대한 답 ..
✔ 평균 [백준 1546] 문제 분석하기 모든 점수를 입력받은 후 최고점을 별도로 저장한 후 평균 점수를 구함 손으로 풀어보기 점수를 1차원 배열에 저장함 배열을 탐색하며 최고 점수와 점수의 총합을 구함 '총합 * 100 / 최고 점수 / 과목의 수'를 계산하여 평균값을 출력함 슈도코드 작성하기 변수 N에 과목의 수 입력받기 길이가 N인 1차원 배열 A[] 선언하기 for(A[] 길이만큼 반복하기) { A[i]에 각 점수 저장하기 } for(A[] 길이만큼 반복하기 { 최고점은 변수 max에, 총점은 변수 sum에 저장하기 } sum * 100 / max / N 출력하기 코드 구현하기 /** * 1546) 평균 */ public class D002_1546 { public static void main(..
✔ 2xn 타일링 [백준 11726] 문제 분석하기 2 x N 크기의 직사각형을 1 x 2 또는 2 x 1 크기의 타일로 채우는 경우의 수를 구하는 점화식 D[N]을 정의해야 함 1부터 N - 1 크기에 직사각형과 관련된 경우의 수를 모두 구해 놓았다고 가정하고 N 바로 직전에 구해야 하는 N - 1, N - 2에서 N의 길이를 만들기 위한 경우의 수를 생각해보면 D[N] = (D[N - 1] + D[N - 2])이라는 점화식을 도출할 수 있음 손으로 풀어보기 점화식의 형태와 의미를 도출 D[N]은 길이 N으로 만들 수 있는 타일의 경우의 수 점화식을 구함 D[N] = D[N - 1] + D[N - 2] 점화식으로 D 배열을 채운 후 D[N]의 값을 출력 D 배열을 채울 때마다 문제에서 주어진 값으로 %..
✔ 이항 계수 1 [백준 11050] 문제 분석하기 조합에서 가장 기본이되는 문제이므로 일반 점화식을 이용하여 문제를 해결 손으로 풀어보기 N과 K의 값을 입력받고 DP 배열을 선언 D[N + 1][N + 1] DP 배열의 값을 초기화 i개 중 1개를 뽑는 경우의 수인 D[i][1] = i i개 중 0개를 뽑는 경우의 수인 D[i][0] = 1 i개 중 i개를 뽑는 경우의 수인 D[i][i] = 1 점화식으로 DP 배열의 값을 채움 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] D[N][K]의 값을 출력함 슈도코드 작성하기 N(총 개수), K(선택 수) D(DP 배열) for(i -> N만큼 반복하기) { D 배열 초기화하기 D[i][1] = i D[i][0] = 1 D[i][i..
✔ 줄 세우기 [백준 2252] 문제 분석하기 학생들을 노드로 생각하고, 키 순서 비교 데이터로 엣지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제 특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일 손으로 풀어보기 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트 진입 차수가 0인 노드를 큐에 저장 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 큐가 빌 때까지 반복 슈도코드 작성하기 N(학생 수) M(비교 횟수) A(데이터 저장 인접 리스트) 학생 수만큼 인접 리스트 ..
✔ 집합의 표현 [백준 1717] 문제 분석하기 최대 원소의 개수 1000000과 질의 개수 100000이 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제 손으로 풀어보기 각 노드의 값을 자기 인덱스값으로 초기화 find 연산으로 특정 노드의 대표 노드를 찾고, union 연산으로 2개의 노드를 이용해 각 대표 노드를 찾아 연결 find 연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 대표 노드로 변경해야 함 union 연산을 수행할 때 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결해야 함 질의한 값에 따라 결과를 반환 슈도코드 작성하기 N(원소 개수) M(질의 개수) parent(대표 노드 저장 배열) for(N만큼 반복하기) { 대표 노드..
