알고리즘 풀이/수학
-
백준 6378번 디지털 루트 :: 마이구미알고리즘 풀이/수학 2017. 11. 12. 22:31
이 글은 백준 알고리즘 문제 6378번 "디지털 루트" 를 풀이한다.문제는 단순한 구현이지만, 디지털 루트란 용어와 관련 공식이 실제로 존재하기 때문에 다루게 되었다.위키 - https://en.wikipedia.org/wiki/Digital_root문제 링크 - https://www.acmicpc.net/problem/6378 양의 정수 N의 디지털 루트를 구하려면 N을 이루고 있는 모든 자리수를 더해야 한다. 이 때, 더한 값이 한 자리 숫자라면, 그 수가 N의 디지털 루트가 된다. 두 자리 이상 숫자인 경우에는 다시 그 수를 이루고 있는 모든 자리수를 더해야 하며, 한 자리 숫자가 될 때 까지 반복한다.24의 디지털 루트를 구해보자. 2+4=6이다. 6은 한 자리 숫자이기 때문에, 24의 디지털 루..
-
백준 14499번 주사위 굴리기 :: 마이구미알고리즘 풀이/수학 2017. 10. 29. 16:35
이 글은 백준 알고리즘 문제 14999번 "주사위 굴리기" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.특정한 알고리즘을 요구하지 않고, 단순히 문제의 이해를 통한 구현이다.https://www.acmicpc.net/problem/10775 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이..
-
백준 1342번 행복의 문자열 :: 마이구미알고리즘 풀이/수학 2017. 10. 15. 22:55
이 글은 백준 알고리즘 문제 1342번 "행복의 문자열" 을 풀이한다.순열(permutation) 알고리즘을 통해 문제를 해결할 수 있다.순열 알고리즘 이해 - http://mygumi.tistory.com/601342번 - https://www.acmicpc.net/problem/1342 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. 행복의 문자열의 예는 다음과 같다. aabbbaa=> aba..
-
백준 6591번 이항 쇼다운 :: 마이구미알고리즘 풀이/수학 2017. 9. 30. 23:50
이 글은 백준 알고리즘 문제 6591번 "이항 쇼다운" 을 풀이한다.조합에 관련된 시리즈 문제 중 하나이다.문제는 쉬워보이나 굉장히 낮은 정답 비율을 통해 만만치 않다는 것을 알 수 있다.6591번 - https://www.acmicpc.net/problem/6591 n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까? 문제의 설명에서 조합의 정의에 대해 그대로 명시했기 때문에, 조합 문제인 것을 알 수 있다.다른 관련 문제들은 단순한 접근 또는 동적계획법을 통해 해결할 수 있다.하지만 이 문제는 다르게 접근해야한다. 우리는 실제로 수학 문제를 풀 때, 1번을 이용해서 조합 문제를 해결한다.다음과 같이 풀 수 있다. 10C4 => (10*9*8*7) / (4*3*2*1)10C3 =>..
-
백준 14717번 앉았다 :: 마이구미알고리즘 풀이/수학 2017. 9. 25. 19:39
이 글은 백준 알고리즘 문제 14717번 "앉았다" 를 풀이한다.수학 과정 중 "조합" 을 활용하여 문제를 해결할 수 있다.최근 충남대에서 열린 "생각하는 프로그래밍 대회" 에 출제되었다.문제 14717번 - https://www.acmicpc.net/problem/14717 섰다는 화투를 이용하여 20장의 카드를 가지고 2명 이상이 경기를 하는 게임이다.이러한 섰다의 규칙을 단순화한 게임이 바로 '앉았다'이다.앉았다의 규칙은 1, 2, 3, ... , 9, 10이 쓰인 카드가 각 2장씩 주어지며 총 20장의 카드가 사용되며, 2명이 참가한다.다음은 앉았다의 경기 방법이다.두 명의 참가자는 순서대로 20장의 카드 중 무작위로 2장의 카드를 가져온다.상대방이 이미 가지고 간 카드를 중복해서 가져올 수는 없..
-
백준 5052번 전화번호 목록 :: 마이구미알고리즘 풀이/수학 2017. 9. 17. 12:55
이 글은 백준 알고리즘 문제 5052번 "전화번호 목록" 을 풀이한다.해싱, 트리와 같은 자료구조를 통해 해결할 수 있다.본인은 논리적 사고를 통한 센스로 문제를 쉽게 풀이하는 것을 다뤄본다.5052번 "전화번호 목록" - https://www.acmicpc.net/problem/5052 전화번호 목록이 주어진다. 이 때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자긴급전화: 911상근: 95 625 999선영: 91 12 54 26이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 ..
-
백준 2858번 기숙사 바닥 :: 마이구미알고리즘 풀이/수학 2017. 9. 12. 20:32
이 글은 백준 알고리즘 문제 2858번 "기숙사 바닥" 을 풀이한다.문제 풀이는 수학적 접근과 브루트 포스를 활용한다.문제 링크 - https://www.acmicpc.net/problem/2858 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다.수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이 때, 가장자리는 빨간색으로, 나머지는 갈색으로 채우려고 한다.아래 그림은 상근이의 방의 크기가 4*3일 때 이다.어느날 상근이네 방에 하근이가 놀러왔다. 하근이는 아름다운 타일 배치에 감동받았다. 다시 방으로 돌아온 하근이는 빨간색과 갈색 타일의 개수는 기억했지만, 방의 크기는 기억해내지 못했다.빨간색과 갈색 타일의 개수가 주어졌을 때, 상근이..
-
백준 1644번 소수의 연속합 :: 마이구미알고리즘 풀이/수학 2017. 9. 10. 12:04
이 글은 백준 알고리즘 문제 1644번 "소수의 연속합" 을 풀이한다.접근은 에라토스테네스의 체를 통해 소수를 구하고, 투 포인터 또는 슬라이드 윈도우를 적용했다.투 포인터 및 슬라이드 윈도우의 개념은 중요하지 않다.본인 또한 구현하니 위와 같이 불리는 방식이였다.에라토스테네스의 체는 다음 링크를 참고하자.소수를 위한 에라토스테네스의 체 - http://mygumi.tistory.com/661644번 문제 - https://www.acmicpc.net/problem/1644 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+1..