# 백트래킹

34개의 포스트
post-thumbnail

[알고리즘] 백트래킹(되추적)

어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다 ("backtrack").DFS는 가능한 모든 경로(후보)를 탐색합니다. 즉, 불필요한 노드까지 모두

2020년 10월 12일
·
0개의 댓글
post-thumbnail

[BaekJoon] 2529 부등호

브루트포스로 푼 문제최대,최솟값만 구하면 되므로 시간 절약을 위해 앞, 뒤로 반복문을 돌림공통 : 0 ~ 9까지 숫자에 대해 문자의 갯수보다 하나 많게 순열을 구한다.MIN 값순열이므로 작은 값부터 시작된다.구한 순열 중 하나를 뽑아 부등호 앞 뒤의 값을 비교한다.조건

2020년 9월 25일
·
0개의 댓글

N-Queen (python)

백트래킹의 전형적인 문제

2020년 9월 6일
·
0개의 댓글

[ICPC-신촌] Ch.02 Backtracking

2020 ICPC-신촌 | Ch.02 백트래킹

2020년 8월 8일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 행운의 문자열

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇

2020년 7월 12일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까

2020년 7월 6일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 맞춰봐

맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때

2020년 7월 1일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - N-Queen

N-Queen 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. > N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N 1. (0,0) 부터 (

2020년 7월 1일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 스도쿠(2239)

비슷한 문제 - 스도쿠(2580)스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.위 그림은 참 잘도 스도

2020년 6월 30일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - N과 M(4)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤

2020년 6월 26일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - N과 M(3)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)한 줄에 하나씩 문

2020년 6월 26일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - N과 M(2)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1

2020년 6월 26일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - N과 M(1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)한 줄에 하나씩 문제의 조건을 만족하는

2020년 6월 26일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 스도쿠(2580)

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터

2020년 6월 25일
·
0개의 댓글
post-thumbnail

[알고리즘] 백 트래킹

백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약

2020년 6월 25일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 로또

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,

2020년 6월 24일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 단어 수학

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은

2020년 6월 23일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 숫자판 점프

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤

2020년 6월 23일
·
0개의 댓글
post-thumbnail

스타트와 링크_14889

문제 출처 : 스타트와 링크_14889 파라미터 정리 N 총 사람 수(4 ~ 20, 짝수) Row 팀(스타트) or Col 팀(링크)로 생각하기 Sij i번 사람과 j번 사람 사이에 존재하는 시너지 (1~100) Sij는 Sji와 다를 수 있음 Sii는 항상 0 (자기 자신과의 시너지를 의미하므로 0) 각 팀의 능력치는 모든 팀원의 시너지를 더한 것 원하...

2020년 5월 31일
·
0개의 댓글
post-thumbnail

요리사_4012

문제 출처 : 요리사_4012 #스타트와링크 문제랑 똑같음 파라미터 정리 T 테스트 케이스 개수 (1~50) N 음식 개수 (N은 짝수) (4~16) Sij 음식 간 시너지 (1~20000) i == j 일 경우 시너지가 없음 팀의 총 시너지 = 각 재료 사이의 시

2020년 5월 31일
·
0개의 댓글