# 백트래킹

30개의 포스트
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개의 댓글

[BOJ 6987] 월드컵 (Java)

BOJ 6987 월드컵재미있는 문제였다. 처음 생각한 것은 전체 경기의 모든 경우를 입력으로 주어지는 것 처럼 스트링으로 만들어서 Set에 저장하고 입력이 들어올때 해당 경우가 Set에 존재하는지 확인하는 방식이였다. 하지만 메모리 초과!이 문제는 시간 제한 1초에 메

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

[프로그래머스] N-Queen (Java)

프로그래머스 N-Queen백트래킹의 기본 예제로 사용되는 N-Queen 문제다.col 배열은 i행에는 coli열에 퀸이 배치되어있음을 나타낸다.isPossible 함수행을 중심으로 퀸을 배치해나가기 때문에 현재 행의 이전 행들 중에서 같은 열에 퀸이 배치된적이 있는지

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

연구소_14502

문제 출처 : 연구소_14502 파라미터 정리 NxM 직사각형, N:row, M:col (3~8) 0 : 빈칸 (3~) 1 : 벽 2 : 바이러스 (벽을 만날때까지 상하좌우로 퍼짐) (2~10) 추가로 3개의 벽을 세움 원하는 것 = 벽 3개를 세워 바이러스 확산을 최소화하기 출력 : 안전 영역(0)의 개수 간단한 과정 input_1 N,M 입력 받기 ...

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

치킨배달_15686

문제 출처 : 치킨배달_15686 파라미터 정리 NxN 맵 크기 (2~50) 1칸은 1x1 크기, 빈 칸(0), 치킨집(2), 집(1) 中 1 (r,c) r : row, c : col 각 값은 1부터 시작함 치킨 거리 = |r1-r2| + |c1-c2| (집과 가장

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