c++
-
JUNGOL 실력키우기 1158 : 삽입정렬보관함 2018. 11. 10. 17:02
삽입정렬(Insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법이다. 수열이 {5 4 3 7 6}이 있을 경우의 삽입정렬 과정은 다음과 같다. 처음상태에서 처음 값 5 앞에 아무것도 없으므로 5는 이미 정렬된 상태가 되므로, 이후 4부터 정렬과정을 살펴보자. ※ 3단계의 경우 7은 앞의 "3 4 5"보다 크므로 제자리에 삽입된다.n개의 수열이 주어지면 위와 같은 방법으로 정렬하는 과정 각 단계를 출력하는 프로그램을 작성하시오. 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다. 처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력예"와 같이 출력한다. 5..
-
JUNGOL 실력키우기 1146 : 선택정렬보관함 2018. 11. 8. 23:44
선택 정렬(selection sort)이란 내부정렬 알고리즘의 하나로 다음 순서대로 실행하여 정렬을 한다.1. 주어진 수열 중에 최소값(같은 값이 여러 개 있는 경우 처음 값)을 찾는다. 2. 찾은 최소값을 맨 앞의 값과 자리를 바꾼다. 3. 맨 앞의 값을 뺀 나머지 수열을 같은 방법으로 전체 개수-1번 반복 실행한다.n개의 주어진 수열을 위와 같은 방법으로 정렬한다.수열이 주어지면 선택정렬의 과정을 한 단계씩 출력한다. 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다. 처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력형식"과 같이 출력한다. 5 6 4 8 3 11 4 8 3 6 1 3 8 4 6 1 3 4 8 6 1 3 4 6 8 슬슬..
-
JUNGOL 실력키우기 1697 : 큐(queue)보관함 2018. 11. 8. 23:14
큐는 먼저 들어온 데이터가 먼저 출력된다. 이러한 구조를 선입선출(FIFO - First In First Out)이라고 한다. 이러한 큐 자료구조는 보통 우리의 생활에서는 매우 일상적인 자료구조이다. 큐 자료구조의 형태를 가장 흔히 볼 수 있는 게 “줄서기”가 될 것이다. 은행 창구에서 줄을 서거나, 버스를 기다리기 위해서 줄을 설 경우 가장 먼저 줄을 선 사람이 가장 먼저 은행 업무를 처리하거나, 버스를 타게 된다.(새치기 하는 경우는 생각하지 말자) 그림과 같은 큐 자료구조를 설계하고, 처리조건에 맞는 출력을 하시오. ≪처리조건≫ 1. 주어지는 명령은 다음의 3가지이다. 2. "i a"는 a라는 수를 큐에 넣는다. 이때, a는 10,000 이하의 자연수이다. 3. "o"는 큐에서 데이터를 빼고, 그 ..
-
JUNGOL 실력키우기 1102 : 스택 (stack)보관함 2018. 11. 7. 16:39
Stack은 "더미"란 뜻을 가진다. 책 더미, 신문 더미 등에 사용하는 단어이다. 책 더미를 예로 들어 보자. 책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다. 다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력).자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack하고 한다. 이러한 Stack의 특징 때문에 흔히 "FILO(First-In-Last-Out : 선입후출)" 혹은 "LIFO(Last-In-First-Out : 후입선출)"라고 한다. 그림과 같이 Stack을 설계하고 다음의 처리조건에 맞는 출력을 하시오. 주어진 명령은 다음의 3..
-
JUNGOL 실력키우기 1836 : 연속부분합 찾기보관함 2018. 11. 4. 21:03
N개의 정수를 담고 있는 배열이 주어졌을 때, 여기서 가능한 연속 부분합을 구하는 프로그램을 작성하라. 여기서 연속 합이라는 것은 배열에서 연속된 숫자들을 선택해서 합하였을 때의 값을 말한다. 아무 배열도 택하지 않는 경우도 연속된 배열합에 포함됨을 유의하자. 입력의 첫 번째 줄에는 정수 N(1≤N≤105)가 입력된다. 그리고 그 다음 줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 숫자의 범위는 -100이상 100이하의 정수다. 입력에 대한 가장 큰 연속 부분합을 출력한다. 4 1 2 -2 45 단순하게 생각하면 최소일 때 원소의 개수가 1개인 부분집합에서 최대일 때 원소의 개수가 모든 원소인 부분집합의 합 중 최댓값을 찾는 문제인 것 같습니다. 그렇다면 일단 입력을 배열(혹은 벡터 등)에 저장한..
-
JUNGOL 실력키우기 2259 : 참외밭보관함 2018. 10. 18. 12:17
시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다.문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다.유레카! 1㎡의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.1㎡의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다.참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다.다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다.밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다. 예를 들어 참외밭이 위 그림과 같..
-
JUNGOL 실력키우기 1998 : 수열보관함 2018. 10. 18. 11:39
0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함),혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 예를 들어 수열 1 2 2 4 4 5 7 7 2 의 경우에는 1≤2≤2≤4≤4≤5≤7≤7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4 1 3 3 2 2 9 2 3 의 경우에는 3≥3≥2≥2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1 5 3 6 4 7 1 3 2 9 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다. 첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가..
-
JUNGOL 실력키우기 1761 : 숫자 야구보관함 2018. 8. 26. 19:34
정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다. * 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) * 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) * 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 예) 영수가 324를 갖고 있으면 429는 1 스트라이크 1 볼이다. 241은 0 스트라이크 2 볼이다. 924는 2 스트라이크 0 볼이다. 영수는 민혁이가 말한..