전체 글

[Baekjoon] 1003번 : 피보나치 함수

실버 3 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 다이나믹 프로그래밍의 기초 보텀업(bottom-up) 방식으로 0번째부터 차근차근 dp 리스트를 채워나간다. 0과 1이 호출되는 횟수도 피보나치 수열과 마찬가지로 점화식을 세울 수 있다. i의 0이 호출되는 횟수 = (i-1)의 0이 호출되는 횟수 + (i-2)의 0이 호출되는 횟수 i의 1이 호출되는 횟수 = (i-1)의 1이 호출되는 횟수 + (i-2)의 1이 호출되는 횟수 코드 t = int(input()) for _ in range(t): dp = [0] * 41 dp[0], dp[1] = (1, 0), (0, 1) n = int(..

[Baekjoon] 14889번 - 스타트와 링크

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 두 팀으로 인원을 나누고 팀 능력치의 차이가 최소가 되도록 하는 프로그램을 구현해라 문제 풀이 1) 조합으로 a팀을 고를 수 있는 경우의 수를 모두 구한다. 2) 모든 사원 집합에서 a팀을 제외하여 (차집합) b팀을 구한다. 3) a팀의 합과 b팀의 합을 구하고 차를 계산한다. 4) 최소값을 구해 출력한다. 코드 from itertools import combinations def solution(): global min_value for team_a in combinations(me..

[Baekjoon] 2580번 : 스도쿠

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Gold 4. 스도쿠의 규칙대로 빈 칸을 채우는 문제! 스도쿠는 9x9 칸에 가로, 세로, 3x3칸 내에 1-9까지의 숫자가 중복없이 들어가야 한다. 문제 풀이 백트래킹 알고리즘 이용 1) 빈칸에 대해서 1-9까지 값을 넣어보고 가능한지 확인한다. 2) 가능하면 값을 넣고 다음 노드로 이동한다. 코드 graph, blank_list = [], [] for i in range(9): graph.append(list(map(int, input().split())))..

[Baekjoon] 9663번 : N-Queen

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 퀸은 자신의 위치를 기준으로 상, 하, 좌, 우, 대각선 방향으로 보드 끝까지 공격이 가능하다. 공격이 닿는 경우를 확인하여 닿으면 False를 반환하는 함수를 만든다. 1) 열이나 행이 겹치는 경우 : 같은 열에 퀸이 있는지 확인 2) 대각선에 걸친 경우 : 대각선 위치에 있다는 것은 두 퀸의 x좌표의 차와 y좌표의 차가 같은 경우 보드의 한칸씩 반복문으로 확인하며 공격받지 않는 위치라면 퀸을 놓고, 아니면 패스한다. 하나씩 퀸이 놓여지고 퀸의 개수가 n 개가 되면..