백트래킹

[C++] 백준 15684번 사다리 조작

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹 문제. 삼성 SW 기출문제에 있어서 풀어봤는데, 구현 문제가 아니라 시뮬레이션 문제였다. (사실 거의 구현에 가깝다.) 시간 초과를 줄일 수 있는 방법이 떠오르지 않아서 게시판을 계속 봤는데 원하는 게시물이 없어서 많이 헤맸다. 그러다 한 게시물을 찾아서 탐색시, 중복을 제거하라는 것을 보고 맞출 수 있었다. 백트래킹은 중복을 줄여야 맞출 수 있다는 것을 다시 한 번 배운 문제다. 사실 아직도 왜 맞은지는 잘 모르겠다. 시간 복잡도를 계산했을때, 탐색하..

[C++] 백준 10819번 차이를 최대로

백트래킹 문제. N의 크기가 3부터 8이다. 따라서 최대 경우의 수가 8! 이므로 40,320번 안에 모든 탐색을 마칠 수 있다. 처음에 부등호를 잘못 표기해서 틀렸습니다. 를 받았다. 백트래킹인 것을 알고서 접근하면 어려운 문제는 아니다. 문제풀이 문제 그대로 구현해주면 된다. 순차적으로 가능한 모든 배열의 경우의 수를 만들어서 그 중 최대값을 골라서 갱신하면 된다. 어려운 부분은 없으므로 바로 코드로 설명하겠다. vector를 사용하기 위한 vector STL, max() 메서드 사용을 위한 algorithm, 절대값 abs() 메서드 사용을 위한 math.h를 사용했다. numCnt : 배열에서의 숫자의 개수 arr 배열 : 처음에 입력받는 숫자들을 저장할 배열 visit 배열 : 백트래킹 메서드를..

[C++] 백준 2580번 스도쿠

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제. 골드 4문제였는데 생각보다 너무 쉽게 풀렸다. 백트래킹 알고리즘을 사용해서 그런건가? 백준의 티어는 정말 알 수가 없다. 어떤 문제는 실버문제여도 오래 붙들고 있어도 안풀리는데, 이런 문제는 금방금방 쉽게 풀린다. 근데 또 정답률은 낮다...흠... 나도 사실 정사각형 3x3 고려를 하지 못해서 틀렸었다. 아마 나도 운이 좋아서 시간초과에 안걸려서 맞춘 것일 수도 있을 것 같다. 문제풀이 스도쿠게임을 완성시키돼, 백트래킹 알고리즘을 사용해서 구현..

[C++] 백준 15686번 치킨 배달

구현 및 브루트 포스(완전 탐색) 문제. 처음에 잘못된 백트래킹과 dfs로 접근해서 시간초과를 많이 냈다. 백준 게시판에서 도움을 얻고, 겨우 풀었다. 처음 이 문제를 봤을 때 백트래킹으로 폐업시킬 치킨집을 정하고 그래프 탐색으로 (처음에는 BFS로 하려 했으나 코드로는 DFS로 했다.) 최단거리에 있는 치킨집의 거리를 다 구해서 더하고 어떤 치킨집들을 폐업시킬 때 최소 거리가 나오는지 구하려 했다. 이 방법은 시간초과가 났고, 게시판을 참고한 결과 다음과 같은 도움을 얻었다. 폐업시킬 치킨집을 고르는 것이 아닌, 그냥 치킨집들 중 어떤 치킨집들을 open할 지 결정하면 된다. 각 집들의 거리와 치킨집들의 거리를 저장해두고 쓰면, 굳이 도시들을 다시 살펴보지 않아도 된다. 이 두개가 이 문제의 keypo..

[C++] 백준 9095번 1, 2, 3 더하기

처음 이 문제를 봤을 때 n이 작아서 백트래킹으로 문제를 풀려고 시도했다. 시간제한이 1초이므로 1억번의 연산이 가능한데 이 문제는 n이 아무리 커도 1억번을 넘지 않을거라 생각했다. 문제풀이 테스트 케이스를 입력받고 정수 n을 입력받으며 backTracking 메서드를 구현했다. 그리고 매 케이스마다 1, 2, 3 합의 개수를 나타내는 output 변수도 만들었다. 메인 함수에서는 간단하다. 매 케이스마다 결과값 output 변수를 0으로 초기화하고 backTracking 메서드를 1, 2, 3부터 시작한다. 이렇게 풀면 쉽게 맞출 수 있다. 그런데 이 문제는 백트래킹이 아닌 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법은 큰 문제를 작은 문제로 쪼개어서 푸는..

[C++] 백준 15649번 N과 M (1)

백트래킹의 기본적인 문제. 백트래킹 알고리즘을 알고있다면 쉽게 접근할 수 있는 문제이다. 백트래킹이란? 기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다. 이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다. 다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데 이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다. 출처 : https://www.acmicpc.net/board/view/15738 - simm4256님 댓글 참고 쉽게 말해서 내가 길을 가다가 이 길이 아닌거 같으면 돌아가서 다른 길로 가는 것을 뜻한다. 물론 경우의 수가 상당히 많으로 시..