제목 : 삽입 정렬 (Insertion Sort) - with Java기초적인 정렬 중, O(N2) 를 가진 방법이다.바로 직전에 선택 정렬 (Selection Sort) 에 대해서 주제를 다뤘는데,선택 정렬과 삽입 정렬은, 현재 인덱스 이전이 완벽하게 정렬 되어 있는가? 로 나뉜다고 생각한다.선택 정렬의 경우, 현재 인덱스 이전이 완벽하게 정렬되어 있다.삽입 정렬의 경우, 현재 인덱스 이전 요소들에 한하여, 해당 영역은 정렬되어 있다.하지만, 결과적으로 봤을 때 완벽하게 정렬되어 있지 않다.또 다른 관점에서 둘을 비교해 보자.Selection Sort 의 경우, i 번째 요소에 넣기 위한 "결과론적으로 완벽한" 요소를 찾는다.Insertion Sort 의 경우, i 번째 요소는 1 번째 부터,..
제목 : 선택 정렬 (Selection sort) 에 대하여 - With Java가장 기초적인 정렬 중 하나이다.시간 복잡도는 O(N2) 이다.나는 선택 정렬을 설명하기 위해 이러한 상황을 예시로 들고 싶다.상황 : 선생님이 걷어온 쪽지 시험을 학생의 고유 번호대로 상승하도록 정렬 해 달라고 부탁하셨다.그렇다면, 약 40장 정도가 존재한다고 가정한다면 나는 어떻게 정렬해야 할까?믈론 사람마다 종이를 순서대로 나열하는 데 있어 다른 방식이 있을 수도 있다.하지만, 1 번부터 찾고 왼쪽에 둔다. 그 다음 2 번을 찾아 1 번의 밑에 둔다.그리고 또 3 번을 찾고 2번의 밑에 둔다. 그리고 4번도...이러한 방식으로 1 번부터 40 번 까지 정렬 할 수 있다.이 방식이 바로 선택 정렬(Selectio..
제목 : 설탕 배달문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다.상근이는 지금 사탕가게에 설탕을 정확하게 N 킬로그램을 배달해야 한다.설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.봉지는 3 킬로그램 봉지와 5 킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.예를 들어, 18 킬로그램 설탕을 배달해야 할 때, 3 킬로그램 봉지 6 개를 가져가도 되지만,5 킬로그램 3 개 와 3 킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N 킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N 이 주어진다. (3 N 출력상근이가 배달하는 봉지의 최소 개수를 출력한다.만약, 정..
제목 : 체스판 다시 칠하기문제지민이는 자신의 저택에서 MN 개의 단위 정사각형으로 나누어져 있는 M x N 크기의 보드를 찾았다.어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.지민이는 이 보드를 잘라서 8 x 8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지 뿐이다.하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 x 8 크기의 체스판으로 잘라낸 후에,몇 개의 정사각형을 다시 칠해야..
제목 : 분수찾기문제무한히 큰 배열에 다음과 같이 분수들이 적혀있다.1/11/21/31/41/5...2/12/22/32/4......3/13/23/3.........4/14/2............5/1.................................이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> ... 와 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, ... 분수라고 하자.X 가 주어졌을 때, X 번째 분수를 구하는 프로그램을 작성하시오.입력첫째 줄에 X (1 X 출력첫째 줄에 분수를 출력한다.예제 입력 11예제 출력 11/1예제 입력 22예제 출력 21/2예제 입력 33예제 출력 32/1아마 단계별로 풀어보기 를 통해 알고리즘을 ..
제목 : 중앙 이동 알고리즘문제상근이는 친구들과 함께 SF 영화를 찍으려고 한다.이 영화는 외계 지형이 필요하다.실제로 우주선을 타고 와계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG 처리를 하려 한다.외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4 개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다. 정사각형의 각 변의 중앙에 점을 하나 추가한다.정사각형의 중심에 점을 하나 추가한다.초기 상태에서 위와 같은 과정을 한 번 거치면 총 4 개의 정사각형이 새로 생긴다.이와 같은 과정을 상근이가 만족할 때 까지 계속한다.아래 그림은 총 2 번 거쳤을 때 까지의 모습이다.상근이는 어떤 점은 한 개 보다 많은 정사..
제목 : 색종이문제가로, 세로의 크기가 각각 100 인 정사각형 모양의 흰색 도화지가 있다.이 도화지 위로 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를,색종이의 변과 도화지의 변이 평행하도록 붙인다.이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후, 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.예를 들어, 흰색 도화 위에 세 장의 검은색 색 종이를,그림과 같은 모양으로 붙였다면, 검은색 영역의 넓이는 260 이 된다.입력첫째 줄에 색종이의 수가 주어진다..이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.색종이를 붙인 위치는 두 개의 자연수로 주어진다.첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고,두 번쨰 자연수는 색종이..
문제 제목 : 행렬 덧셈문제N * M 크기의 두 행렬 A 와 B 가 주어졌을 때,두 행렬을 더하는 프로그램을 작성하시오.입력첫째 줄에 행렬의 크기 N 과 M 이 주어진다.둘째 줄 부터 N 개의 줄에, 행렬 A 의 원소 M 개가 차례대로 주어진다.이어서 N 개의 줄에 행렬 B 의 원소 M 개가 차례대로 주어진다.N 과 M 은 100 보다 작거나 같고, 행렬의 원소는 절대값이 100 보다 작거나 같은 정수이다.출력첫째 줄부터 N 개의 줄에 행렬 A 와 B 를 더한 행렬을 출력한다.행렬의 각 원소는 공백으로 구분한다.예제 입력 13 31 1 12 2 20 1 03 3 34 4 45 5 100예제 출력 14 4 46 6 65 6 100우선, 예제의 입력과 출력을 보면 알 수 있듯이,3 * 3 크기의 행렬의 덧셈..
문제 제목 : 크로아티아 알파벳문제예전에는 운영체제에서 크로아티아 알파벳을 입력 할 수가 없었다.따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.크로아티아 알파벳변경čc=ćc-dždz=đd-ljljnjnjšs=žz=예를 들어, ljes=njak 는,크로아티아 알파벳 6개 (lj, e, š, nj, a, k) 로 이루어져 있다.단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다.lj 와 nj 도 마찬가지이다.위 목록에 없는 알파벳은 한 글자씩 센다.입력첫째 줄에 최대 100 글자의 단어가 주어진다.알파벳 소문자와 -, = 로만 이루어져 있다.단어는 크로아티아 알파벳으로 이루어져 있다.문제 설명..
문제 제목 : 별 찍기 - 7문제예제를 보고 규칙을 유추 한 뒤에 별을 찍어 보세요.입력첫째 줄에 N ( 1 N 출력첫째 줄 부터 2 * N - 1 번째 줄 까지 차례대로 별을 출력한다.예제 입력 15예제 출력 1 * *** ***** **************** ******* ***** *** *별 찍기 문제는 하나의 방향으로 점화식이 만들어 지지만,이 문제는 혼란스럽게도, 증가와 감소의 경향을 동시에 보여주고 있다.먼저 확실히 해야 하는 것은, 공백(' ') 과 별('*') 이 순서대로 나온다는 것이다.공백의 증감, 별의 증감 요소를 살펴보는 것이다.예제 출력 1 을 살펴보면,먼저 공백이 줄어들며, 별이 점점 증가한다.중반 이후부터, 공백이 증가하며, 별이 점점 감소한다.그렇다..
