알고리즘 풀이
-
백준 2580번 스도쿠 :: 마이구미알고리즘 풀이/그래프 2017. 9. 2. 23:47
이 글은 백준 알고리즘 문제 2580번 "스도쿠" 를 풀이한다.일반적으로 알고 있는 스도쿠 문제를 해결하는 과정을 그대로 구현하는 것이다.본인은 스도쿠 문제를 풀어본 적이 없다.그렇기에 스도쿠 관련 알고리즘을 사용한 것이 아닌, 단순히 규칙만을 가지고 접근했다.문제 풀이의 핵심은 백트래킹을 활용한다.참고 링크 - http://www.geeksforgeeks.org/backtracking-set-7-suduku/DFS, BFS - http://mygumi.tistory.com/102백준 문제 - https://www.acmicpc.net/problem/2239 스도쿠 문제를 풀기 위한 일반적인 규칙은 다음과 같다.스도쿠에 대해 굳이 자세히 다루지는 않겠다. 일반적으로 빈칸에 해당하는 가로줄 또는 세로줄 또..
-
백준 4158번 CD :: 마이구미알고리즘 풀이/수학 2017. 9. 2. 14:36
이 글은 백준 알고리즘 문제 4158번 "CD" 에 대한 문제를 풀이한다.이 문제를 풀기위해 특정 알고리즘에 대한 지식은 필요하지 않다.정답 비율이 20%대뿐만 아니라, 제출수가 많지 않은 문제이다.하지만 단순히 문제를 이해하고, 그것에 대해 논리적 사고만으로 충분히 풀 수 있는 문제이다. 상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가..
-
백준 1535번 안녕 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 26. 14:21
이 글은 백준 알고리즘 문제 1535번 "안녕" 을 풀이에 대해 작성된다.백트래킹과 동적계획법 2가지 풀이를 다뤄볼 것이다. 세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하게 되면 L[i]만큼의 체력을 잃게 되고, J[i]만큼의 기쁨을 얻게 된다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이 되거나, 음수가 되면, 죽게되서 아무런 기쁨을 못 느낀 것..
-
백준 14653번 너의 이름은 :: 마이구미알고리즘 풀이/수학 2017. 8. 22. 00:28
이 글은 백준 알고리즘 문제 14653번 "너의 이름은" 을 풀이한다.2017 선린고에서 열린 천하제일 코딩대회 본선 문제에 속하면서, 가장 정답률이 낮은 문제가 된다. OAKAK TALK에는 신기한 기능이 있다. 바로 메세지 옆에 아직 안 읽은 사람의 수를 표시해주는 기능이다. 하지만 이 기능은 읽지 않은 사람의 수만 표시해줄 뿐, 메세지를 읽지 않은 사람이 누구인지는 표시해주지 않는다. 따라서 이 기능으로 메세지를 몇 명이 읽었는지는 알 수 있지만, 누가 읽었는지는 알 수 없다. 하지만 특정한 조건을 만족한다면, 우리는 메세지를 읽지 않은 사람을 유추해낼 수 있다.그 조건은 다음과 같다. N명이 있는 OAKAK TALK방이 있다. 그리고 그 방에는 K개의 메세지가 있다. 각각의 메세지는 해당 메세지의..
-
백준 9663번 N-Queen :: 마이구미알고리즘 풀이/그래프 2017. 8. 17. 19:24
이번 글은 백준 알고리즘 문제 9663번 "N-Queen" 을 다뤄본다.백트래킹하면 바로 이 문제라고 알려져있을 정도로 유명하다고 한다.그렇다. 백트래킹을 통해 문제를 풀이해보자.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 체스의 룰을 알아야겠지만, 크게 문제가 되지 않는다.퀸은 배치된 칸을 기준으로 오와 열, 그리고 대각선 이동이 가능한 가장 가치있는 기물이다.퀸을 배치할 수 있는 경우를 보면 확실히 이해를 할 ..
-
백준 1890번 점프 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 15. 17:41
이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.그리하여 동적계획법으로 문제를 접근했다. N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개..
-
백준 2026번 소풍 :: 마이구미알고리즘 풀이/그래프 2017. 8. 15. 00:24
이번 글은 백준 알고리즘 문제 2026번 "소풍" 을 다뤄본다.종만북이라 불리는 책에서도 나오는 문제이긴 하나, 응용된 문제이다.문제 풀이는 DFS를 통한 백트래킹을 이용한다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 원장선생님께서는 K(1≤K≤62)명에게 소풍을 보내려 한다. 원장선생님께서는 1부터 N까지 번호가 붙은 N(K≤N≤900)명의 학생들 중에서 K명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 ..
-
백준 1062번 가르침 :: 마이구미알고리즘 풀이/그래프 2017. 8. 13. 15:50
이번 글은 백준 알고리즘 문제 1062번 "가르침" 을 다뤄본다. 백트래킹을 활용하는 문제로써, 20% 대의 정답 비율을 가졌다. 이전에 다룬 6603번 로또와 유사한 문제지만 문제를 잘 이해하지 않는다면, 시간 초과를 경험하게 된다. 백트래킹 관련은 6603번 로또 문제 풀이를 통해 참고하길 바란다. 참고 링크 DFS, BFS - http://mygumi.tistory.com/102 Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 2019.06.11 재채점 결과 메모리 초과 발생으로 코드 추가 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민..