L.O.K

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 1. 문제 추상화 X좌표와 Y좌표가 주어질 때, X좌표의 내림차순으로 정렬하라. X좌표가 같으면 Y좌표의 내림차순으로 정렬하라. 2. 알고리즘 1. X좌표와 Y좌표를 저장할 수 있는 이차원 배열을 생성한다. 2. X좌표의 내림차순으로 비교하다가 X좌표가 같은 경우 Y좌표의 내림차순으로 비교하는 조건을 분기한다. 퀵정렬, 병합정렬, 힙정렬을 사용하였다. 버블정렬은 시간초과가 나고 카운팅정렬은 메모리초과가 났다. ..

1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 주어진 수의 각 자리수를 내림차순으로 정렬하시오 2. 알고리즘 1. 수를 문자열로 받는다. 2. 문자열의 길이만큼 정수 배열을 생성한다. 3. 문자열의 각 문자를 배열에 정수로 저장한다. 4. 내림차순 정렬을 한다. 1번 - 3번까지의 코드는 아래와 같다. // 1. 수를 문자열로 받기 public static void setInputData() { Scanner sc = new Scanner(System.in); input = sc.next(); } // 2. 문자열의 길이만큼 정수배열 생성하기 public static void ..

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 문제 추상화 주어진 수들의 산술평균, 중앙값, 최빈값, 범위를 구하시오. 2. 알고리즘 1) 정렬 알고리즘 퀵정렬, 합병정렬, 카운팅 정렬, 힙정렬로 풀어볼 것이다. ( 참고로 버블정렬은 시간초과가 난다. ) (각 정렬의 알고리즘은 아래 포스팅을 참고바랍니다!) [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(..

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 N개의 수를 오름차순 정렬 하시오. 2. 알고리즘 카운팅 정렬을 사용하는 문제이다. 카운팅 정렬은 퀵, 병합, 힙 정렬같이 복잡하지 않고 단순하고 직관적이다. 시간복잡도도 O(N)으로 굉장히 빠르다. 이해하기 쉽고 빠르다는 장점이 있지만 많은 수의 정렬은 힘들다. 1. 입력받은 N개의 수를 배열에 저장하고 제일 큰 값을 구한다. 2. 제일 큰 값이 10이므로 배열의 크기가 ( 10 + 1 )인 카운팅 배열 하나를 생성한다. 3. 입력받은 수와 대응하는 인덱스가 가..

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 추상화 주어진 수의 나열을 시간복잡도 O(NlogN) 이상의 알고리즘으로 오름차순 정렬하라. 2. 알고리즘 O(NlogN) 시간복잡도는 정렬을 두 구간으로 분할정복할 때의 시간복잡도이다. N개의 수를 N번 비교하면 O(N2) ( 버블정렬 ) N개의 수를 분할한 수만큼 비교하면 O(NlogN) ( 퀵정렬, 병합정렬 ) 퀵정렬은 최악의 경우 O(N2)의 시간복잡도를 가진다. 테스트케이스 중 퀵정렬 저격용 최악의 경우도 있기 때문에 웬만하면 병합..

2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 추상화 N개의 수가 주어졌을 때, 오름차순으로 정렬하시오. 2. 알고리즘 ( 아래 포스팅에 정리해두었으니 참고바랍니다. ) [ JAVA ] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 그러니 일반적인 버블정렬과 버블정렬의 효율을 높이는 방법 두 가지를 소개하겠다. 7개의 lordofkangs.tistory.com 3. 코드 구현 3-1) 버블정렬 코드 //..

1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 1. 문제 추상화 "666"이 들어간 수를 작은 순서대로 시리즈 넘버로 한다. N번째 시리즈의 번호를 구하라. 2. 알고리즘 API를 이용하면 굉장히 쉽게 풀 수 있는 문제다. String 객체의 contains() 메소드를 이용하여, 작은 수부터 666이 들어간 모든 경우의 수를 조사하면 된다. [ 브루트 포스 ] 그러나 나는 규칙성을 찾는 도중 재귀함수 냄새를 맡았고 재귀함수로 풀려다가 실패했다. contains() 메소드를 알고 있었지만 기억하지 못했다...

1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 1. 문제 추상화 M X N 크기의 보드를 8X8로 잘라 체스판을 만들려 한다. M X N의 보드는 격자마다 무작위로 색칠되어 있을 때, 어느 부분을 8X8로 잘라야 최소한의 색칠로 8X8체스판을 만들 수 있을까? ( 체스판은 격자간 색깔이 겹치면 안 된다. ) 2. 알고리즘 알고리즘 구상은 쉬우나 사소한 조건을 놓칠 수 있어 코드 구현이 만만치 않은 문제이다. 나는 두 가지 방법으로 풀었다. 첫 번째 방법은 나의 알고리즘이고 두 번째 방법은 인터넷에서 ..

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 1. 문제 추상화 A(x, y), B(p, q)에서 x > p 그리고 y > q 이면 A가 B보다 크다고 할 때,입력된 값들의 크기 순위를 매겨라. 순위는 자신보다 큰 수의 개수 + 1이다. 2. 알고리즘 풀이는 쉽지만 문제 뉘앙스가 헷갈릴 여지가 있다. 상식적으로 몸무게가 같고 키가 크면 덩치가 더 크다 말할 수 있다. 그러나 여기서는 아니다. 키와 몸무게가 둘 다 커야 덩치가 큰거다. 문제를 풀 때는 상식이 아닌 조건으로 풀어야 한다. 1. 이차..

2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1. 문제 추상화 임의의 값 M이 주어질 때, M의 생성자(N) 중 최소값을 구하라. ( 생성자(N)는 생성자와 생성자 각 자리 수의 합이 M과 같은 수를 의미한다. ) 2. 알고리즘 생성자(N)의 각 자리수의 합을 SUM이라 하겠다. M = N + SUM 이므로 M > N이다. 그러므로 가장 쉬운 방법은 1부터 M까지 모든 경우의 수를 조사하는 방법이다. (브루트 포스) 그러나 M은 1 ≤ M ≤ 1,000,000 이므로 경우의 수..