백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 9184번: 신나는 함수 실행 (Python)

접근 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 저장함으로써 동일한 계산 반복 수행을 제거하는 문제이다. 실질적으로 계산이 되는 범위는 각 숫자가 1에서 19일 때까지이므로 해당 범위에 대한 list를 만들어주고, 함수를 순환하는 중에 해당하는 값을 list에 저장해준다. 코드 import sys wt = [[[0] * 21 for _ in range(21)] for __ in range(21)] def w(a, b, c): global wt if a 20: return w(20, 20, 20) if wt[a][b][c]: return wt[a][b][c] if a < b < c: wt[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, ..

2021. 3. 26. 21:51
코딩/백준 (Python)

백준 1003번: 피보나치 함수 (Python)

접근 단순 재귀함수로 풀었을 때 피보나치 수를 구하기 위해 많은 시간이 걸린다고 한다. 당연하게도 그냥 피보나치 수를 구하는 재귀함수에 n = 0, n = 1일때마다 카운트하게 코드를 작성하면 시간 초과가 되게 된다. def fibonacci(n): global fibonacci_count if n == 0: fibonacci_count[0] += 1 return 0 elif n == 1: fibonacci_count[1] += 1 return 1 else: return fibonacci(n - 1) + fibonacci(n - 2) 요점은 n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이라는 것이다. 즉 n번째 피보나치 수가 0과 1을 호출하는 횟수는 n-1번째 수와 n-2번..

2021. 3. 26. 02:45
코딩/백준 (Python)

백준 14888번: 연산자 끼워넣기 (Python, PyPy3)

접근 각 숫자들 사이를 빈칸이라고 두고, 해당 칸에 들어갈 수 있는 연산자를 넣어보면서 해당 숫자들과 연산자들로 얻을 수 있는 가장 큰 수와 작은 수를 구하는 백트래킹 문제이다. 사용할 수 있는 연산자들을 모두 list에 모아두고, 해당 연산자가 사용되었는지를 저장하는 또 한개의 list를 이용하였다. 중간에 temp라는 이름의 list를 이용하여 계산이 완료된 후 되돌아갈 중간 값들을 저장해주었다. 다시 풀기(2022.9.19) 백트래킹 문제였습니다. 덧셈, 뺄셈, 곱셈, 나눗셈에 대한 함수를 만들어 배열에 저장해주고, 백트래킹 알고리즘을 이용하여 처음 숫자부터 순서대로 계산하면서 depth 가 마지막에 도달하면 최대값과 최소값을 갱신해줍니다. 매 depth 마다 사칙연산 4가지를 고려하고, 해당 사칙..

2021. 3. 26. 02:11
코딩/백준 (Python)

백준 2580번: 스도쿠 (Python)

문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 정사각형의 ..

2021. 3. 26. 01:59
코딩/백준 (Python)

백준 9663번: N-Queen (Python, PyPy3)

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 접근 체스에서 퀸은 가로, 세로, 대각선 방향으로 끝까지 이동할 수 있다. 즉, N개의 퀸을 체스판 위에 올려놓았을 때, 서로 가로, 세로, 대각선 방향으로 겹치면 안된다. 처음에는 list를 이용하여 N*N 배열의 리스트를 만들고 퀸 한개를 놓을 때마다 놓인 위치의 좌표를 이용하여 가로, 세로, 대각선 방향의 칸들을 지운 후 다음 퀸을 놓는 백트래킹 방식을 사용했는데, 수가 커질 수록 시간이 매..

2021. 3. 26. 01:43
코딩/백준 (Python)

백준 1436번: 영화감독 숌 (Python)

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..

2021. 3. 25. 23:17
반응형