Algorithm Cinema

18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 주어진 정수들의 Ranking을 매기는 문제이다. 적절한 자료구조를 활용해야겠다는 생각을 처음에 못하고 일단 정렬된 배열과 원본 배열을 만들어놓고, 이진탐색을 해보자.라는 생각을 했다. (시간제한이 빡세서) 일단 첫번째 정렬된 배열을 만들자. > 이건 좋은 아이디어. 애사당초에 ranking을 할때 정렬된 배열 하나는 꼭 있어야한다. 시간제한이 있으니 nlogn짜..

11650번: 좌표 정렬하기 (acmicpc.net) 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이 문제는 2차원 좌표평면의 좌표들의 순서를 정렬하는 문제이다. 첫번째 최우선의 정렬 기준은 x좌표 증가 순, 그리고 x좌표가 같다면 y좌표가 증가하는 순서로 정렬을 하는 것이다. 일단 나의 첫번째 시도는 x좌표 따로, y좌표 따로 , 그 다음 이 두 x,y를 합친 배열 따로 총 3가지 배열을 다뤄보자하였다. 고민을 계속하다 보니 xy 좌표 를 따로 배열로 ..

10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수의 개수의 범위가 상당히 크다. 천만개.. 일단 시간복잡도를 고려하면 O(NlogN)을 사용해야할 생각을하겠다. 이 문제의 경우 하지만 더 좋은 시간복잡도를 활용할수있는 정렬 알고리즘이 있는데 바로 카운팅 정렬이다. 카운팅 정렬은 일반적으로 이 문제와 같이 input받는 정수의 범위가 주어질때 유용하다. 시간복잡도는 O(N+K)이지만. 이상적으로 웬만하면 O(N)에 수렴한다. 즉 상당히 효율적인 정렬이라고 할 수 있다. 또한 ..

1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이해하기는 쉬운 문제였다만 코드로 구현하기 어려웠다. *문제파악 문제의 첫 조건 1. M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. >> MxN 즉 , 이 전체의 틀은 직사각형일수도 있고 정사각형일 수도 있지만 이들을 8x8 짜리 정사각형으로 강제로 만들어서 이상적인 체스판을..

24313번: 알고리즘 수업 - 점근적 표기 1 (acmicpc.net) 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 이게 전제조건인데 보면 주어진 양수 이상의 모든 구간에 대해 저 조건을 만족하는것을 O()로 정의했다.사실 "여기서 o(N)의 정의를 만족하는지 물어봤기에 G(N)= N인것을 알 수 있고이제는 f(n) ≤..

10798번: 세로읽기 (acmicpc.net) 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 5개의 단어를 입력받아 이를 세로로 읽은 값을 띄어쓰기 없이 출력하는 프로그램이다. 각각의 다른 단어들의 글자 순서대로 출력을 하는 것이니까 2중배열을 쓴다면 간단히 해결될 것 같았다. 여기서의 중요한 점은 단어들의 글자수가 다를 수 있다는 것. 예를들어 apple banana 1234 ABee3 답 = ab1Apa2Bpn3ela4een43n3a 마지막 n3이나 a같은 경우 다른 단어들의 알파벳이 없기에 이렇..