https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 처음에는 정말 단순하게 이중 for문을 사용해서 생성자가 있는지 없는지 체크하는 방식으로 아래와 같이 코드를 작성했다. for i in range(1, 10001): flag = True for j in range(1, i): num = j for k in str(j): num += int(k) if (num == i): flag = False b..
알고리즘💻/Bruteforce&Backtracking
https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, www.acmicpc.net DFS 재귀를 이용해서 구현을 했는데 시간초과가 났다. 아예 처음부터 순열을 구해서 부르트포스로 풀면 되는 문제였다. 처음에 접근할 때는 넣을 때부터 덧셈의 결과를 맞춰보려고 생각하다가 막혔는데.. 너무 어렵게 생각했던 것 같다. 각 문자마다 다른 숫자여야 하므로 전체 문자의 개수를 구해 0~9까지 그 개수에 맞게 순열을 뽑으면 된다. ..
https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 백트래킹 문제가 항상 어렵다... 재귀 싫어.... 일단 재귀를 사용할 때는 먼저 탈출조건을 적은 후에 차근차근 생각하면 될 것 같다. 1. 먼저 조건을 체크하고, 조건에 맞으면 ans에 추가한다. 2. ans의 길이가 K가 되면 끝낸다. 3. dfs에서 탈출했을 때 pop해야한다. import sys input = sys.stdin.readline K, N, F = map(int, input().sp..
import sys input = sys.stdin.readline arr = [] for _ in range(9): arr.append(list(map(int, input().rstrip()))) row = [[0]*10 for _ in range(10)] col = [[0]*10 for _ in range(10)] box = [[0]*10 for _ in range(10)] for i in range(9): for j in range(9): n = arr[i][j] row[i][n] = 1 col[j][n] = 1 box[i//3+j//3*3][n] = 1 def solve(cnt): if (cnt==81): for i in range(9): for j in range(9): print(arr[i][..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이전에 풀었던 문제인데, 백트레킹 문제를 너무 오랜만에 풀어서 감이 잘 오지 않았다. 이제는 주먹구구식으로 풀기보다 유형별로 정리해서 공부를 제대로 해야겠다.. 재귀를 이용해서 풀 수 있었다. import sys sys.setrecursionlimit(10**8) input = sys.stdin.readline N, S = map(int, input().spli..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 두 팀으로 나누는 걸 어떻게 구현해야 할 지 감이 잘 오지 않았다. 1부터 N명의 선수가 있을 때, 그 선수가 a팀에 들어가는 경우와 b팀에 들어가는 경우 두 가지 이므로,, 그걸 이용해서 백트래킹으로 풀 수 있을 것이라 생각했다. 그런데 파이썬은 시간초과가 나왔고, pypy는 15프로 정도에서 틀렸다고 계속 떠서.. 일단 파이썬 조합 라이브러리를 이용해서 풀었다. 처음에는 심지어 N은 짝수이고 N/2명으로 나눈다는 ..
https://www.acmicpc.net/problem/2993 2993번: 세 부분 첫째 줄에 원섭이가 고른 단어가 주어진다. 고른 단어는 알파벳 소문자로 이루어져 있고, 길이는 3보다 크거나 같고, 50보다 작거나 같다. www.acmicpc.net 문자열의 길이가 최대 50이기 때문에 가능한 모든 경우를 살펴보는 브루트 포스를 이용하여 풀었다. 세 부분으로 나누기 위해서는 두 포인트가 필요하므로 for 문을 이용해 가능한 모든 두 포인트를 구하였고, 각각의 포인트 별로 세 부분으로 나누어 거꾸로 이어붙였다. 그리고 동시에 사전순으로 가장 빠른 문자열을 ans에 갱신하였다. 파이썬에서 문자열을 거꾸로 정렬하는 방법을 잘 기억해놓아야 할 것 같다. import sys word = sys.stdin.r..
www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제풀이: 모든 경우를 탐색해야 하므로 DFS를 이용하여 풀 수 있다. 연산자를 주어진 배열의 형태로 접근해 보려고 하다가.. 어차피 위치는 정해져 있으니까 개수만 가져와서 함수를 만들었다. DFS 구현 부분에서 elif라고 적었다가 오류가 났었다.. 간단하게 풀 수 있는 문제인데 너무 어렵게 생각했던 것 같다. import sys input = sys.s..
www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 아이디어: 3
www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 아이디어: 열: row = [[False]*10 for _ in range(9)] 행: col = [[False]*10 for _ in range(9)] 3*3: square = [[False]*10 for _ in range(9)] -> 1~9까지 숫자가 있으면 해당 인덱스 True 주어진 스도쿠 행렬을 돌면서 0인 경우 조건을 검사하고 조건에 부합하면 일단 넣기. 어려웠던 부분: 이차 배열 선언을 [[Fal..
