코딩 맛집

1. 분할 정복법 - 분할 : 배열을 다음과 같은 조건이 만족 되도록 두 부분으로 나눈다. 1. 자기 자신 보다 작은 값들 2. 자기 자신 보다 큰 값들 - 정복 : 각 부분을 순환적으로 정렬 한다. ​ 2. 퀵 정렬 1. 정렬할 배열이 주어짐. 마지막 수를 기준(pivot)으로 삼는다. 31 8 48 73 11 3 20 29 65 15 2. 기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치 분할 한다. 8 11 3 15 31 48 20 29 65 73 3. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다. 3 8 11 15 20 29 31 48 65 73 3. sudo 코드 quickSort(A[], p, r) { // A[p....r]을 정렬한다. if (p < r) then ..

Merge Sort, Quick Sort, Heap Sort 중 에서 Merge Sort, Quick Sort 는 분할 정복법 (Divide and Conquer) 에 해당 합니다. ​ * 분할 정복법 - 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 - 정복 : 각각의 작은 문제를 순환적으로 해결 - 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 1. Merge Sort 는 위 그림과 같이 주어진 배열을 분할 해줍니다. (5, 2) (4, 7) (1, 3) (2, 6) 2개의 원소들로 분할 해줍니다. ​ 2. 분할된 각 원소들을 각각 정렬(합병) 시켜 줍니다. (5), (2) -> 정렬 -> (2, 5) (4), (7) -> 정렬 -> (4, 7) (1)..

1. 문제 학생들의 점수 목록이 배열로 주어진다. 그리고 k개 그룹으로 학생들을 묶을려고 합니다. 이때, 그룹별로 학생들의 점수 차이가 비슷 한 학생들 끼리 묶을려고 합니다. 그룹들의 점수가 가장 높은 친구의 점수와 가장 낮은 점수 차이들의 합이 최소값을 출력 하시오. 학생들의 점수 배열은 오름차순으로 정렬되어 입력 됩니다. 입력 점수 배열 입력 조 그룹 인원 출력 {1, 3, 7, 8, 10, 15} 3 5 {1, 2, 12, 14, 15} 2 4 2. 접근 1. 점수 목록 배열을 가지고 구간 별 차이를 구합니다. 2. 구간 차이가 작을수록 같은 그룹이 될 확률이 높습니다. 3. 구간 차이가 크면 다른 그룹으로 분리 시켜야할 기준이 됩니다. 3. 구간 차이 배열에서 값이 가장 큰 순서대로 k개를 뽑습니..

1. 문제 괄호가 존재하는 문자열에서 특정 괄호의 인덱스가 주어질 때, 그 괄호의 짝이 되는 괄호(열린 괄호 -> 닫힌 괄호, 닫힌 괄호 -> 열린 괄호)에 위치 인덱스를 배열로 출력하는 문제 입니다. 입력 문자열 입력 인덱스 출력 인덱스 "{kcc{orag}}{orange}" {0, 9, 11} {10, 4, 18} "{kcc{i{like}{dart}}{abcd}}{orange}" {0, 4, 11} {25, 18, 6} 2. 접근(추상) 예: "{kcc{orag}}{orange}" 1. 무조건 '열린 괄호'가 먼저 등장 한다. 2. 앞에서 부터 탐색을 시작하면, '닫힌 괄호'가 등장하면, 가장 최근에 등장한 '열린 괄호'와 짝 이다. 3. '열린 괄호', '닫힌 괄호'를 짝별로 저장해두면, 검색 시 ..

1. 문제 "010-1234-1234" 휴대폰 번호 "02-123-1234" 전화 번호 "1234-1234" A 자격증 번호 "123456-1234567" 주민번호 입력 출력 { "02-123-1234", "010-1234-1234", "010-2222-2222", "1234-1234"} {1, 1, 2} 예를 들어, 위와 같이 숫자의 개수가 같고, 하이픈(-)의 위치가 같으면, 같은 패턴으로 가정하고, 문자열 배열이 주어졌을 때, 같은 패턴 끼리의 개수를 오름차순 배열로 출력 하시오. 2. 2개의 문자열이 같은 패턴인지 비교 로직 import java.util.*; import java.util.stream.Collectors; public class One { public static void mai..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 문제 오늘 부터 N + 1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 적절히 상담을 잡아, 최대 수익을 출력 해야 하는 문제 입니다. 예시로 주어진 입력 값인데요, Ti = 는 상담 기간, Pi = 상담을 해줌으로써 얻을수 있는 수익 입니다. 예를 들어, 1일에 상담을 하면 2, 3일은 상담을 할수 없고, 10의 수익을 얻을수 있습니다. 이때, 최대 수익을 출력 하시오. 2. 접근 1. 다이나믹 프로그래밍(dp)를 통해서 접근 할 수 있습니다. 2. 현재 상담 일자의 수익(p[i]) + 현재 상담을 진행 한 후, 부터 얻을 수 있는 최대 수익(t[i] + i) 3. 위와 같은 점화식을 떠..

1. 문제 백준 14888번(연산자 끼워넣기) N개의 수로 이루어진 수열이 주어지고, N - 1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(÷) 으로만 이루어져 있습니다. 이 연산자들은 연산자 우선순위를 무시하고, 앞에서 부터 연산을 합니다. 이때, 구할수 있는 최대값과 최소값을 구하시오. 나눗셈의 경우에는 몫만 취하고 나머지 값은 버립니다. 그리고 음수를 양수로 나눌때는 음수를 양수로 바꾼 뒤 몫을 취하고, 몫을 음수로 바꾸어 계산 합니다. 2. 접근(추상) 1. 주어진 연산자들(n-1개) 중에 n-1개를 뽑아야 합니다. 2. 하지만, 이 연산자들의 순서에 따라서, 값이 달라집니다. 3. 따라서, 순열을 사용합니다. 4. 연산자들 중 중복으로 사용 가능한 연산자도 주..

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개�� www.acmicpc.net 1. 문제 1번 부터 N번 까지의 도시가 M개의 단방향 도로가 존재 합니다. 모든 도로의 거리는 1로 같습니다. 이 때 X번 도시 부터 출발 하여 최단 거리가 K인 모든 도시들의 번호를 출력하는 프로그램을 작성 하시오. (2

18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 1. 문제 n x n 의 복도가 주어졌습니다. 선생님과 학생의 위치가 n x n의 2차원 배열의 주어졌을때, 선생님은 상, 하, 좌, 우 로 학생이 있는지 감시 할수 있습니다. 그런데 선생님의 눈이 너무 좋아서 끝까지 학생이 있는지 없는지 확인 할 수 있습니다. 이때, 3개의 장애물을 설치 할 수 있습니다. 학생 앞의 장애물이 놓이면, 선생님은 학생을 발견 할 수 없습니다. 이때 선생님과 학생의 위치를 알 수 있는 n x n 의 2차원 배열이 주어 졌을 ..

1. 문제 위와 같은 배열이 주어지고, 쿼리 : (left 인덱스, right 인덱스) 가 주어졌을 때, 이 쿼리는 left 인덱스 부터 right 인덱스 까지 수의 합을 반환해야 합니다. 이때 쿼리는 총 M(1