16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 예제가 굉장히 많아 백준에 들어가서 보시는 것을 추천합니다! 굉장히 재미있는 문제인데, 데이터의 수가 8로 굉장히 적다. 완전 탐색을 먼저 고려해 보고 문제에서 시키는 조건대로 알고리즘을 생각해 보자. 문제를 풀다가 알게 된 건데 1번 계란으로 3번을 깬 후 3번 계란으로 1번을 다시 깰 수 있다. 헷갈릴 것 같아서 이 조건은 먼저 기억해 두자. 문제의 조건을 따라서 계란을 깨다 보면 백트래킹 형태로 상태 공간 트리를 만들면서 구현하게 될 것 같다...

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 예제 YYYYY SYSYS YYYYY YSYYS YYYYY ans : 2 처음에는 일반적인 백트래킹으로 접근했다. 어차피 데이터의 크기가 25로 매우 작고 시간은 2초로 여유롭니 모든 점을 시작점으로 두고 O(25) 재귀식을 상하좌우 중 방문할 수 있다면 방문하는 식으로 짜서 백트래킹으로 구현하였다. 이 방법에서 두 가지 문제점을 발견했는데, 사진으로 보는 게 나을 것 같다. 애초에 백트래킹은 재귀식으로 해야한다는 고정관념에 잘못 접근한 것 같다. 차라리 데이터가 ..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 예 7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0 ans : 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 ..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 예제 1 3 1 4 4 2 ans : 2 4 예제 2 4 2 9 7 9 1 ans : 1 7 1 9 7 1 7 9 9 1 9 7 9 9 예제 3 4 4 1 1 1 1 ans : 1 1 1 1 백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!! [알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제 백트래킹을 공부하기 전에 BFS와 재귀를 꼭 꼭 먼저 공부하는 ..

15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 예제 1 3 1 4 5 2 ans : 2 4 5 예제 2 4 2 9 8 7 1 ans : 1 7 1 8 1 9 7 8 7 9 8 9 수열을 사전순으로 출력하되 중복을 제거해야 한다. 참고로 1 7과 7 1은 같은 수열로 본다. 일반적인 백트래킹에서 중복을 제거해 주면 풀릴 것 같다. 백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!! [알고리즘] 백트래..

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 예제 5 0 -7 -3 -2 5 8 ans : 1 백트래킹에 익숙하지 않은 분들은 [알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제 백트래킹을 공부하기 전에 BFS와 재귀를 꼭 꼭 먼저 공부하는 것을 추천합니다. 구현의 상당 부분이 재귀로 이루어지고 BFS와 비슷한 이론의 느낌이 나기 때문입니다. [알고리즘] BFS와 DFS BFS는 큐 jun-n.tistory.com 이 글을 꼭 먼저 읽어보시기 바랍니다. N개의 정수의..