코테35 프로그래머스 - 방문 길이 (핵심 : line 체크) 💡문제 분석 요약위 아래 왼쪽 오른쪽 명령어가 들어오면 해당 좌표로 이동한다.이동하지 못하는 위치라면, 즉 벗어났다면 해당 명령은 무시한다.이때 새로운 길에 대해서 체크한다. 갔던 길을 다시 가는 것은 count하지 않는다.💡알고리즘 설계처음엔 전형적인 DFS인줄 알았으나, 이미 주어진 명령어와 범위가 있어서 DFS까지는 안써도 되는 거로 인식했다.다만 왔던 길인지 알아야하므로 visited같은 역할을 하는 자료구조가 필요했고, 이는 set()을 사용했다.💡코드def operation(x, y, op): if op == "U": y += 1 elif op == "D": y -= 1 elif op == "R": x += 1 elif op ==.. 2024. 9. 11. 1303 전쟁 💡문제 분석 요약구역별로 병사들이 몇명 있는지 구한다. 해당 구역 내에 병사들의 power는 병사들 수의 제곱이다.white, blue 각각의 power를 구한다.💡알고리즘 설계DFS, BFS 둘 다 가능하다.상하좌우 체크와, 병사들 수 체크만 잘 하면 된다. 병사들 총 수는 DFS 실행횟수와 같다.💡코드import syssys.setrecursionlimit(10**6)# 가로, 세로 "길이"가 n, m임. 즉 행:m , 열:nn, m = map(int, input().split()) # 가로가 열 개수, 세로가 행 개수라는 것을 헷갈리면 안됨 !!!!!!!!!!!!!!!!!!!!!!!!!!war = [list(input()) for _ in range(m)] # 여기서도 range(n)이 아니.. 2024. 8. 13. 12845 모두의 마블 💡문제 분석 요약카드 합성시 합쳐진 카드의 레벨만큼 돈을 받고, 이 돈이 최대가 되는 경우를 구한다.레벨이 높은 카드는 합쳐져도 레벨이 변하지 않는다. = 즉, 계속 사용된다💡알고리즘 설계인덱스를 신경써야하는 것으로 이해해서, enumerate나 dictionary를 생각했다. 근데 enumerate는 인덱스 값을 변경할 수가 없었다.그러나 카드의 위치가 고정이 아니라는 것을 알고, 정렬 후 최대 레벨의 카드를 기준으로 합치면 된다고 생각했다.💡코드n = int(input())cards = sorted(list(map(int, input().split())))print(cards[-1]*(n-1) + sum(cards[:n-1]))"""1. 일단 정렬해서 가장 큰 레벨을 뒤로 빼줌. (최대 레벨이 .. 2024. 8. 3. 1495 기타리스트 💡문제 분석 요약마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 찾는다.볼륨은 0 이상 M 이하의 값만 가능하다.각 곡을 연주할 때, 주어진 볼륨 변화(V[i])로만 조절할 수 있다.💡알고리즘 설계2차원 배열 dp[i][j]를 정의하여, i번째 곡을 연주할 때 볼륨이 j인 상태를 기록.💡코드n, s, m = map(int, input().split())v = list(map(int, input().split()))def max_volume(n, s, m): # dp[i][j]는 i번째 곡을 연주할 때 볼륨이 j인 상태를 나타낸다. dp = [[0] * (m + 1) for _ in range(n + 1)] # 시작 볼륨 설정 : dp[0][S] = True dp[0][s] = T.. 2024. 8. 2. 12026 BOJ 거리 💡문제 분석 요약시작지점에서, 끝까지 가는데에 드는 최소비용을 계산한다.이동은 반드시 B -> O -> J 순서로만 이동할 수 있고, 해당 알파벳이 인접해있지 않으면 점프도 가능하다.점프할 때 드는 비용은 거리의 제곱만큼 든다.💡알고리즘 설계DP를 이용해서 점프를 할 때 어디 알파벳으로 점프해야 최소비용일지 계산한다.이중 for문으로 모든 원소에 대해서 비교한다.💡코드n = int(input())boj = input()# 여기서 dp[i]의 값은 해당 인덱스까지 가는데에 드는 에너지를 의미함.# 문제 조건에서 적힌 N의 최대값이 1000이라서, 첫번째에서 마지막으로 바로 점프하더라도 1000000을 넘지 않음dp = [1000000]*ndp[0] = 0for i in range(n): for .. 2024. 8. 1. 1654 랜선 자르기 💡문제 분석 요약이미 가지고 있는 랜선들은 길이가 제각각이다. 이것들을 이용해서 n개의 랜선이 더 필요하다.갖고 있는 랜선들을 n개로 만들 때, 최대길이가 되어야한다.💡알고리즘 설계지난번 풀었던 절단기 문제와 매우 유사해서 쉽게 풀 수 있었다. 이분탐색을 이용한다.💡코드k, n, = map(int, input().split()) # k : 이미 가진 랜선개수 / n : 필요한 랜선개수lans = []for i in range(k): lans.append(int(input()))left = 1right = max(lans)while left = n: left = mid + 1 else: right = mid - 1print(right)💡시간복잡도O(log N)💡.. 2024. 7. 31. 2805 나무 자르기 💡문제 분석 요약나무개수, 원하는 나무 길이, 각 나무들의 길이가 주어졌을 때 바닥에서부터 몇m가 되는 지점을 베어야 나무의 윗부분들을 잘라내어서 정확히 내가 원하는 나무의 길이만큼 베어갈 수 있는지를 구해야한다.중요한 것은 절단기가 아래서부터 시작한다는 것이다. 즉, 맨 아래를 자르는 것이 가장 많은 나무를 가져가는 경우이다.💡알고리즘 설계나무가 아닌 절단기를 대상으로 이분탐색을 진행한다.💡코드처음에 틀린 풀이이다. (아래 설명)n, m = map(int, input().split())tree = sorted(list(map(int, input().split())))# 절단기의 높이를 이분탐색으로 찾기# 절단기 높이는 짧을수록 나무를 더 많이 자르는 것임. (중요)def checkSum(mid):.. 2024. 7. 30. Programmers 입국심사 💡문제 분석 요약N명의 사람들이 심사관들에게 심사를 받는 최소 시간을 구해야한다.심사관마다 심사를 보는 시간은 제각기 다르다.이때 주의할 점은, 당장 내가 심사를 받을 수 있는 상황이더라도 잠시 기다렸다가 심사를 더 짧게 보는 사람에게 가는 것이 이득일 수 있다는 것이다. ex) 당장 가서 100분 심사받기 vs 1분 기다렸다가 20분 심사받기💡알고리즘 설계잠시 기다리는 대기시간을 고려한다는 점에서 DP로 풀 수 있다고 생각했지만, 입력 값이 10억인 것을 보고 안되는 것으로 판단했다...이분탐색을 이용해본다.💡코드def solution(n, times): # left = 최소시간 , right = 최대시간 left = 1 # 최소시간은 1분이상이라고 문제에 명시 ri.. 2024. 7. 29. 필독!!) DP (Dynamic Programming) DP처음 보면 dynamic programming이 무슨 뜻인지 감이 잘 안오는데, 쉽게 말하면 중복되는 과정은 재사용하겠다는 것이다. 큰 문제를 해결하는데 작은 문제들이 사용된다면, 이를 어디다가 저장해놓고 큰 문제를 해결하는데에 이용한다.이 맥락에서 알 수 있듯이, 작은 문제의 결과를 저장해야 하므로 메모리를 추가적으로 사용한다.그러나 생각해보자. 100이라는 문제를 푸는데 단계별로 1, 2, 3, ... , 98, 99가 필요하다고 한다면, 99까지의 결과를 어디다가 저장해두고, 99 → 100 이렇게 한단계만 푸는 게 효과적이지 않겠는가?? 그래서 메모리는 추가적으로 들지만 앞단계를 다 스킵할 수가 있으므로 시간을 많이 단축할 수 있다.Memoization위에서 설명했던, 메모리를 추가로 사용해서.. 2024. 7. 29. 이전 1 2 3 4 다음 반응형
