Kangho_Story

알고리즘 분류백트래킹문제 설명자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력 설명첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력 설명한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력3 14 24 4예제 출력1231 21 31 42 32 43 4 1 2 3 4아이디어1~n까지 벡터에 push 하면서 재귀적으로 들어가다가 만약 벡터의 길이가 m과 같아지면 해당 벡터를 출력하고리턴하고..

알고리즘 분류그래프 이론그래프 탐색트리BFSDFS문제 설명루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.출력 설명첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.예제 입력71 66 33 54 12 44 7121 21 32 43 53 64 74 85 95 106 116 12예제 출력46131411233445566아이디어입력받은 값으로 그래프를 만든다.BFS로 그래프를 순회하면서 자신의 부모 노드를 기록하는 배열에 부모 노드를 기록한다.이후 2~n번의..

알고리즘 분류그래프 이론그래프 탐색BFS문제 설명네 개의 명령어 D, S, L, R을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.S: S 는 n에서 1을 뺀 결과 n-1을 레지스터에 저장한다. n이 0이라면 9999 가 대신 레지스터에 저장..

알고리즘 분류다이나믹 프로그래밍문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력 설명첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력 설명첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력610 20 10 30 20 50예제 출력4아이디어2중 for문 내에서 현재 위치의 숫자보다 더 작은 숫자가 존재하는지 보고 존재한다면 그 개수가 내가 기록한 ..

알고리즘 분류다이나믹 프로그래밍문제 설명 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.입력 설명첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼..

알고리즘 분류구현브루트포스 알고리즘투포인터문제 설명입력 설명출력 설명문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.예제 입력55 1 1 2 131 1 191 2 3 4 5 6 7 8 9예제 출력432아이디어과일을 하나씩 꽂다가 서로 다른 종류의 과일이 2개를 초과하면 서로 다른 종류의 과일이 2개 이하가 될 때까지 맨 처음 끼운 과일부터 뺀다.이때의 과일의 개수를 저장하여 저장된 과일의 개수 중 가장 큰 값을 출력한다.알고리즘과일을 입력받을 때마다 과일 수를 증가시키고 기존에 입력받은 적 없는 과일이라면 과일 종류도 증가시킨다.과일 종류가 2가지를 초과하면 2이하가 될 때까지 list의 front에서 pop..

알고리즘 분류수학자료구조조합론해시를 이용한 집합과 맵문제 설명해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까?입력 설명첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.모든 문자열은 1 이상 20 이..

알고리즘 분류그래프 이론그래프 탐색BFSDFS문제 설명적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 ..

5 51 2 3 4 55 4 3 2 12 3 4 5 66 5 4 3 21 2 1 2 1​알고리즘 분류구현브루트포스 알고리문제 설명폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대..

알고리즘 분류구현알고리즘문자열파싱덱문제 설명선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는..

알고리즘 분류자료구조우선순위 큐트리를 사용한 집합과 맵문제 설명이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q..

알고리즘 분류구현시뮬레이션문제 설명첫 번째 직사각형이 먼저 놓여 있고, 두 번째 직사각형이 그다음 놓아졌을 때 그 이후에 남아있는 첫 번째 직사각형의 잔해물을 덮기 위한 최소 직사각형의 넓이를 구하는 프로그램을 작성해 보세요.입력 설명첫 번째 줄에 첫 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.두 번째 줄에 두 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.-1,000 ≤ x1 -1,000 ≤ y1 출력 설명첫 번째 줄에 남아있는 첫 번째 직사각형의 잔해물을 덮기 위한 최소 직사각형의 넓이를 출력합니다.예제 입력2 1 7 45 -1 10 3예제 ..

알고리즘 분류구현브루트포스 알고리즘문제 설명N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.입력 설명첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.출력 설명첫째 줄에 정답 정사각형의 크기를 출력한다.예제 입력3 54210122100221012 212342 4125534551 10123456789011 109785409507205510369408613967613073207669123304949323002489689769239548798413000116700200958894..

알고리즘 분류시뮬레이션구현문제 설명일직선으로 무한히 나열된 타일이 있습니다. 아무 타일에서 시작하여 n번의 명령에 걸쳐 움직입니다. 명령은 "x L", "x R" 형태로만 주어지며, "x L"의 경우 왼쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 흰색으로 연속하게 칠하고, "x R"의 경우 오른쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 검은색으로 연속하게 칠함을 뜻합니다. 각 명령 이후에는 마지막으로 칠한 타일 위치에 서있는다고 가정합니다. 타일의 색은 덧칠해지면 마지막으로 칠해진 색으로 바뀌는데, 만약 타일 하나가 순서 상관없이 흰색과 검은색으로 각각 두 번 이상 칠해지면 회색으로 바뀌고 더 이상 바뀌지 않습니다. 모든 명령을 실행한 뒤의 흰색, 검은색, 회색의 타일 수를 각각 ..

알고리즘 분류구현자료구조큐문제 설명요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 N과 K가 빈칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)출력 설명예제와 같이 요세푸스 순열을 출력한다.예제 입력7 3예제 출력아이디어list..