전체 글

📌문제 출처백준 14500 테트로미노🤔일반적인 풀이 - dfs를 이용한 풀이위 문제는 dfs를 이용하여 풀 수 있다.1. T자 블럭(ㅗ/ㅏ/ㅜ/ㅓ)을 제외한 탐색기준점을 잡고 상/하/좌/우 모든 방향으로 블럭을 추가한 뒤 재귀적으로 함수를 호출한다.(이때 블럭이 중복 선택되는 경우는 제외한다.)만약 선택된 블럭이 총 4개가 되면 블럭의 점수를 더해 최대값이 나오는지 확인한다.위 사진처럼 dfs를 이용한 경우의 수를 보면, T자 모양 블럭을 제외한 모든 테트로미노 블럭을 검사할 수 있다.해당 dfs 탐색은 새로 이동한 블럭을 기준점으로 잡고 재귀 함수를 호출한다. 이 함수를 약간 변형하여 선택된 모든 블럭을 각각 기준점으로 잡아 재귀 함수를 호출하면 T자 블럭의 경우도 탐색할 수 있다.하지만, 그렇게 ..

문제 출처백준 - 30804 과일 탕후루🤔첫번째 아이디어첫번째로 떠오른 방법은 꼬치를 처음부터 끝까지 순회하며 앞뒤로 과일이 달라지는 지점을 특정하여 각 지점에서의 최대 탕후루 길이를 구하고 순회가 끝나면 그 중에서 가장 큰 값을 출력하는 방법이였다. 이때 특정 지점을 기준으로 오른쪽 방향으로만 개수를 체크하면 된다.(왼쪽을 포함한 최대 길이는 이미 측정 되었기 때문) 아래의 경우로 살펴보자   💻코드n = int(input())tanghulu = list(map(int, input().split()))result = 0# 앞 뒤 과일이 달라지는 지점을 특정하여 오른쪽 방향으로만 count를 구하고 max값 구하기for i in range(0, n): if i == 0 or tanghulu[i ..

🗒️문제백준 2579 - 계단 오르기대표적인 dp문제이다. 각 계단을 마지막으로 올랐을 때, 얻을 수 있는 최대 점수를 dp에 저장하여 바텀업 방식으로 마지막 계단에서의 최대 점수인 dp[n]을 구하자.💻풀이 1import sysn = int(input())# 계단 점수 입력n_nums = []for _ in range(n): n_nums.append(int(sys.stdin.readline().strip()))# (직전 계단을 밟은 경우 최대값 / 직전 계단을 밟지 않은 경우 최대값 저장)dp = []for i in range(n): if i == 0: dp.append((n_nums[0], n_nums[0])) elif i == 1: dp.append((n..

문제 출처📝백준 1074번 Z🤔첫번째 아이디어 - 4분할아래 그림처럼 전체 매트릭스를 4분할 해서 보면 규칙이 보인다.좌상단을 기준으로 봤을 때, 우상단/좌하단/우하단의 동일 위상에 있는 값이 각각 16x1/16x2/16x3 씩 증가한다.      위의 규칙은 좌상단의 서브 매트릭스만을 가지고 보아도 비슷하게 적용된다.여기서 매트릭스의 크기에 따라 더해지는 값이 달라진다는 것을 알 수 있고 매트릭스 한 변의 길이를 x라고 했을때, 더해지는 값은 다음과 같이 나타낼 수 있다.변화량 = x^2 / 4✏️첫번째 아이디어 - 풀이위에서 찾은 규칙으로 문제 해결을 해보자.매트릭스를 2by2로 4분할한다.구하려는 (c, r)이 나눠진 4개의 매트릭스중 어디에 위치하는지 구한다.2번에서 구한 위치에 따라 (c, ..