알고리즘 풀이/수학
-
백준 17143번 낚시왕 :: 마이구미알고리즘 풀이/수학 2019. 5. 30. 16:48
이 글은 백준 알고리즘 문제 17143번 "낚시왕" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 특정 알고리즘을 요구하는 것보다는 정확한 문제 이해를 통한 구현이다. 문제 링크 - https://www.acmicpc.net/problem/17143 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이..
-
백준 15685번 드래곤 커브 :: 마이구미알고리즘 풀이/수학 2018. 11. 17. 12:53
이 글은 백준 알고리즘 15685번 "드래곤 커브" 문제를 풀이한다.삼성 SW 역량 테스트의 문제로 출제된 적이 있다.시뮬레이션 문제로써, 난이도 있는 알고리즘을 요구하는 문제는 아니다.15685번 드래곤 커브 - https://www.acmicpc.net/problem/15685 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.시작 점시작 방향세대0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다...................................................................
-
백준 1652번 누울 자리를 찾아라 :: 마이구미알고리즘 풀이/수학 2018. 8. 14. 13:57
이 글은 백준 알고리즘 문제 1652번 "누울 자리를 찾아라" 를 풀이한다.제출량이 많고, 정답 비율이 40% 인 문제.DFS, BFS 문제처럼 보이지만, 쉽게 해결할 수 있는 문제이다.본인에게는 다른 접근을 생각하는 자극을 준 문제이다.문제 링크 - https://www.acmicpc.net/problem/1652 일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다..
-
백준 6064번 카잉 달력 :: 마이구미알고리즘 풀이/수학 2018. 7. 16. 12:44
이 글은 백준 알고리즘 문제 6064번 "카잉 달력" 을 풀이한다.일반적으로 시뮬레이션 문제라고 보이지만, 순수하게 접근하면 시간 초과를 초래한다.별도 알고리즘 지식이 아닌, 시간 초과를 해결하는 다른 접근을 요구한다.문제 링크 - https://www.acmicpc.net/problem/6064 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 ..
-
백준 14890번 경사로 :: 마이구미알고리즘 풀이/수학 2018. 4. 6. 18:41
이 글은 백준 알고리즘 문제 14890번 "경사로" 를 풀이한다.접근 방법은 단순 문제 이해를 통한 구현이 된다.2017 삼성 SW 역량 테스트 기출문제이다.문제 링크 - https://www.acmicpc.net/problem/14890 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.경사로는 낮은..
-
백준 10837번 동전 게임 :: 마이구미알고리즘 풀이/수학 2018. 4. 1. 21:46
이 글은 백준 알고리즘 문제 10837번 "동전 게임" 을 다뤄본다.정올(KOI) 중등부, 고등부 출제 문제이다.규칙을 찾아 단순한 구현을 통해 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/10837 영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다. 위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 ..
-
백준 1244번 스위치 켜고 끄기 :: 마이구미알고리즘 풀이/수학 2018. 3. 6. 19:59
이 글은 백준 알고리즘 문제 1244번 "스위치 켜고 끄기" 를 풀이한다.정올 초등부에서 출제된 문제로써, 단순 문제 이해를 통한 구현이다.문제 링크 - https://www.acmicpc.net/problem/1244 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. 에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.스위치 번호 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 스위치 상태 0 1 0 1 0 0 0 1 남학생은 스위치 번호가 ..
-
백준 1236번 성 지키기 :: 마이구미알고리즘 풀이/수학 2018. 3. 6. 00:36
이 글은 백준 알고리즘 1236번 "성 지키기" 를 풀이한다.접근 방식은 단순 문제 이해를 통한 수학적 접근이다.문제 링크 - https://www.acmicpc.net/problem/1236 영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오. 본인은 행과 열을 기준으로 무언가를 한다고 했을 때, DFS 또는 BFS 를 생각한다.이 문제의 경우에도 그렇게 생각했다.하지만 N의 크기 때문에 다소 무리가 있어, 다른 접근을 생각했다. 문제의 핵심은 모든 ..