[백준] 2579 : 계단 오르기 (Python)

출처 : https://www.acmicpc.net/problem/2579  아이디어해당 문제의 제한 시간을 통해, 최대 O(n) 정도의 알고리즘이 필요하다는 사실을 알 수 있다. 이는 이분 탐색, 그리디를 떠올릴 수 있지만, 다음과 같은 이유로 적용할 수 없다.이분 탐색입력 자료의 순서가 일정한가? Yes랜덤한 값을 선택해도 되는가? No : 마지막 계단을 무조건 밟아야 한다는 규칙이 존재.그러므로, 불가능그리디입력 자료의 순서가 일정한가? Yes지역적으로 최댓값을 선택해나간다면, 전역 정답에 근사해지는가? No+1 계단 이동시 지역적으로 최댓값일 수는 있어도, 전역 정답은 +2 계단에서 이동하는 경우가 존재하기 때문.그러므로 불가능결국, 두 가지 알고리즘을 제외한 나머지 브루트포스를 셀수있는 알고리즘..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 2. 6.

[백준] 12869 : 뮤탈리스크 (Python)

출처 : https://www.acmicpc.net/problem/12869  아이디어'한 번에 3개의 scv를 공격할 수 있다.'해당 요구사항을 바탕으로, '어떤 scv에 제일 높은 공격을 진행할 것인가'에 대한 인사이트가 이번 문제의 핵심이다. scv수가 3개인 상황을 예시로 경우의 수가 어떻게 나뉘는지 살펴보자.먼저, 3개의 scv를 공격하는 방법은 순열이라는 것을 알 수 있다. 즉, 6가지 경우의 수가 존재한다는 것이고, 이는 그래프 상에서 분기되는 간선(자식 서브트리)에 해당된다. 이러한 그래프와 scv 공격과의 관계를 바탕으로 다음과 같은 해석을 진행할 수 있다.큰 문제(초기 scv의 공격 최소 횟수)는 작은 문제(서브트리의 scv의 공격 최소 횟수)로 분할 가능하다.작은 문제의 답을 큰 문제..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 2. 3.

[백준] 13904 : 과제 (Python)

출처 : https://www.acmicpc.net/problem/13904  아이디어최대값을 얻기 위해서는 높은 점수의 과제를 최대한 많이 해야 한다는 생각을 가질 수 있다. 다시 말해, 높은 점수에 우선순위를 부여하여, 과제 일정 관리를 진행한다는 의미이다.즉, 우선순위 큐로 접근 가능한 문제이며, 이를 바탕으로 어떻게 과제 일정 관리 스케줄을 만들어야하는지 생각해보자. 며칠부터 며칠까지 스케줄을 관리할 것인가'중간고사 대비를 위한 1달 스케줄'중간고사 당일 ~ 당일+30일로 스케줄의 일정을 쉽게 알 수 있다. 즉, 현재 문제로 적용하면, 과제 마감일 ~ 마감일로부터 가장 많이 남은 과제가 될 것이다.가장 d값이 큰 (6,5)가 있다고 가정한다면, 마감일 ~ 마감일+6일로 스케줄 일정을 짜면 된다. ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 2. 1.

[백준] 1072 : 게임 (Python)

출처 : https://www.acmicpc.net/problem/1072  아이디어먼저, 해당 문제의 요구사항들을 자세히 파악해야할 필요가 있다. 컴퓨터의 연산 과정을 이해할 필요가 있기 때문이다. 생각해봐야 할 요구사항들은 다음과 같다.소수점은 버린다.앞으로의 모든 게임은 지지 않는다.승률(Z)가 변하지 않을 경우, -1을 출력한다.소수점은 버린다.승률의 공식은 (Y / X) * 100이다. X의 입력값은 최대 10억이기 때문에, 분수는 소수가 나올 수 있으므로 소수 연산을 하게 된다. 즉, 부동 소수점 오차를 일으킬 수 있으므로, 분수를 정수로 변환하여 컴퓨터가 정수 연산을 하게끔 유도해야 한다. 이를 통해, 다음과 같은 식으로 변환할 수 있다.승률 변환 공식 = (Y * 100) / X 앞으로의 ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 30.

[백준] 11726 : 2 x n 타일링 (Python)

출처 : https://www.acmicpc.net/problem/11726  아이디어해당 문제는 DP의 대표적인 유형이다. 그렇다면, 연산 과정(경우의 수)을 통해, 왜 DP로 접근해야 하는지 살펴보자. n이 증가할 때 마다, 어떤 규칙이 있는지를 파악하는 것이 핵심 인사이트이다.먼저, n이 1과 2일때는 손쉽게 경우의 수가 고정되는 것을 알 수 있다. n이 3일때 또한 쉽게 발견할 수 있으나, 다음과 같은 생각을 해봐야 한다.n이 2일 때와 1일 때에서 타일링을 진행하면, n=3일 때의 타일을 만들 수 있지 않을까?이를 통해, n이 1,2일 때의 각 경우를 통해 n=3 경우의 수를 구하게 되면, 점화식 가설을 세울 수 있게 된다. 해당 점화식이 과연 올바른지 확인하기 위해, 우리는 n=4일 때, 가설..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 29.

[백준] 16294 : Bee Problem (Python)

출처 : https://www.acmicpc.net/problem/16294  아이디어'특정 셀에 꿀을 흘리면, 인접한 빈칸들에 퍼져나간다.'해당 요구사항을 통해, 그래프 탐색 유형으로 해석 가능하며 DFS/BFS 모두 사용 가능하다. 주어지는 2차원 행렬은 공백이 포함되있기 때문에 다음의 사진을 바탕으로, 행렬의 범위와 탐색 방향을 계산할 수 있다. 한 번의 탐색은 빈칸들의 덩어리를 찾게 되므로, 한 덩어리(그룹)의 빈칸 개수를 찾아내고 이 수를 이용하여, 벌의 최소 작업량을 구할 수 있다. 정답 코드더보기# https://www.acmicpc.net/problem/16294# Bee Problem# 그래프탐색,BFS,DFSinput=__import__('sys').stdin.readlinedeque=..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 27.