#연산 재활용 -> dpX = int(input())dp = [0] * (X+1) # 기본적인 dp 세팅for i in range(2,X+1): dp[i] = dp[i-1] +1 #그리디로 푼다면 짝수, 홀수로 바로 나눌 수 있지만 #이 문제의 경우 경우의 수를 고려하는 최솟값임 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1) # if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1) # print(dp[X])
이 문제 풀면서 궁금했던 점: 공유기 1개가 몇개까지 커버치는지가 궁금했는데 문제 방향이랑은 크게 상관이 없음 이분 탐색으로 풀어야겠다는 생각은 못하고 각 공유기의 지점을 포인터로 지정해야 하나 생각함 -> 근데 이래 버리면 포인터가 공유기 개수만큼 있어야 하니까 안됨 -> 완전 탐색으로 풀어야 하나 생각함 -> 시간이...?????????되나 ➡ N = 200,000, C = 200,000일 때,➡ 가능한 공유기 간 거리(gap)의 최대값은 1,000,000,000 (10억)➡ 완전 탐색(O(N * max_gap))으로 해결하려면 최악의 경우 200,000 * 10^9 = 2 * 10^13결론: 최대, 최소 거리 문제의 경우 시간복잡도를 계산해보고 완전 탐색 안될거 같으면 이진탐색으로 가자...for ..
코딩 테스트에서 "완전 탐색(Brute Force)"이 불가능한 경우를 어떻게 알까?➡ 시간 복잡도를 기반으로 연산 횟수를 계산하면 알 수 있습니다.💡 핵심:컴퓨터는 1초에 약 10^8 ~ 10^9(1억 ~ 10억)번 연산을 수행 가능따라서 "최악의 경우 연산 횟수" 를 계산하여 1억을 넘으면 비효율적인 알고리즘이라고 판단할 수 있음완전 탐색(Brute Force) 이 가능한지 시간 복잡도를 계산하여 결정해야 함- 삼성 제외 일반적인(?) 코테 문제들의 시간 제한은 1초이기 때문에 1억이내(10^8)의 연산으로 끝내야 함- 1억 이상의 완전 탐색을 요구하지 않음 🚀 1️⃣ 연산 횟수에 따른 알고리즘 선택 기준 연산 횟수시간 복잡도알고리즘N ≤ 10O(N!) (팩토리얼)완전 탐색 가능 (순열, 백트래킹..
큰 문제를 작은 문제로 나누어 풀고, 중복 계산을 줄여 효율적으로 해결하는 알고리즘 기법🚀 동적 계획법(DP)이란?✅ 큰 문제를 작은 하위 문제로 나누어 푸는 방식✅ 이전에 계산한 결과를 저장하여 중복 계산을 줄임 → 메모이제이션(Memoization) 사용 / 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 ✅ "최적 부분 구조(Optimal Substructure)"와 "중복되는 부분 문제(Overlapping Subproblems)"가 존재할 때 사용 가능 🚀 DP의 두 가지 접근 방법1️⃣ Top-Down (재귀 + 메모이제이션)큰 문제를 작은 문제로 나누어 푸는 방식재귀 + 딕셔너리(memo) 또는 리스트(dp[])를 사용하여 중복 계산을 줄임def fib(n): if n..
✅ 1️⃣ 기본적인 방향 설정우리가 보통 사용하는 2D 좌표계에서의 방향 이동에 대해 알아보자2차원 리스트(행렬)에서 이동할 때는 (행, 열)로 움직이게 된다방향이동 (행 변화, 열 변화)L (왼쪽)(0, -1)R (오른쪽)(0, +1)U (위쪽)(-1, 0)D (아래쪽)(+1, 0)👉 즉, 이동하면 행(row)과 열(col)이 변화함 # 방향 정의 (L, R, U, D 순서)dx = [0, 0, -1, 1] # 행 변화량dy = [-1, 1, 0, 0] # 열 변화량move_types = ['L', 'R', 'U', 'D']# 초기 위치 (예: (x, y) = (2, 2)에서 시작)x, y = 2, 2# 이동할 명령어 리스트commands = ['L', 'D', 'D', 'R', 'U'] # ..
https://www.acmicpc.net/problem/1546 def solution(): N=int(input()) # 시험 본 과목의 개수 scores = list(map(int,input().split())) # 시험 점수 M = max(scores) # 성적 중 최대값 new_score = [(score / M) * 100 for score in scores] new_average = sum(new_score)/N print(new_average)