마이구미의 HelloWorld 마이구미의 HelloWorld

이번 글은 백준 알고리즘 2875번 "대회 or 인턴" 을 다뤄본다.이 문제는 그리디 알고리즘으로 문제를 접근할 수 있다.그리디 알고리즘 - http://mygumi.tistory.com/1212875번 대회 or 인턴 - https://www.acmicpc.net/problem/2875 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다.백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것..

이번 글은 약수를 구하는 알고리즘을 다뤄본다.약수 구하는 방법은 어렵지 않다.하지만 조금만 응용된 약수 관련 문제라면 순수한 방법으로는 시간이 너무 오래걸린다.더 효율적인 방법을 알아볼 것이다. 약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수를 말하며, 배수 관계와 서로 반대되는 개념이다. 약수는 보통 정수에 대해 정의되지만, 일반화하여 정역에 대해 정의하기도 한다. 관련 문제를 보자. (약수 문제)기본적인 문제로써, 주어진 수(N)의 약수의 개수를 구하는 문제이다.가장 순수한 방법으로는 1부터 N까지 N의 나머지를 구해 0이라면 약수라고 판단한다. int n = sc.nextInt(); int cnt = 0; for(int i = 1; i

이번 글은 그리디(Greedy) 알고리즘에 대해 다뤄본다.그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불린다. 그리디 알고리즘은 간단히 정의하자면 아래와 같이 표현할 수 있다. 경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다. 여기서 최선이라고 생각하는 경우가 무엇인가?그것을 이해하면 그리디 알고리즘을 이해할 수 있다.쉽게 말하면, 전체를 고려하지 않고, 그 순간에서의 최선을 말한다.즉, 그때그때 더 좋아보이는 쪽을 선택하는 것이다.그렇기에 최종적으로는 그 선택이 최적이라고 확신할 수 없다. (문제에 따라 최적이라고 확신할 수도 있다.) 예를 들어, 지금은 초코파이를 먹을 수 있지만, 10분 후면 랍스타를 먹을 수 있다.그리디 알고리즘의 경우에..

이번 글은 백준 알고리즘 1946번 "신입사원" 을 다뤄본다.문제 해결법은 그리디 알고리즘이다.그리디 알고리즘 - http://mygumi.tistory.com/121 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않..

이번 글은 백준 알고리즘 12353번 "Baby Height" 를 다뤄본다.2013 Google code jam 문제이다.영어 문제라 번역이 필요하다. Every parent wants to know how tall their child will grow.모든 부모는 자녀들의 키가 얼마나 자라는 지 알고 싶어한다. Dr.Spaceman's algorithm, which we describe below.Dr.Spaceman의 알고리즘을 아래에서 설명하겠다. Accurately calculates, with errors low, Adult height of any child, with just genetics, yo!단순히 유전학으로 어떤 아이의 성인 신장을 낮은 오류와 함께 정확한 계산한다. Take th..

이번 글은 백준 알고리즘 1015번 "수열 정렬" 을 다뤄본다.문제 이름을 보다시피 정렬 관련 문제다. P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 문제의 키워드는 비내림차순과 사전순으로 볼 수 있다.문제를 해결하기 위해 수열 P를 구해보자. 적용하는 방법으로 나와있는 B..

이번 문제는 백준 알고리즘 12400번 "Speaking in Tongues" 를 다뤄본다.2012 Google Code Jam 에서 출제된 문제이다.영어로 된 문제이기 때문에 해석이 필요하다.해석만 가능하다면 굉장히 쉬운 문제이기 때문에 두려울 게 없다. 문제를 보자. (번역과 함께 보여주겠다) We have come with up the best possible language here at Google, called Googlerese.- 구글은 Googlerese라고 불리는 최고의 언어를 제시한다. To translate text into Googlerese, we take any message and replace each English letter with another English lett..

이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.플로이드 와샬 알고리즘을 통해 해결한다.백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의..