본문 바로가기

알고리즘/🥇 골드

 (72)
백준 1005 ACM Craft 파이썬 풀이 난이도 : 골드3 풀이일 : 05033 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 4% 틀렸습니다 import sys from collections import deque def sol(queue): while queue: i = queue.popleft() for j in child[i]: total[j] = max(total[i] + time[j], total[j..
백준 1027 고층건물 파이썬 풀이 난이도 : 골드4 풀이일 : 04307 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 중간 과정 처음에는 이렇게 건물 높이를 그림으로 그려놓고 어떻게 접근해야 할 지 생각했다. 실제 코드에서는 저런 식으로 배열을 만들 게 아니니까 메모리 같은 것들은 고려하지 않았고, 건물의 최대 개수도 50개여서 시간도 고려하지 않았다. # 1. 모든 건물에 대해 좌, 우 방향 탐색 # 2. 볼 수 있는 건물의 ..
백준 16236 아기상어 파이썬 풀이 난이도 : 골드3 풀이일 : 04274 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 문제 요약 1. 상어는 본인 크기보다 작은 물고기만 먹음 2. 상어 크기와 같은 수의 물고기 먹으면 성장 3. 상어와 크기 같은 물고기 칸 통과 가능, 섭취 불가능 4. 먹을 수 있는 물고기가 많다면 거리가 가까운 물고기 섭취 거리가 가까운 물고기가 많다면 위, 왼쪽 우선순위 5. 아기상어 최초 크기 2,..
백준 17298 오큰수 파이썬 풀이 난이도 : 골드4 풀이일 : 03131 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys n = int(sys.stdin.readline().strip()) arr = list(map(int, sys.stdin.readline().split())) stack = [arr[-1]] num = [-1] * n for i in range(n-2, -1, -1): while stac..
백준 14719 빗물 파이썬 풀이 난이도 : 골드5 풀이일 : 04241 https://www.acmicpc.net/problem/14719 14719번: 빗물첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐풀이 과정 인덱스 활용을 위해 enumerate 사용 배열 안에서 max 탐색 max 좌, 우 방향 두 번째 max 탐색 빗물 += 두 번째 max - 각 인덱스에 있는 값들의 높이 인덱스 범위 : 두 번째 max ~ max (좌, 우 반대) 좌, 우 모두 방향은 유지 탐색 풀이 코드# 1. 인덱스 활..
백준 2096 내려가기 파이썬 풀이, 메모리 초과 해결 난이도 : 골드5 풀이일 : 04226 https://www.acmicpc.net/problem/2096 2096번: 내려가기첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답 -> 3% 메모리 초과# i == 1, 모든 j 넣은 내려오기 함수 실행 # visited 최소값, 최대값 함수 두 번 실행 # DFS 방향으로 세 방향 탐색 # di = [1, 1, 1] # dj = [-1, 0, 1] # i == n-1, 모든 j visited 순회하며 maxi, mini 판별 출력 import ..
백준 5430 AC 파이썬 풀이, 반례 난이도 : 골드5 풀이일 : 04215 https://www.acmicpc.net/problem/5430 5430번: AC각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답import sys T = int(sys.stdin.readline().strip()) for tc in range(1, T+1): p = list(map(str, sys.stdin.readline().strip())) flag = 1 F = 0 B = 0 for i in range(len(p)): if p[i] == 'D': if flag: F += 1 els..
백준 14503 로봇청소기 파이썬 풀이, 반례 난이도 : 골드5 풀이일 : 04204 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답 -> 1% 틀렸습니다.import sys def clean(arr, i, j, h): sell = 0 while True: if arr[i][j] == 0: arr[i][j] = -1 sell += 1 next_sell = 0 for k in range(..
백준 13549 숨바꼭질3 파이썬 풀이, 반례 난이도 : 골드5 풀이일 : 04193 https://www.acmicpc.net/problem/1354913549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답 -> 8% 틀렸습니다import sys N, K = map(int, sys.stdin.readline().split()) def find(num): visited = [0] * 100000 queue = [num] visited[num] = 1 p = 0 while p ..
백준 7569 토마토 파이썬 풀이 난이도 : 골드5 풀이일 : 04171 https://www.acmicpc.net/problem/7569 7569번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐풀이 과정 - 익은 토마토는 동, 서, 남, 북, 상, 하 6방향 토마토에 영향 - 3차원 형식으로 리스트 구성 -> 6방향 탐색 진행 - 포인터 사용으로 pop 연산 시간초과 방지 - 익은 토마토 리스트를 구성해 토마토 숙성 함수에 넘겨주기 - 토마토가 익는 날짜는 이전 숫자 +1 기록 -> ..
백준 2573 빙산 파이썬 풀이, 시간초과, 반례 난이도 : 골드4 풀이일 : 04156 https://www.acmicpc.net/problem/2573 2573번: 빙산첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답 -> 34% 시간 초과import sys def melt(arr): global day temp = [[0] * m for _ in range(n)] flag = False # 빙산 존재 여부 # 녹을 높이 구하기 for i in range(n): for j in range(m): if arr[i..
백준 7576 토마토 파이썬 풀이, 시간초과 해결 난이도 : 골드5 풀이일 : 04145 https://www.acmicpc.net/problem/7576 7576번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답# 익은 토마토 발견 시, 리스트에 추가 # 리스트를 인자로 하는 함수에서 토마토 인근 4방향 탐색 # 익지 않은 토마토가 있다면, -1 출력 import sys # 익은 토마토 찾기 함수 def tomato(arr): red = [] for a in range(n): for b in ra..

티스토리툴바