Algorithm Cinema

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

자료구조의 간략한 개념들을 JAVA로 학습을 해보자. 군휴학의 무료함을 달래주길. 자료구조의 모든 part는 객체이며 자바는 객체지향. 모든 흐름은 객체로.. 신입생때 뇌에 각인시키도록 학습했었다. 자료구조의 가장 basic하면서 중요한 type. 배열이다. 생성은 아래코드로 하는데 python과 다르게 JAVA는 상당히 피곤하게 아래처럼 배열의 데이터 타입과 크기를 꼭 지정해줘야한다. 위의 배열의 경우 10,20,30의 값만 선언해주었다. 하지만 네번째 인덱스에는 값을 넣어주지 않았다. 이럴때 numbers[3]을 해준다면.. 오류가 날까? 그렇지 않다. 크기엔 지정이됐지만 값이 없는 배열의의 값은 0으로 설정되어있다 자동으로 그래서 따로 주입하지 않아도 10 20 30 0 이 순서대로 저장되어있다 *..

2745번: 진법 변환 (acmicpc.net) 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제가 특이하다. n진법을 다루는 문제인데 처음에 약간 이해하기 빡셀수 있으나 몇번 예시를 들어보면 쉽다. input의 예시는 ZZZZZ 36. 10진법을 넘어가는 숫자는 대문자 알파벳으로 표시한다라고 했다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 35 35 35 35 35을 36진법으로 표현하는 프로그램을 짜는것. 복잡해보이지만 어려울것 없다. z 각각 한개는 자릿수를 구성하..

마틴 스코세이지 감독의 영화이다. 노장의 경험은 역시 어마어마 하다는 것을 알 수 가 있다. 개인적으로 스코세이지 감독 영화 중 가장 재밌게 봤던 것 같다. 그렇게 영화가 어렵지 않고 흥미롭게 볼 수 있다. 러닝타임이 3시간 40분짜리라 지루할꺼 같다고 생각할 필요가 전혀 없다. 바로 해석하겠다. 스포주의. 1. 역사 이 영화는 놀랍게도 "실화"이다 . 19세기 초반의 미국 동부지역에 있던 사람들을 이주시키기 위해 아메리카 원주민들을 강제 이주시키는 일이 있었다. 그때에 있던 오세이지 부족 사람들과 백인들간의 이야기들을 그린 영화이다. 오세이지 부족의 땅에 석유가 발견되자, 어마어마한 부를 축적한 오세이지 부족 사람들의 돈을 노렸던 백인들이 여러 횡령범죄 심지어 결혼을 하여 상속받으려는 그러한 범죄들이 ..

아리 애스터의 영화 중 가장 재밌게 봤던 영화다. 영화가 많이 난해하고 어렵다. 장르 또한 이게 공포인지 판타지인지 모를만큼 신선하고 재밌는 영화이다. 바로 해석을 적어보겠다. 주관적인 해석이니 참고해주시길! 아리 애스터의 , , 그리고 이 영화의 공통점은 '어머니'의 역할이 정말 강하고, '아버지'의 역할이 정말 약하다. 란 것이다. 이 영화에서는 아들인 '보'가 어머니를 찾으러가는 여정을 그린 영화다. 1. 영화의 핵심, 자작극 혹은 실제 그 과정에서 어머니 '모나'의 집에 가는 길에 많은 장애물들을 헤치고 헤쳐 결국 도달하는 그런 영화처럼 표면적으로 보이나, 중요한 것은 이 여러가지의 이벤트가 과연 실제인가?를 생각해봐야한다. 기본적으로 보의 엄마는 매우 강압적이고 통제적이다. 보는 성인이 된 지금..

2563번: 색종이 (acmicpc.net) 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 좌표평면을 다루는다는 생각으로 접근했다. X좌표의 MAX = 100, Y좌표의 MAX= 100. 100X100 짜리 좌표평면에 10X10짜리 정사각형 N개를 올리고, 이 N개들의 넓이의 영역을 구하는 문제이다. 10X10짜리 정사각형이 3개있고 이들이 자신들의 영역이 아닌 각자의 영역을 서로 침범할 경우 넓이의 영역이 300보다 작아지겠다. 이를 고려해야하는 문제임. 내 첫번째 접근은 패턴을 찾는 것이었다. input이 예를들어..

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