hyunsix의 개발블로그

1814 : 삽입정렬 횟수 세기 제한시간1000 ms 메모리제한32 MB 해결횟수345 회 시도횟수463 회 문제 임의의 서로 같지 않은 수로 이루어진 수열 A를 삽입정렬을 하고자 한다. 만약 배열 A에 20, 40, 30, 10 이 들어갈 경우 다음과 같이 삽입정렬이 이루어진다. i = 1 일 때 20, 40, 30, 10 이동수 : 0 i = 2 일 때 20, 40, 30, 10 이동수 : 0 i = 3 일 때 20, 30, 40, 10 이동수 : 1 (40이 움직이고 30이 들어감) i = 4 일 때 10, 20, 30, 40 이동수 : 3 (20, 30, 40 이 움직이고 10이 들어감) 총 4번의 밀어내기를 통하여 삽입정렬이 완료된다. 임의의 수열 A가 주어질 경우, 수열의 숫자가 얼마나 이동하..

1158 : 삽입정렬 제한시간1000 ms 메모리제한32 MB 해결횟수692 회 시도횟수1120 회 문제 삽입정렬(Insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법이다. 수열이 {5 4 3 7 6}이 있을 경우의 삽입정렬 과정은 다음과 같다. 처음상태에서 처음 값 5 앞에 아무것도 없으므로 5는 이미 정렬된 상태가 되므로, 이후 4부터 정렬과정을 살펴보자. ※ 3단계의 경우 7은 앞의 "3 4 5"보다 크므로 제자리에 삽입된다. n개의 수열이 주어지면 위와 같은 방법으로 정렬하는 과정 각 단계를 출력하는 프로그램을 작성하시오. 입력형식 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0..

1146 : 선택정렬 제한시간1000 ms 메모리제한32 MB 해결횟수694 회 시도횟수1414 회 문제 선택 정렬(selection sort)이란 내부정렬 알고리즘의 하나로 다음 순서대로 실행하여 정렬을 한다. 1. 주어진 수열 중에 최소값(같은 값이 여러 개 있는 경우 처음 값)을 찾는다. 2. 찾은 최소값을 맨 앞의 값과 자리를 바꾼다. 3. 맨 앞의 값을 뺀 나머지 수열을 같은 방법으로 전체 개수-1번 반복 실행한다. n개의 주어진 수열을 위와 같은 방법으로 정렬한다. 수열이 주어지면 선택정렬의 과정을 한 단계씩 출력한다.​ 입력형식 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다. 출력형식 처음 상태를 제외하고 정렬과정의 각 단계별 결..

1697 : 큐(queue) 제한시간1000 ms 메모리제한32 MB 해결횟수1750 회 시도횟수3419 회 문제 큐는 먼저 들어온 데이터가 먼저 출력된다. 이러한 구조를 선입선출(FIFO - First In First Out)이라고 한다. 이러한 큐 자료구조는 보통 우리의 생활에서는 매우 일상적인 자료구조이다. 큐 자료구조의 형태를 가장 흔히 볼 수 있는 게 “줄서기”가 될 것이다. 은행 창구에서 줄을 서거나, 버스를 기다리기 위해서 줄을 설 경우 가장 먼저 줄을 선 사람이 가장 먼저 은행 업무를 처리하거나, 버스를 타게 된다.(새치기 하는 경우는 생각하지 말자) 그림과 같은 큐 자료구조를 설계하고, 처리조건에 맞는 출력을 하시오. ≪처리조건≫ 1. 주어지는 명령은 다음의 3가지이다. 2. "i a"는..

1102 : 스택 (stack) 제한시간1000 ms 메모리제한32 MB 해결횟수2801 회 시도횟수4816 회 문제 Stack은 "더미"란 뜻을 가진다. 책 더미, 신문 더미 등에 사용하는 단어이다. 책 더미를 예로 들어 보자. 책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다. 다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력). 자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack하고 한다. 이러한 Stack의 특징 때문에 흔히 "FILO(First-In-Last-Out : 선입후출)" 혹은 "LIFO(Last-In-First-Out : ..

3427 : 볼 모으기(balls) 제한시간1000 ms 메모리제한1024 MB 해결횟수453 회 시도횟수1536 회 문제 빨간색 볼과 파란색 볼이 에서 보인 것처럼 일직선상에 섞여 놓여 있을때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다. 1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도..

1031 : 빙고 제한시간1000 ms 메모리제한32 MB 해결횟수633 회 시도횟수1467 회 문제 빙고 게임은 다음과 같은 방식으로 이루어진다. 먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다. 다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5 10 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다. 차례로 수를 지워가다가 같은 가로줄 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다. 이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데 가장 먼저 외치는 사람이 게임의 승자가 된다. 철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어..

1733 : 오목 제한시간1000 ms 메모리제한32 MB 해결횟수791 회 시도횟수4692 회 문제 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이..

1311 : 카드게임 제한시간1000 ms 메모리제한32 MB 해결횟수465 회 시도횟수1545 회 문제 근우는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4x9)장이다. 근우가 배운 카드 게임은 36장의 카드에서 5장을 뽑고, 아래와 같은 규칙으로 점수를 계산하는 것이다. 각 카드는 다음과 같이 나타낸다. 카드의 색깔은 영어 대문자 R, B, Y, G로 나타내는데, R은 빨간색, B는 파란색, Y는 노란색, G는 녹색을 뜻한다. 예를 들어서 Y8은 노란색 8을 나타내고, B5는 파란색 5를 나타낸다. ① 카드 5장이 모두 같은 색이면서 숫자가 연속적일 때, 점수는 ..

1671 : 색종이(중) 제한시간1000 ms 메모리제한3 MB 해결횟수727 회 시도횟수1577 회 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다. 입력형식 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지..