Algorithm Cinema

1764번: 듣보잡 (acmicpc.net) 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 중복을 다루는 문제이다. 주어진 두번의 문자열들의 집합에서 , 중복되는걸 찾아서 사전순으로 return하라는 문제다. 중복을 다루니까 map을 활용하면 편하겠고 사전순으로 return.. > sort해야겠다는 생각 n.m의 max가 50만이니, 정렬할때 nlogn짜리 sort()메소드 활용. 이 정도의 아이디어만 있으면 쉽게 풀리겠다 ! 추가적인 tip이지만 Map.containsKey()의 시간복잡도는 평균적으로 ..

11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net) 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 아주 직관적이며 쉬운 문제다. >> 부분 문자열 영어로 하면 substring.. 자바에 substring()이라는 메소드가 있다 허허.. 그걸 써서 어느 자료구조에다 넣느냐가 문제인데, 부분 문자열에 불가피하게 중복이 생기기 때문에 map 구조를 활용하여 중복을 다루는것이 가장 현명해보인다. map을 생성해서 값을 put했다면 entry로 한바퀴 돌며 중복된값있나 체크하고 있다면 그 값을 1로 replace()해준다면 바로 문제가 풀린다. 여기서 point는 s..

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 다솜이가 포켓몬을 참 좋아하는갑다. 문제를 상당히 정성스럽게 만드셨다. 일단 문제를 보자마자 map을 만들어야겠다는 생각을했고 문제의 조건은 input값이 String일때 (포켓몬이름) 포켓몬 번호를 출력하고 input값이 Integer일때 (포켓몬 번호)일때 포켓몬 이름을 출력하라고 했다. 일반적으로 map을 사용할때, key > value를 얻는건 매우쉽다. 그냥 ..

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 좌표 를 따로 배열로 ..

입력되는 정수의 배열의 범위가 보장될때, 유용한 아주 간단하고 효율적인 좋은 알고리즘. package 정렬알고리즘; import java.io.*; //운팅 정렬(Counting Sort)은 정수 배열을 정렬하는 비교 없이 선형 시간에 수행되는 안정적인 정렬 알고리즘입니다 // 알고리즘은 입력 배열의 범위가 제한되어 있을 때 특히 유용합니다 public class 카운팅정렬 { public static void main(String[] args) throws IOException { int[] range = new int[10001]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parse..

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)에 수렴한다. 즉 상당히 효율적인 정렬이라고 할 수 있다. 또한 ..

두 정렬 모두 시간복잡도가 o(n^2)라 느리긴 하지만, 배워두면 쓸데가 있지 않을까 하고 포스팅해본다. 배열은 9 2 4 5 3 . 크기 5짜리라고 가정하자 1. 선택정렬 선택정렬의 컨셉은 간단히 말하면 최솟값을 0번째 인덱스에 집어 넣는다 생각해야한다. 첫번째 loop부터 살펴보자. i=0 & j = 1,2,3,4 i=0일때, minindex=0이겠다. 여기서 j=1,2,3,4로 움직이면서 첫번째 인덱스보다 다음인덱스가 작다면 minindex를 초기화하고 이를 j = 1,2,3,4 다 돌면 최종적으로 최소값을 지닌 인덱스가 나올 것이다. minindex = 1이라는 결론이 나오고. temp > arr[1] , arr[1] > arr[0] , arr[0] > temp( 즉 temp는 여기서 최솟값이겠다..

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) ≤..