아임'준

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 다이나믹 프로그래밍 풀이: 계단에 각각의 점수가 적혀져 있으며 시작점(시작점은 계단이 아님)부터 계단을 올라 마지막 계단까지 올랐을 때 점수가 가장 높게 계단을 오르는 법을 구하는 문제이다. 계단은 한번에 한 계단씩 혹은 두 계단씩 오를 수 있으며 연속된 3개의 계단을 밟을 수는 없다. 이런 류의 문제는 해당 ..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 다이나믹 프로그래밍 풀이: 삼각형 위에서부터 내려오면서 정수를 더해갔을 때 가장 큰 값을 구하는 문제이다. 단 내려올 때 값은 본인과 맞닿아있는 왼쪽 대각선 아래와 오른쪽 대각선 아래로만 내려갈 수 있다. 끝까지 내려왔을 때 가장 큰 값을 구하기 위해 삼각형을 새로 만들 것이다. 삼각형과 똑같은 모양이지만 새로 바뀐 삼각형에는 기존 삼각형의 해당 위치에 있는 값을 더했을..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 다이나믹 프로그래밍 풀이: 문제에서 원하는 조건은 다음과 같다 1) 이웃한 집끼리 색깔이 같으면 안된다 2) 각 집마다, 색깔마다 칠하는 비용이 다르다 해당 문제를 처음 봤을 때 이런 문제 유형을 처음 접하는거라 당황했었는데 이 이후로 아주 자주 볼 문제이기도 하다. 첫번째 조..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 수학, 다이나믹 프로그래밍 풀이: 나선 모양으로 놓여 있는 삼각형의 특정 몇번째 삼각형의 변의 길이가 몇인지 구하는 문제이다. 문제에서 첫 10개의 삼각형의 변의 길이는 [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]라고 알려주었다. 이제 수열의 규칙성을 찾기 위해 다음 삼각형의 변의 길이를 구하..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 단계 : 동적 계획법 1단계 알고리즘 분류 : 다이나믹 프로그래밍 풀이: 문제에서 주어진 타일은 길이가 2인 '00'타일과 길이가 1인 '1' 타일이다. 규칙을 찾기 위해 몇개만 구해보겠다. 길이 1 : "1" 길이 2 : "11", "00" 길이 3 : "111", "100", "001" 길이 4 : "0000", "0011", "1001 , ..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 다이나믹 프로그래밍, 재귀 풀이: w라는 재귀 함수의 실행에 있어서 여러번의 테스트를 거칠 때 더 빠르게 돌아가도록 하는 문제이다. 어차피 구해야 하는 값을 한번은 구해야하기에 해당 값을 저장할 dict라는 딕셔너리를 하나 전역변수로 만들어준다. 그리고 문제에 나와있는 w 함수를 그대로 구현하는 대신 ..

백준 / BOJ / Python / 파이썬 문제 링크 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 단계 : 동적 계획법 1 알고리즘 분류 : 다이나믹 프로그래밍 풀이: 풀이 방법이 두개가 있다. 1. 첫 번째 방법 문제에서 주어진 코드인 fibonacci(N)을 호출했을 때 출력되는 0과 1의 개수를 구하는 문제이다. 0이 출력되는 경우는 N이 0일 때만 출력되며 1이 출력되는 경우는 N이 1일 때만 출력된다. 피보나치 수열 구하는 방법은 피보나치 수열에서 자기 이전 두 개 수의 합을 구하는 것이다. n번째 피보나치 수를 구하고 싶다..

백준 / BOJ / Python / 파이썬 문제 링크 : 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 단계 : 백트래킹 알고리즘 분류 : 브루트포스 알고리즘, 백트래킹 풀이: 두 팀 간의 전력 차이를 최소화해야 한다. 사람 수, 사람들의 능력치를 입력받는다. team이라는 리스트를 만들 것이다. 이 리스트에 들어있는 사람들은 start팀으로 간주할 것이고 이 리스트에 들어있지 않은 사람들은 link 팀으로 간주할 것이다. solve의 인자를 순서대로 설명하면 n..