조이의 개발 성장 다이어리

문제: https://www.acmicpc.net/problem/28069해당 문제는 DP로 풀이했다.- 0번 계단부터 N번째 계단까지 도달하는 종료 조건이 있음- DP[N]을 N번째 계단까지 도달하기 위해 행동한 횟수라고 가정하여 점화식을 세울 수 있음 ❌ 틀린 풀이n, k = map(int, input().split())INF = int(1e9)dp = [INF] * (n+1) # DP[i]: i번째 계단까지 도달하기 위한 행동 횟수dp[0] = 0 # 현재 0번째 계단에 있고, 행동횟수는 0이므로 dp[0] = 0으로 초기화for i in range(n): if i + 1 소수점을 제거한 정수와 같다. # int(i+i/2) : [x]는 x보다 작거나 같은 가장 큰 정수 --> 소..

1. 문제: https://www.acmicpc.net/problem/27971해당 문제는 다음과 같은 근거로 BFS로 풀이했다.- 처음에는 강아지가 0마리임 --> N마리로 가기 위한 최소한의 행동횟수 : BFS- 인덱스가 0부터 N까지 존재하는 배열을 그래프로 가정하고, 각 요소에 도착할 때마다 행동횟수를 +1 하는 방식으로 설계한다. ✅ 풀이from collections import deque# n: 키우길 원하는 강아지의 수# m: 닫힌구간의 갯수n, m, a, b = map(int, input().split())visited = [-1] * (n+1) # 1) -1을 선언함으로써 방문여부와 거리를 모두 판단할 수 있도록 함for _ in range(m): l, r = map(int, in..

문제: https://www.acmicpc.net/problem/18126이 문제는 DFS를 활용하여 푸는 문제다. 문제에서 다음과 같은 근거를 찾았다- 입구는 1번이며, 입구에서 방까지 이동 --> 탐색- 문마다 양방향으로 연결하는 길이 --> 그래프- 최대한 입구에서 먼 방까지의 거리 --> 모든 그래프 탐색을 통해 최댓값 탐색 --> DFS*BFS를 활용할 수도 있으나 최단거리를 이용하는 조건이 없으므로 DFS를 활용하는 것이 효율이 좋음 ✅ 풀이import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)n = int(input())graph = [[] for _ in range(n+1)]visited = [False] * (n+1)for _ ..

1. 문제:https://school.programmers.co.kr/learn/courses/30/lessons/72410 ✅ 풀이def solution(new_id): # 1단계 answer = new_id.lower() # 2단계 temp = "" for c in answer: if c.islower() or c.isdigit() or c in ["-", "_", "."]: temp += c answer = temp # 3단계 while ".." in answer: answer = answer.replace("..", ".") # 4단계 answer = answer.strip(".") # 5단계 ..

문제: https://www.acmicpc.net/problem/2437해당 문제는 풀다가 도저히 이해가 안가서 풀이를 보고 이해해보고자 했다 🥲알고리즘 분류를 보니, 그리디 알고리즘을 활용하여 푸는 문제라고 하는데 왜 이게 그리디 알고리즘인지는 아래에서 알아보도록 하자.우선 이 문제를 푸는 방법이다. https://aerocode.net/392 이분의 풀이를 참고했는데, 해당 풀이를 이해한 바는 다음과 같다. 1) "추들을 가지고 측정할 수 있다" = "추를 활용하여 ~ 범위 내의 무게를 측정할 수 있다" 라는 의미로 이해한다. --> 측정할 수 있는 범위를 수직선으로 그려보기2) 무게가 작은 추를 활용하여 측정할 수 있는 무게를 점점 늘려가야하므로, 추들을 오름차순으로 정렬 후 차례대로 올려본다. ..

문제: https://www.acmicpc.net/problem/9996이 문제는 처음에 한번에 못풀었고, 반례를 보고 이해한 다음에 두번째 풀이끝에 성공했다.문제를 풀 때 반례를 가능한한 많이 고려해야하고, 또 반례를 떠올리는 법을 반복적으로 연습해야 한다고 느꼈다. ❌ 첫번째 풀이 - 틀린 풀이n = int(input())expression = input().split("*")start = expression[0]end = expression[1]for _ in range(n): word = input() if word.startswith(start) and word.endswith(end): print("DA") else: print("NE") 해당 풀이는 65%에서 틀렸다는 결과가..

1. 문제: https://www.acmicpc.net/problem/10799이 문제는 인접한 쌍이 레이저, 여는 괄호와 닫는 괄호로 쇠막대기의 왼쪽과 오른쪽 끝의 쌍을 이룬다는 점에서 "스택"을 떠올렸다.그러나 규칙을 찾는 데 어려움을 겪고 제한 시간내에 풀지는 못했다 🥲 따라서 다른 사람의 풀이를 보고 이해한 바를 다시금 정리하고 문제를 풀어보았다. ✅ 풀이  이 규칙대로 코드를 짜면 다음과 같다.pipelines = input()stack = []answer = 0for idx, p in enumerate(pipelines): if p == "(": # 1 stack.append("(") else: if pipelines[idx-1] == "(": # 2. 레이저인 경우 ..

1. 문제: https://www.acmicpc.net/problem/4963해당 문제는 그래프 탐색을 이용하여 영역을 세는 문제다. 단 조금 특이한 점은 "대각선"으로 연결되어있는 사각형도 섬의 영역으로 친다는 점이라서 영역으로 봐야하는 범위가 늘어난다. ✅ 풀이import syssys.setrecursionlimit(10**6) #recursion error를 위해 limit 늘리기input = sys.stdin.readlinedx = [-1, 1, 0, 0, -1, -1, 1, 1]dy = [0, 0, -1, 1, -1, 1, -1, 1]def dfs(x, y): visited[x][y] = True for i in range(8): nx = x + dx[i] ny = y + d..

문제: https://www.acmicpc.net/problem/2559해당 문제는 슬라이딩 윈도우 개념을 활용하여 풀 수 있는 문제이다.슬라이딩 윈도우는 배열에서 하나의 틀(부분 배열)을 일정한 크기 만큼 이동시키며 문제를 풀이하는 알고리즘이다.문제의 예제 2를 참고하여 원리를 보면 다음 그림과 같다. 위와 같이 배열 안에서 분홍색의 고정된 크기만큼 이동하며 각 경우의 합을 세게 되는데, 한칸씩 이동할때마다 이전의 값을 삭제하되 이후의 값을 더하는 방식으로 시간복잡도를 줄이는 방식이다. 이 문제는 "연속적인 며칠 동안의 온도의 합이 가장 큰 값" 을 확인하는 문제이고, "연속적인"에서 고정된 크기 내의 원소들의 합을 구해야한다는 점과 배열의 원소 갯수인 N이 최대가 100,000 이하(=10^5)라는 ..

1. 문제: https://www.acmicpc.net/problem/1260그래프 탐색에 대한 복습 겸 DFS와 BFS 관련 문제를 풀이해보았다. ✅ 인접행렬 활용 풀이import sysfrom collections import dequeinput = sys.stdin.readlinen, m, v = map(int, input().split()) # 정점의 갯수, 간선의 갯수, 시작지점graph = [[0] * (n+1) for _ in range(n+1)]visited = [False] * (n+1)for i in range(m): start, end = map(int, input().split()) graph[start][end] = 1 # 양방향 연결 graph[end][start] = ..