알고리즘
-
백준 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이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오. 유클리드 기하학과 ..
-
백준 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 = ..
-
백준 1003번 피보나치 함수 :: 마이구미알고리즘 풀이/수학 2016. 6. 15. 22:07
이번 글은 백준 알고리즘 문제 1003번 "피보나치 함수"에 대해 다뤄본다.피보나치 수는 너무도 대중적이기에 많이 들어보았으리라 생각한다.' 0 1 1 2 3 5 8 13 21 34 55.......' 일단 문제를 보자. n번째 피보나치 수를 구하는 과정에서 재귀를 통해 돌아갈 때 n이 0일 때와 1일 때의 경우가 얼마나 되는지 카운트를 구하는 문제이다. 먼저 순수한 방법으로 풀어보자.위 그림에 있는 소스를 활용해서 0일때 1일때 카운트 변수 만들어서 if문 들어가면 ++해주면 된다. 이렇게 하더라도 사실상 원하는 결과값이 나온다.알고리즘 문제에는 시간 제한이 있다.그 말은 막 짜면 안되고, 문제가 원하는 로직은 꼭 존재한다.그걸 캐치하여 최소한의 시간으로 돌아가도록 소스를 짜야한다. (속도를 고려하는 ..