소트인사이드 소트인사이드 - 백준 - 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 내림차순으로 수를 한 줄에 연속적으로 정렬하면 되는 문제이다. 이번 문제는 선택 정렬(Selection Sort)로 풀어보고자 한다. Selection Sort : 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다. 시간복잡도는 O(n²)으로 느린편이다. 선택 정렬 과정 1. 정렬하는 과정에서 정렬되지 않는 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택한 데이터를 swap 한다. 3. 가장 앞에 있는 데이터의 위치를..

시간복잡도와 공간복잡도 시간복잡도 (Time Complexity) 알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.(시간이 아니다.) 일반적으로는 1억 번의 연산을 1초로 예측한다고 한다. (CPU) 시간복잡도는 3가지 유형이 존재한다. 1. 빅-오메가(Ω(n)) 최선일 때(best case)의 연산 횟수를 나타낸 표기법 2. 빅-세타(Θ(n)) 보통일 때(average case)의 연산 횟수를 나타낸 표기법 3. 빅-오(O(n)) 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 일반적으로 최악의 경우를 염두에 두는 것이 안정적일 것이다. 또한 광범위한 데이터의 집합에 대하여 알고리즘을 적용시켜 평균값을 계산하는 것은 매우 어려울 수도 있다. 따라서 시간복잡도의 척도..

수 정렬하기 1 수 정렬하기 1 - 백준 - 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net n개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력하는 문제이다. 자바에는 sort로 손쉽게 풀 수 있다. 하지만 버블정렬(BubbleSort) 방법으로 풀어보고자 한다. Bubble Sort : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 원소의 이동이 거품이 수면위로 올라가 듯한 모습으로 보여 붙여진 이름이다. 버블 정렬은 두 인접한 데이터의 크기를 비교해서 정렬하는 방법이다. 시간복..

ACM 호텔 ACM 호텔 - 백준 - 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net N번째 손님이 H, W 크기의 호텔에서 특정순서대로 방배정이 된다면 몇 호에 투숙하게 되는지 구하는 문제이다. N 번째와 H(높이)를 이용하여 투숙할 층을 구한다. 나머지로 몇 층에 투숙하게 될지 알 수 있는데 만약 6층에 6번째 손님이 온다면 0층이 되므로 그때는 높이와 똑같이 6층으로 맞춰주는 조건을 추가해 준다. int floor = n % h; if(floor == 0) { floor = h; } strin..

직각삼각형 직각삼각형 - 백준 - 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 3개에 대한 입력에 대하여 직각삼각형인지를 판별하면 되는 문제이다. 피타고라스의 정리, 피타고라스의 정리 증명 피타고라스의 정리, 피타고라스의 정리 증명 학교를 졸업한 지 오랜 시간이 지난 분들도 1학기 때 공부했던 근의 공식과 이 글에서 공부할 피타고라스의 정리는 들으면 기억이 난다고 할 거에요. 피타고라스의 정리는 이처럼 학교를 졸업한 mathbang.net 위 링크는 피타고라스의 정리에 대해서 간략하게 설명이 되어있다. do - while문..

직사각형에서 탈출 직사각형에서 탈출 - 백준 - 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net (x, y)의 좌표가 주어지고 (w, h)의 직사각형의 크기가 주어진다. (x, y) 안에서 직사각형의 가장자리에 도달할 수 있는 가장 짧은 거리를 출력하면 되는 문제이다. int min = 1000; 문제의 최대 범위가 1000이므로 최솟값의 초기값을 1000으로 주었다. int case1 = w - x; int case2 = h - y; if(min >= x) { min = x; } if(m..

접미사 배열 접미사 배열 - 백준 - 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 접미사를 사전 순으로 배열하여 출력해야 한다. substring을 이용하면 어렵지 않게 풀 수 있었다. 입력받은 문자열의 길이만큼 배열의 크기를 선언해 주었다. int sLength = s.length(); String[] strArray = new String[sLength]; 접미사 이기 때문에 앞에서부터 잘라서 배열에 넣어주면 되겠다는 생각을 하였다. for(int i=0; i

춤 춤 - 백준 - 4836번: 춤 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 창영이가 춘 춤이 주어진다. 각 춤은 1000스텝을 넘지 않는다. 각 스텝 알파벳 소문자로 이루어져 www.acmicpc.net 문제가 무척 길어서 읽다가 이해를 포기하는 사람이 많아서 제출 횟수가 적지 않을까? 하는 생각이 든다. 문제를 풀기 위해 알고리즘적으로 알아야 하는 개념은 딱히 없었던 것 같고 자바의 문법을 어느정도 다루느냐와 문제를 읽는 끈기가 중요한 것 같다. 규칙 1. dip은 jiggle을 춘 다음이나 다다음, 또는 twirl을 추기 전에 출 수 있다. 2. 모든 춤은 clap stomp clap으로 끝나야 한다. 3. 만약 twirl을 췄다면, hop도 춰..