알고리즘 풀이
-
백준 11650번 좌표 정렬하기 :: 마이구미알고리즘 풀이/정렬 2016. 10. 19. 00:45
이번 글은 백준 11650번 좌표 정렬하기 문제를 다룰 것이다.문제는 간단하다.백준 11650번 좌표 정렬하기https://www.acmicpc.net/problem/11650백준 11650번 좌표 정렬하기 2https://www.acmicpc.net/problem/11651 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 문제에 보다시피 정렬하는 문제이다. 1차원적인 문제라면 정렬 문제는 정말 쉽다. 본인의 경우는 큰 어려움이 없는 한 Arrays.sort()를 통해 처리한다. 하지만 이렇게 2개 이상의 기준을 가진다면 조금 까다롭게 느껴진다. 이전 글에서도 정렬 문제를 다룬 적이 2번 있다...
-
백준 1158번 조세퍼스 문제 :: 마이구미알고리즘 풀이/스택, 큐 2016. 10. 18. 21:04
이번 문제는 백준 1158번 조세퍼스 문제를 다룰 것이다.이미 요세푸스의 문제로 많이 알려져있는 대중화된 문제이다.Github - https://github.com/hotehrud/acmicpc 조세퍼스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 이다.N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오. 본인은 보자마자 그냥 원이니..
-
백준 3053번 택시 기하학 :: 마이구미알고리즘 풀이/수학 2016. 10. 18. 20:28
이번 글은 백준 알고리즘 3053번 "택시 기하학" 을 다뤄본다.문제 이름 그대로 택시 기하학에 관한 문제이다.문제는 아래와 같다. 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.D(T1,T2) = |x1-x2| + |y1-y2|두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오. 유클리드 기하학과 ..
-
백준 11279번 최대 힙 [Heap] :: 마이구미알고리즘 풀이/스택, 큐 2016. 8. 7. 14:50
이번 글은 백준 알고리즘 사이트 11279번 '최대 힙' 문제를 알아볼 것이다.자료구조 중 힙 에 관한 문제이다.Github - https://github.com/hotehrud/acmicpc 힙은 트리를 기반으로 된 자료구조다.일단 이것만 기억하면 된다.힙은 완전 이진 트리이다.이진트리는 자식노드가 최대 2개인 트리이지 않느냐?또한 균형이 잡혀있는 트리이다. 힙은 최대 힙과 최소 힙으로 나눌 수 있다.아래 그림처럼 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 구조이다.최소 힙은 당연히 반대이다. 당연히 힙으로 푼다.혹시 이전 글 10814번 나이순 정렬 글을 보면 좋다.http://mygumi.tistory.com/44 이번에도 우선순위 큐로 문제를 해결할 것이다.나는 그냥 최대 힙을 구현해서..
-
백준 10814번 나이순 정렬 [Queue] :: 마이구미알고리즘 풀이/스택, 큐 2016. 8. 3. 18:57
이번 글은 백준 알고리즘 10814번 "나이순 정렬"에 대해 알아볼 것이다.본인은 다르게 풀었지만 다른 사람이 푼 것을 보고 이 글의 메인을 정했다.PriorityQueue 우선순위 큐를 통해 문제를 해결해보자.Github - https://github.com/hotehrud/acmicpc 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이 때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 큐는 모두 알다고 가정한다.큐에는 원형 큐, 우선순위 큐, 덱큐가 있다.PriorityQueue 이녀석은 해석하면 알겠지만 우선순위 큐이다.우선순위 큐는 말 그대로 우선순위가 높은 데이터를 먼저 꺼내온다. 이번 문제는 이해..
-
백준 1010번 다리 놓기 [고등수학 조합] :: 마이구미알고리즘 풀이/수학 2016. 7. 27. 17:47
이번 글은 백준 알고리즘 사이트 1010번 다리놓기에 대해 알아볼 것이다.재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다...
-
백준 1834번 나머지와 몫이 같은 수 :: 마이구미알고리즘 풀이/수학 2016. 7. 19. 16:25
이번 글은 백준 알고리즘 1834번 문제를 다뤄보겠다.문제의 제목은 "나머지와 몫이 같은 수" ..흠 뭔가 쉬워보인다.하지만 정답률은 34% 낮은 편이다. 난 수학을 좋아했지만 못한다....난 그냥 노가다다.. 걍 노가다 하다보면 규칙이 나올 때가 있지 않느냐?이 문제도 그렇다. 일단 문제를 보자.N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.문제는 쉽게 이해할 수 있을 것이다.이런 문제 나오면 난 그냥 규칙부터 찾아본다.일단 나머지는 나누는 수보다 클 수 없을테고...뭐 이런 것들 생각해볼 수도 있지만 일단 걍 해보자. N = 1일때는 없군,N = 2일때는..
-
백준 1157번 단어 공부 [아스키 코드] :: 마이구미알고리즘 풀이/수학 2016. 6. 28. 16:11
이번 글은 백준 알고리즘 1157번 단어 공부 문제를 풀어보겠다.문제는 간단하다.알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오.단, 대문자와 소문자를 구분하지 않는다. 어떻게 접근하겠는가?사람마다 당연히 다르겠지..?나는 아스키 코드를 사용해봐야겠다고 생각이 들었다.아스키 코드를 어떻게 활용해서 문제를 풀 지 한 번 생각해보고 읽기 바란다. 다들 아스키 코드 잘 알고 있을 것이다.문제에서는 알파벳만을 사용하므로 65번부터 122번 까지만 사용하면 된다. 일단 먼저 크기가 26인 배열을 선언할 것이다.왜 26만 선언할까?? 눈치 챘을거다. 알파벳의 갯수는 26개이다. int[] arr = new int[26]; String str = ..