Algorithm Cinema

11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net) 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 부분 문자열의 갯수를 출력하는 문제이다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 즉 어떠한 문자열의 부분문자열들은 서로 겹치는게 분명히 존재하겠다. 겹치지 않는 부분문자열의 가짓수. 일단 겹치지 않는 조건중에 가장 잘 보이는건 글자의 갯수겠다. 사실 부분문자열을 영어로 해석하면 substring이다. 하지만 ..

1269번: 대칭 차집합 (acmicpc.net) 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 차집합에 관한 문제. 두가지 포인트를 보면 된다. 1. a-b 이땐 a의 집합에서 b의 집합이 겹칠경우 그 부분만 제외한다. 즉 a집합이 point이며, a-b집합은 a집합보다 클수없다. 2. b-a 위와 똑같지만 point가 b 즉 각각 중복된 요소를 찾아서 a집합, b집합에 겹친 부분집합을 뺴준다. 중복된 요소를 다루니 map을 활용하는게 편하겠다. 사실 아래 문제는 내가 바로 푼거라 지금 포스팅할때 봐..

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

고레에다 히로카즈 영화를 그렇게 좋아하지 않는데, 이 영화 만큼은 강추. 영화를 보고 이 글을 보면 더욱 더 재밌게 영화를 다시 즐길수 있을것이다. 스포주의.. 이 영화는 인물들의 시점에 따라 많이 달라진다. 따라서 조금은 어려울수도 있는데 히로카즈 영화중에선 제일 쉽다고 생각한다. 영화의 주된 흐름은 "거짓말의 결과"로 인한 여러 인물들의 오해에서 비롯된 상황이다. 시점에 따라 영화를 해석해보겠다. 1. 어머니, 사오리의 시점 싱글맘으로서 아들 미나토를 키우고있는 사오리는 극진하게 미나토를 돌봐주지만 이상한 행동을 하는 미나토를 보고 학교폭력을 의심하여 학교에 찾아간다. 사실은 학교폭력이 아닌, 담임 선생님인 호리 선생님이 미나토를 폭행했다는 말을 듣는다. 학교에서는 대충 사과만 하며 일을 대충 수습하..

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