백트래킹 (14) 썸네일형 리스트형 [Python] 15650번 N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/06/25 옛날에 풀었던 문제를 오늘(22/12/01) 백트래킹으로 다시 풀어보았다. 이전에는 파이썬의 itertools묘듈의 combinations를 사용해서 문제를 해결했지만, 백트래킹을 연습하는 문제로, 백트래킹으로 풀어보기로 했다. 문제 접근 방식: 첫 번째 접근 방법은 N과 M (1)의 코드를 변형한 코드이다. 2022.12.01 - [백준 문제 풀이] - [Python] 1564.. [Python] 15649번 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/11/30 백트래킹의 기초적인 문제로, 단계별로 풀어보기에서 풀어볼 수 있다. 문제 접근 방식: 백트래킹은 주로 재귀+가지치기로 접근이 되어진다. 말 그대로 Backtrack이기 때문에, 쭉 갔다가 다시 돌아오는 작업이 필요하다. 때문에 깊이 있게 들어가는 dfs탐색으로 대부분의 문제가 풀린다. dfs는 스택을 이용할 수도 있고, 재귀를 이용할 수도 있지만, 일반적으로 재귀를 이용한 구현이.. [Python] 7490번 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 22/11/23 파이썬에 특화된 문제로, 만약 다른 언어로 이 문제를 풀었다면 힘들게 풀었을 것이다. 문제 접근 방식: 기껏 해봤자 입력으로 받는 자연수의 범위가 $9$까지 이기 때문에 그냥 깡으로 구현하면 될 것이라고 생각했다. $N$개의 자연수가 있다면 그 사이에 공백이든, 더하기 기호든, 빼기 기호든지 간에 $N-1$개의 기호가 들어가므로 가능한 모든 조합들을 itertools모듈의 product함수를 사용하여 구현하였다. 만약 product함.. [Python] 2661번 좋은수열 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 22/10/06 전형적인 백트래킹 문제로, 좋은 수열이 되는 조건을 잘 따라가며 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 문제를 해설하기에 앞서, 먼저 N = 8일 때의 찾는 과정을 도식화한 그림을 보자. 우리는 좋은 수열 중 가장 작은 수열을 찾는 것이 목적이다. 이 그림은 이를 찾기 위해 3가지 조건을 지키면서 탐색을 진행하는 과정을 나타낸 것으로, 3가지 조건은 다음과 같다. 1. 가장 작은 수열.. [Python] 21317번 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 22/10/03 개인적으로 굉장히 난이도에 비해 굉장히 어렵게 느껴졌던 문제로, 다른 방법으로 풀었다면 조금 쉽게 해결하지 않았을까 하는 아쉬움이 남는 문제이기도 하다. 문제 접근 방식: 백트래킹으로도 접근할 수 있는 문제이긴 하지만, 나의 경우는 DP로 이 문제를 접근했었다. 굉장히 많이 틀렸기 때문에 틀린 과정을 상세하게 설명하고자 한다. 맨 처음 풀이는 그냥 단순하게 DP[N] = N번째까지 도착했을 때, 산삼을 얻기 위해 필요한 영재의 에너지 최솟값이라고 정의를 했었다. 그리고 가장 큰 점프는 한 번만 할 수 있으므.. [Python] 9663번 N-Queen (추후 보강 예정) 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 22/09/01 클래스 3 문제 중에서 안 풀었던 문제가 있기에 풀어보았다. 백트래킹 문제 중에서 가장 유명하고 잘 알려진 문제인 N-Queen 문제이기에, 나는 당연히 이 문제를 솔루션을 보지 않고는 풀기 힘들 것이라고 생각되어서 이 문제를 유튜브 강의를 참고하여 해결하였다. 참고한 유튜브 강의는 아래 링크에 있다. 유튜브 강의에서 설명을 굉장히 잘 해놓았기 때문에 보고 글을 읽으면 더욱 이해가 잘 될 것이다. 파이썬으로 배.. 이전 1 2 다음
