본문 바로가기
728x90

dfs

[백준알고리즘] 2580번: 스도쿠 -C++ [백준알고리즘] 2580번: 스도쿠 -C++ 2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 문제 또한 대표적인 백트래킹 문제 중 하나다. 그만큼 유명하고, 비슷한 문제도 많이 있다. 그럼에도 정답 비율이 30%가 안 되는 것은 그만큼 처음 풀기에도 어려운 문제라는 것 같다. 예전에 이 문제를 Python3 (PyPy3)로 풀었다. 두 번 풀었었고, 해당 코드들을 모두 블로그에 쓴 적이 있다. [백준알고리즘] 2580번: 스도쿠 -Python (tistory.. 더보기
[백준알고리즘] 9663번: N-Queen -C++ [백준알고리즘] 9663번: N-Queen -C++ 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제로 유명한 N-Queen 문제다. 유명한 문제인만큼 정답 비율은 53%가 넘음에도 불구하고 골드 5의 난이도를 갖고 있는 문제다. 그만큼 중요한 문제라고 말하는 것 같다. N-Queen 문제는 원래 8 Queen 문제로 유명하다. 문제의 요구조건은 동일하나 \( 8 \times 8 \) 크기의 체스판에 8개의 퀸을 놓는 문제다. 이거에 대한 접근법도 다양하게 있던.. 더보기
[백준알고리즘] 15683번: 감시 -C++ [백준알고리즘] 15683번: 감시 -C++ 15683번: 감시 (acmicpc.net) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 예전에 파이썬으로 풀다가 무슨 일 때문인지 하다가 포기했던 문제다. C++로 새롭게 푸는데 생각보다 쉽게 풀려서 당황스럽다. 시간제한은 1초이지만 메모리 제한은 큰 문제다. 시간제한 때문에 고민을 좀 했다. 하지만 한 가지 조건 덕분에 완전 탐색(브루트포스) 방식으로 문제를 해결할 수 있었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제를 풀 수 있는 .. 더보기
[백준알고리즘] 1759번: 암호 만들기 -C++ [백준알고리즘] 1759번: 암호 만들기 -C++ 1759번: 암호 만들기 (acmicpc.net) 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 예전에 파이썬으로 풀었던 문제다. 하지만, 역시나 기억이 나지 않았다. ㅋㅋ.. 다 풀고 글을 쓰려고 예전 글을 보니까 역시 파이썬 코드는 간단하다. 오늘 짠 C++ 코드도 더 간단히 가능하겠지만, 요즘 복잡하면서 간단한 것보다는 길더라도 깔끔한 코드를 지향하고 있어서 뭐 만족한다. 예전에 파이썬으로 풀었던 포스팅은 아래의 링크를 통해 가면 있다. [백준알고리즘] 17.. 더보기
[백준알고리즘] 10974번: 모든 순열 -C++ [백준알고리즘] 10974번: 모든 순열 -C++ 10974번: 모든 순열 (acmicpc.net) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 가능한 순열을 오름차순으로 출력하는 문제다. 처음에는 순열을 만드는 STL 라이브러리를 사용하지 않고 문제를 풀었고, 이후 해당 기능의 라이브러리가 있을 것 같아 찾아서 적용해봤다. 두 경우 모두 통과했고, 아래에 순서대로 작성해놨다. 간단한 문제라서 길진 않다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 1. 직접 구현 직접 순열을 만들고 출력하는 함수를 만들어주었다. DFS로 동작하면서 브루트포스(완전 탐색)를 시도해서 문제를 풀었다. 길이가.. 더보기
[백준알고리즘] 2210번: 숫자판 점프 -C++ [백준알고리즘] 2210번: 숫자판 점프 -C++ 2210번: 숫자판 점프 (acmicpc.net) 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 메모이제이션을 사용할까 하다가 숫자판도 작고, 만들어낼 숫자의 길이도 6자리로 길지 않았기 때문에 계산을 해보다가 메모이제이션 없이 완전 탐색을 시도했다. 대강 계산했을 때 각 위치에서 4방향으로 이동할 수 있기 때문에 메모이제이션 없이 각 시작 위치에서 \(4^5\)개의 위치로 이동할 수 있다. 즉, \(5 \times.. 더보기
[백준알고리즘] 1039번: 교환 -C++ [백준알고리즘] 1039번: 교환 -C++ 1039번: 교환 (acmicpc.net) 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 굉장히 어려웠다. 풀고 제출을 했었는데 틀렸다고 나왔고 해당 문제가 뭔지 알았는데, 고치지 못했다. 결국 다른 분의 블로그를 참고해서 문제를 푸는 법을 알았고, 이해한 내용을 바탕으로 다른 내용으로 풀고 싶었다. 아래 블로그의 얍문님의 포스팅을 보고 BFS로 푸는 방법에 대해서 알게 됐다. [ 백준 1039 ] 교환 (C++) :: 얍문's Coding World.. (tistory.com) [ 백준 1039 ] 교환 (C++) 백준의 교환(103.. 더보기
[백준알고리즘] 1890번: 점프 -C++ [백준알고리즘] 1890번: 점프 -C++ 1890번: 점프 (acmicpc.net) 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 누가 봐도 동적 계획법으로 풀어야 할 것 같은 문제다. 그래서 가능한 모든 경우를 찾는데 재귀를 사용했고, DFS를 사용했다. 사실 이전에 Python으로 풀었던 문제였다. 물론 기억은 나질 않았지만.. 아래 링크가 이전에 풀었던 코드다. [백준알고리즘] 1890번: 점프 -Python (tistory.com) [백준알고리즘] 1890번: 점프 -Python [백준알.. 더보기
728x90

티스토리툴바