본문 바로가기

728x90

알고리즘 문제 풀이/DFS,BFS24

[백준] 포도주 시식 https://www.acmicpc.net/problem/2156 문제에 나온 예시 입출력을 가지고 20분정도 고민해보니 규칙을 찾을 수 있었다.길이가 n인 일차원 배열 wines에는 와인의 양을 저장한다.길이가 n인 일차원 배열 dp에는 마실 수 있는 포도주의 최댓값을 저장한다.포도주 잔이 k개 있는 경우(k>=3) 포도주를 마실 수 있는 경우의 수는 아래 중 최댓값이다.k번째 포도주, k-1번째 포도주를 마시는 경우이 경우 최대값은 k번째 포도주 양 + k-1번째 포도주 양 + k-3번째까지 마신 포도주 최댓값즉, dp[k] = wines[k] + wines[k-1] + dp[k-3]k번째 포도주, k-2번째 포도주를 마시는 경우이 경우 최대값은 k번째 포도주 양 + k-2번째까지 마신 포도주 최대.. 2024. 11. 25.

[백준]2573번: 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net bfs로 정직하게 풀어주었다..! 내 코드로는 python3로는 시간초과가 났고, pypy3로는 정답 판정을 받았다. 1. 빙산이 몇덩어리인지 확인 1-1. 두 덩어리 이상이라면, 경과시간(year)을 출력하고 프로그램 종료 2. 빙산 녹이기 작업 및 경과시간(년) 증가 3. 빙산이 모두 녹았는지 체크하고, 모두 녹았다면 0을 출력하고 프로그램 종료 코드 from collections imp.. 2023. 7. 28.

[백준]5014번: 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net bfs로 풀었다. 최초 좌표를 큐에 넣고, 큐에서 하나씩 꺼내서 위 또는 아래 층의 범위와 방문여부를 체크하였다. 최초의 좌표 s의 방문 여부 체크를 하지 않아서 자꾸 오답이 나왔었다. python from collections import deque f, s, g, u, d = map(int, input().split()) elevator = [0 for _ in range(f+1)] q = deque() .. 2023. 7. 23.

[백준]11725번: 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net python import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) visited = [0 for _ in range(n+1)] result =.. 2023. 7. 18.

[백준]1926번: 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs import sys from collections import deque input = sys.stdin.readline dx = [-1,0,1,0] dy = [0,1,0,-1] def bfs(x,y): q = deque() q.append((x,y)) cnt = 0 while q: x,y = q.popleft() for i in range(4): nx, ny = x + dx[i], y + dy.. 2023. 7. 16.

[백준]14940번: 쉬운 최단거리 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 목표지점을 시작점으로 하여, 모든 지점까지의 거리를 구해서 출력하면 된다. "원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 라는 조건만 잘 보면 될 것 같다. python import sys from collections import deque input = sys.stdin.. 2023. 7. 3.

이전 1 2 3 4 다음

728x90

티스토리툴바