백트래킹
-
백준 1535번 안녕 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 26. 14:21
이 글은 백준 알고리즘 문제 1535번 "안녕" 을 풀이에 대해 작성된다.백트래킹과 동적계획법 2가지 풀이를 다뤄볼 것이다. 세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하게 되면 L[i]만큼의 체력을 잃게 되고, J[i]만큼의 기쁨을 얻게 된다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이 되거나, 음수가 되면, 죽게되서 아무런 기쁨을 못 느낀 것..
-
백준 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이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 체스의 룰을 알아야겠지만, 크게 문제가 되지 않는다.퀸은 배치된 칸을 기준으로 오와 열, 그리고 대각선 이동이 가능한 가장 가치있는 기물이다.퀸을 배치할 수 있는 경우를 보면 확실히 이해를 할 ..
-
백준 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 재채점 결과 메모리 초과 발생으로 코드 추가 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민..
-
백준 6603번 로또 :: 마이구미알고리즘 풀이/그래프 2017. 8. 1. 21:24
이번 글은 백준 알고리즘 문제 6603번 "로또" 를 다뤄본다.문제를 보다시피, 모든 경우의 수를 찾아야한다.DFS에서 백트래킹을 응용하여 문제를 해결할 수 있다.이 문제의 코드를 이해한다면, 재귀 함수와 친해질 수 있을 것이다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를..
-
백준 1987번 알파벳 :: 마이구미알고리즘 풀이/그래프 2017. 7. 22. 22:36
이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.문제 풀이는 DFS를 응용하여 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..