![]()
📕문제 세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자 형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다. 따라서, 아래 그림과 같이 생겼다. 세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다. 세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사 중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다. (0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오. 📕입력 첫째 줄에 도로의 가로 크기 N과 세로 크..
![]()
📕문제 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다. 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 예) 영수가 324를 갖고 있으면 429는 1 스트라이크 1 볼이다. 241은 0 스트라이크 2 볼이다. 924는 2 스트라이크 0 볼이다. 영수는 민혁이가 말한 수..
![]()
문제 요즘 민규네 동네에서는 스타트 링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩,... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카..
![]()
📕문제 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 💡문제 해석 전형적인 DP문제이다. 이중 포문을 사용 기준이 되는 원소와 처음부터 기준까지의 구간을 정함. 기준이 되는 원소가 구간 내의 원소보다 크다. (ary [i]>ary [j]) DP [i..
![]()
📕문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 📕입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)..
![]()
📕문제 8*8 크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다. 킹은 다음과 같이 움직일 수 있다. R : 한 칸 오른쪽으로 L : 한 칸 왼쪽으로 B : 한 칸 아래로 T : 한 칸 위로 RT : 오른쪽 위 대각선으로 LT : 왼쪽 위 대각선으로 RB : 오른쪽 아래 대각선으로 LB : 왼쪽 아래 대각선으로 체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 ..
![]()
📕문제 정수 집합 S가 주어졌을 때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자. 📕입력 첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다. 📕출력 첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다. 💡제한 1 ≤ L ≤ 50 집합 S에는 중복되는 정수가 없다. 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다. 1 ≤ n ≤ (집합 S에서 가장 큰 정수) ✔예제 입력 1 4 1 7 14 10 2..
sequential search(순차적 탐색) 순차적 탐색은 각 항목을 차례로 확인하여 우리가 탐색 중인 항목과 비교한다. 찾고자 하는 항목을 찾았거나, 모든 항목을 확인했는데 찾지 못했을 때에 멈춘다 Sorted Arrays [정렬된 배열] ascending order : 오름 차순 11 정렬된 배열에는 각 원소들이 순서대로 되어 있다. Binary search(이진 탐색) 정렬된 배열 이어야 한다. 탐색은 중간부터 시작하여 항목을 발견하거나 확인하지 않은 항목들 중 절반을 제거-> 다시 중간부터 시작-> 반복 배열의 원소의 개수가 20개 이하 일 때는 sequential search가 binary search보다 빠르다. [비교 횟수와 시간의 개념은 다르다] 비교 횟수는 항상 binary search..
Variable [변수] 값을 저장해두는 장소 memory의 특정 장소 simple variable, atomic variable [단순 변수] single value를 저장할 경우 분할 불가 composite variable [복합변수] 한 변수안에 여러개가 들어감. Composite Data types [복합자료형] Records [구조체] 여러항목들의 조합으로 이루어짐. 고용인 구조체 [ 이름, 나이, 월급] Arrays [ 배열] 같은 종류들로 이루어진 조합. index를 가짐. 집합과 유사함. Control Structures [제어 구조] 프로그램 내의 다른 명령들이 실행되는 순서를 결정하는 명령어 의사코드의 기능성에서 정의한 명령어들은? if, while 계수 제어 루프 이벤트 제어 루프
