유혁스쿨

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 동적계획법 큰 문제를 작은 문제로 나누어 푸는 방법. 복잡한 문제를 풀기 위해 작게 조각내어 문제를 풀고 합치면 된다. 정수삼각형 숫자로 구해진 삼각형이 있고 위에서부터 대각선으로만 내려올 수 있다. 내려오면서 숫자를 더했을 때 어떤 경로로 이동했을 때 가장 큰 숫자가 나오는지 가장 큰 최대값을 구하는것이 문제이다. 굉장히 많은 경우의수가 나올수 있기 때문에 어렵게 느껴질 수 있지만, 이중 하나만 때어놓고 생각해보면 7에서 3으로 가는것과 7에서 8로 가는것 둘중 어느것이 최대값으로 가는것인지 생각해보면 굉장히 단순하다. 이 작은 조각의 단위가 여러개 있는것 뿐이다. 중간의 경우 8 1 0 2 7 4 4 처음 2는 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 올바른 괄호의 갯수 A 입력값으로 괄호쌍의 갯수가 주어지고 이 괄호의 조합중에 올바르게 닫힌 괄호의 갯수가 몇개인지 구하는 문제 모든 케이스를 다 순회하면서 조건에 맞는 경우만 카운트한다. 괄호가 열렸다가, 닫혔다가 하면서 점점 증가하며 여러 케이스가 생기고 각 케이스에서 열리고 닫히는 순서를 달리하면서 또 다른 케이스들이 파생되기 때문에 선형적으로 증가하지 않게되므로 비 선형구조 탐색에서는 너비,깊이 우선 탐색이 있다. N = 2라고 가정 주어진 괄호를 하나씩 차근차근 쌓아나가것으로 문제를 접근한다. 열리는괄호 닫히는괄호 각각 N개씩있다. N이 2일때 열리는것 혹은 닫히는것 각각의 기준을 놓고 시작할 수 있다. 그..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 게임 맵 최단거리 미로의 시작 점에서 시작해서 목적지까지 찾아가는 최단 거리를 구하는 문제이다. 최단거리 탐색 중 BFS - 너비우선 탐색에 대한 전형적인 문제이다. 현재 시점에 움직일 수 있는 여러가지 경우의 수 중 모든 경우를 다 확인해야 한다. 맵에서 player가 특정 위치에 있을 때 대각선을 제외한 이동가능 경우의 수는 4가지 경우의 수가 나온다. 이 4가지 경우를 모두 가본다. 각 방향대로 1칸씩 움직인 이후에 다음 위치를 경우의 수 대로 생각하는 방식이다. 현재 시작점 위치를 0으로 두고 각각의 이동할 수 있는 경우의 수를 모두 가보는 것이다. 현재 위치의 수보다 1씩 더해서 이동하게 된다. 만약 벽이 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 의상(위장) 스파이가 위장할 수 있는 아이템들의 종류가 있다. 각 종류들을 조합해서 위장을 하게 되는데, 그 모든 경우의 수가 몇가지가 되는가 위장 용품은 착용을 할 수 있고 안할 수도 있다. 쉽게 접근하면 위장용품들의 각 갯수를 서로 곱하면 모든 경우의 수가 나온다. 하지만 착용 안할 수도 있다. 경우의 수에 1을 더해서 모두 곱해주면 된다. 모든 위장용품을 하나도 착용하지 않은 경우가 포함되기 때문에 추후 1을 빼주면 된다. 문제의 핵심은 경우의 수를 구하는 것이 아니라 아이템의 종류별로 갯수를 카운트하는데에 있다. 문제에서는 헤드기어 2종류, 아이웨어 1종류가 있다. 종류별로 총 몇개가 나오는지를 카운트 하는것..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 숫자게임 A B 두 팀의 숫자를 순서대로 내서 큰 수를 낸 팀이 승점을 갖게 된다. 숫자가 같은경우 비기는경우는 승점이 없다. A팀은 숫자와 순서가 정해져 있다. (실제 게임상에서는 B팀이 A팀의 순서는 알지만 순서에 매핑되어있는 숫자는 모른다.) B팀의 순서를 여러가지로 조합했을 때 얻을 수 있는 최대 승점이 몇인지 구한다. B팀이 배열될 수 있는 모든 경우의 수를 다 비교해 보고 그 상황에서의 승점들을 구해서 최대값을 구하면 된다. 만약 전체 모든 경우의 수를 다 확인하고, 그 안에서 내가 원하는 값을 찾는 탐색 법으로 풀수 있다. 하지만 B가 최대 승점으로 이긴다는 조건이 있고, 이 조건에 맞는 조합을 재연해 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 예산 각 지방에서 신청한 예산안 들이 있는데, 국가의 총 예산을 넘지 않는 선에서 수용 가능한 최대 상한가를 구하라는 문제이다. 예산의 상한가가 정해지면, 요청된 예산이 상한가보다 크거나 같을 경우 상한가 만큼만 지급하고, 상한값보다 작으면 신청된 예산값만 지급한다. 각 지방에서 신청한 예산 액이 있고, 이 예산액의 총 합이 국가에서 지정한 총예산값을 넘기면 안된다. 특정 상한값을 정하고 상한값보다 큰 경우 상한값 만큼만 제공한다. 상한값을 찾아내는것이 문제의 핵심이다. 이진탐색 주어진 데이터에서 내가 원하는 특정 데이터를 찾아내는것을 `탐색` 이라고 한다. 가장 단순한 방법은 모든 경우의 수 0에서부터 최대값 사이..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 정렬 여러개의 정수가 주어지는데, 이 정수들의 숫자를 이어붙혀 만들 수 있는 수중 가장 큰 숫자를 구한다. 6, 10 2 세개의 숫자가 주어졌다고 가정, 이때 가능한 조합은 6가지가 나온다. 그중 가장 큰 수는 6210이 된다. 핵심은 배열의 모든 요소를 사용하는 경우의 수를 모두 구하고 그중 가장 큰 값을 구하는것이며, 이때 함정은 한자릿수 두자리수 한자릿수 합치면 4자리밖에 되지 않지만 만약 배열이 3자리수 10개로 구성된다면 총 30자리의 숫자가 만들어 진다. 이는 integer의 범위가 넘어간다. double을 사용한다고 하더라도 배열이 조금만 길어진다고 하더라도 범위를 넘어가므로 Long을 사용해야 한다. ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 탐욕법 현재(초기) 위치에서부터 모든 아파트를 순회한다. 현재 위치가 전파범위에 속하는지 확인하고 전파 범위가 아니라면 일단 기지국을 세운다. 이때, 전파 범위의 효과가 최대가 되도록 전파 유효범위 만큼 이동하여 기지국을 설치한다. 전파가 끝나는 지점 이후부터 한칸씩 이동하면서 기지국을 설치한다. 설치 도중, 만약 이미 세워진 기지국의 점파범위 안으로 들어갈 경우 일단 해당 위치에도 설치한다. 다음 위치로 이동했는데, 이미 설치되어있는 기지국의 전파범위에 포함된다면 기지국의 범위 바깥으로 이동한다. 벗어난 뒤 계속해서 마지막 아파트까지 같은 작업을 반복한다. [풀이 1] Queue사용 import java.util...

문제 설명 정수 n과 정수 배열 numlist가 매개변수로 주어질 때, numlist에서 n의 배수가 아닌 수들을 제거한 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 10,000 1 ≤ numlist의 크기 ≤ 100 1 ≤ numlist의 원소 ≤ 100,000 입출력 예 n numlist result 3 [4, 5, 6, 7, 8 ,9, 10, 11, 12] [6, 9, 12] 5 [1, 9, 3, 10, 13, 5] [10, 5] 12 [2, 100, 120, 600, 12, 12] [120, 600, 12, 12] 입출력 예 #1 numlist에서 3의 배수만을 남긴 [6, 9, 12]를 return합니다. 입출력 예 #2 numlist에서 5의 배수만을 ..

문제 설명 정수 n이 매개변수로 주어질 때, n 이하의 홀수가 오름차순으로 담긴 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 100 입출력 예 n result 10 [1, 3, 5, 7, 9] 15 [1, 3, 5, 7, 9, 11, 13, 15] 입출력 #1 10 이하의 홀수가 담긴 배열 [1, 3, 5, 7, 9]를 return합니다. 입출력 #1 15 이하의 홀수가 담긴 배열 [1, 3, 5, 7, 9, 11, 13, 15]를 return합니다. [나의 풀이] import java.util.stream.IntStream; class Solution { public int[] solution(int n) { return IntStream.rangeClosed(..

문제 설명 순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 1,000,000 입출력 예 n result 20 6 100 9 입출력 예 #1 n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다. 입출력 예 #2 n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므..

문제 설명 어떤 자연수를 제곱했을 때 나오는 정수를 제곱수라고 합니다. 정수 n이 매개변수로 주어질 때, n이 제곱수라면 1을 아니라면 2를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 1,000,000 입출력 예 n result 144 1 976 2 입출력 예 #1 144는 12의 제곱이므로 제곱수입니다. 따라서 1을 return합니다. 입출력 예 #2 976은 제곱수가 아닙니다. 따라서 2를 return합니다. [나의 풀이] class Solution { public int solution(int n) { return Math.sqrt(n) % 1 == 0.0 ? 1 : 2; } } Math 라이브러리에서 제곱근을 구하는 sqrt를 활용하였다. sqrt의 반환타입은 ..

문제 설명 정수 리스트 num_list와 정수 n이 주어질 때, num_list의 첫 번째 원소부터 n 번째 원소까지의 모든 원소를 담은 리스트를 return하도록 solution 함수를 완성해주세요. 제한사항 2 ≤ num_list의 길이 ≤ 30 1 ≤ num_list의 원소 ≤ 9 1 ≤ n ≤ num_list의 길이 ___ 입출력 예 num_list n result [2, 1, 6] 1 [2] [5, 2, 1, 7, 5] 3 [5, 2, 1] 입출력 예 #1 [2, 1, 6]의 첫 번째 원소부터 첫 번째 원소까지의 모든 원소는 [2]입니다. 입출력 예 #2 [5, 2, 1, 7, 5]의 첫 번째 원소부터 세 번째 원소까지의 모든 원소는 [5, 2, 1]입니다. [나의 풀이] import java...

문제 설명 정수 리스트 num_list가 주어질 때, 마지막 원소가 그전 원소보다 크면 마지막 원소에서 그전 원소를 뺀 값을 마지막 원소가 그전 원소보다 크지 않다면 마지막 원소를 두 배한 값을 추가하여 return하도록 solution 함수를 완성해주세요. 제한사항 2 ≤ num_list의 길이 ≤ 10 1 ≤ num_list의 원소 ≤ 9 입출력 예 num_list result [2, 1, 6] [2, 1, 6, 5] [5, 2, 1, 7, 5] [5, 2, 1, 7, 5, 10] 입출력 예 #1 마지막 원소인 6이 그전 원소인 1보다 크기 때문에 6 - 1인 5를 추가해 return합니다. 입출력 예 #2 마지막 원소인 5가 그전 원소인 7보다 크지 않기 때문에 5의 두 배인 10을 추가해 retu..