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

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도 춰..

후위 표기식 2 후위 표기식2 - 백준 - 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위표기법 (postfix notation) 역폴란드 표기법(RPN, reverse Polish notation) 또는 후위 표기법(후치 표기법)(postfix notation)은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다. 수식을 계산할 때 특별한 변환이 필요 없이, 수식을 앞에서부터 읽어 나가면서 스택에 저장하면 된다는 장점이 있다. 중위표기법에서는 연산자의 우선순위가 모호해서 괄호가 필요한 경우가 ..

유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 먼저 MOD 연산에 대하여 이해하고 있어야 한다. 나머지 연산(modulo) 컴퓨터 프로그래밍 언어에서는 나머지 연산을 나타내는 기호로 사용한다. ex) mod 연산 14 mod 3 = 2 14 % 3 = 2 10 mod 5 = 0 10 % 5 = 0 2 mod 7 = 2 2 % 7 = 2 MOD 연산을 활용한 유클리드 호제법 1. 큰 수를 작은 수로 나누는 MOD연산 수행 2. 이전 단계의 작은 수와 MOD연산 결과 나온 나머지로 MOD연산 수행 3. 앞단계를 반복하며 나머지가 0이 될 때의 작은 수가 최대 공약수 최대공약수 (Greatest Common Divisor, GCD) 유클리드 호제법을 적용하여 최대공약수를 구해보자 유클리드 호제법 구현..