생각하는 아져씨

1912번: 연속합https://www.acmicpc.net/problem/1912 문제 정의n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 DP 테이블을 어떻게 정의해야 할까 고민했다.예제를 보면서 규칙을 찾으려고 했다. 연속합이므로 연속적인 숫자의 합이니까 이전의 값을 활용해야지 라는 생각으로 접근했는데, 생각보다 정의하기 어려웠다. 다이나믹 프로그래밍이 맞지만, ..

9461번: 파도반 수열https://www.acmicpc.net/problem/9461 문제 정의오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 접근 방법규칙을 찾고 점화식을 세우는 다이나믹 프로그래밍을 이용한다. 문제 해설규칙을 찾으면 N=6부터 점화식을 세울 수 있다.dp[i] ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 정의어떤 숫자 N과 numbers가 주어질 때, N과 사칙연산만 사용해서 numbers를 표현해야 한다.이 때 N 사용횟수의 최솟값을 리턴해야 한다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 dp 테이블을 어떻게 정의해야 하는지 고민하다가 처음에는 다음과 같이 정의했다.dp[i]: i를 만드는데 필요한 N의 최소 개수 N = 5일 때, dp[0] = 0, dp[1] = 5/5 → 2, … dp[5] = 1 그리고 점화식으로는, dp[i] = min(1~(i-1) 중 더해서 i가 되는 조합의 숫자에 해당하는 인덱스의 dp 값) 즉, dp[7] = min(dp[1] + dp[6],..

2805번: 나무 자르기https://www.acmicpc.net/problem/2805 문제 정의상근이는 M미터의 나무가 필요해서 나무를 벌목하려고 한다. 절단기의 높이를 설정하면, 높이만큼 나무를 잘라주는데, 나무들의 높이가 주어졌을 때 적어도 M미터의 나무를 가져가려면 절단기의 높이를 최대 몇까지 설정할 수 있을까? 접근 방법나이브한 접근방법나무리스트 [20, 15, 10, 17] 가 주어졌을 때, 절단기의 높이를 1~최대 나무 높이(=20)까지 설정해보면서, (나무-절단기높이)의 합이 M미터 이상인지 확인하면 된다.즉, sum(각 나무높이 - 절단기 높이) ≥ M (적어도 M 미터이므로, M이상과 비교하면 된다.)하지만, N은 최대 2,000,000,000 이므로, 이중 for문을 사용하면 시간 ..

24479번: 알고리즘 수업 - 깊이 우선 탐색 1https://www.acmicpc.net/problem/24479문제 정의입력으로 주어지는 간선 정보로 DFS를 수행하고 각 노드의 방문 순서를 출력한다. 접근 방법DFS 알고리즘 활용 문제 해설각 노드 정보를 이차원 리스트 정보로 받는다.무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.시작 노드인 R 부터 DFS를 수행한다. 풀이import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N, M, R = map(int, input().split()) # 정점 개수, 간선 수, 시작 정점 graph = [[] for _ in range(N+1)] # 연결 그래프 vis..

플로이드 와샬(Floyd-Warshall)동작 과정A → 1번 노드 → B 로 가는 최단 거리 비용은?점화식시간복잡도코드참조 플로이드 와샬(Floyd-Warshall)모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다. 👉 최단경로를 구하는 다익스트라와 다른점은?다익스트라는 ‘한 지점에서 다른 특정 지점까지의 최단 경로’를 구하는 알고리즘인 반면, 플로이드 와샬은 모든 노드에 대한 최단 경로를 찾는 것이 목적이다.또한 다익스트라는 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾아야 하는데, 플로이드 와샬은 찾지 않아도 된다.마지막으로, 다익스트라는 최단거리를 1차원 리스트에 저장하는데, 플로이드 와샬은 2차원 리스트에 저장한다는 특징이 있다. ..