Baekjoon

Baekjoon/구현

🥇[백준] 15686 치킨 배달 (골드5) / 구현, 백트래킹

문제요약 나의 코드 및 설명 백트래킹을 활용하여 가능한 m개의 치킨집 좌표 케이스들을 저장하고, 하나씩 탐색하며 최단 치킨거리를 찾는다. #백트래킹으로 폐업시키지 않을 치킨집 구하기 def dfs(count, start, temp_list): if len(temp_list) == m: #m개가 되면, result.append(temp_list) #result에 저장된 리스트 저장 후 리턴 return for i in range(start, len(chicken)): if i not in v: v.append(i) dfs(count+1, i+1, temp_list+[chicken[i]]) v.pop() n, m = map(int, input().split()) board = [list(map(int, in..

Baekjoon/구현

🥇[백준] 11559 Puyo Puyo (골드4) / 구현

문제요약 나의 코드 및 설명 DFS로 연결된 뿌요들의 좌표를 구하고, 4개 이상 연결된 뿌요들을 터뜨리고 나서 공중에 떠있는 뿌요를 아래로 내린다. #연결된 뿌요들의 좌표를 구하는 코드 def dfs(x,y): global color for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

Baekjoon/구현

🥇[백준] 2638 치즈 (골드3) / 구현, 시간초과 해결, 문제 아이디어

문제요약 나의 코드 및 설명 01 (시간초과) 녹을 치즈가 더이상 없을 때까지 반복을 수행하면서 check_hole() 함수로 내부 공기의 좌표를 구하고, 치즈가 내부 공기 이외의 공기(외부 공기)와 2개 이상 맞닿아 있다면 녹을 예정인 치즈이므로, 리스트 r에 녹을 예정인 치즈의 좌표를 구하는 melt() 함수를 구현하였고, 그리드를 갱신해주도록 소스 코드를 작성했다. 매 반복마다 내부 공기 좌표를 구하는 check_hole() 함수를 통해, 매우 많은 좌표를 중복해서 여러번 탐색하기 때문에 시간 초과가 발생했다. #공기가 치즈 내부에 있는 공기인지 체크 def check_hole(arr): for y in range(n): for x in range(m): cnt = 0 #공기(0)인 좌표 if ar..

Baekjoon/구현

🥇[백준] 16234 인구 이동 (골드5) / 구현, 시간초과 해결

문제요약 나의 코드 및 설명 01 : 77~80%에서 시간초과.. bfs(sx,sy) : 연합 가능한 좌표 탐색하는 bfs 함수이고, 아래의 값들을 구할 수 있다. (sx,sy) 부터 상하좌우로 좌표를 이동하면서 방문한다. 현재의 좌표와 다음 좌표의 나라의 인구 차이가 조건에 부합한다면 방문 처리한다. temp_total : 방문한 좌표의 인구수를 저장하는 변수 temp_cnt : 방문한 좌표의 수를 카운트한다.(하나의 연합을 이루는 나라들의 수가 된다.) check : 연합이 한 번이라도 생성이 되면 check 변수 값을 +1해준다. bfs() 함수의 작성이 끝났다면, 더 이상 연합이 불가능해질 때까지 while문을 통해 반복을 수행한다. 이중 for문을 통해 그리드(board)의 좌표 값(나라)들을 ..

Baekjoon/구현

[백준] 5212 지구 온난화 (실버2) / import copy, list2 = copy.deepcopy(list1), 다시한번 풀어보자

문제요약 나의 코드 및 설명 (틀림..) 50년 후의 지도를 초기화 해두고, 현재 지도의 부분 중 섬인 부분을 방문하여 주변을 둘러싼 바다의 개수를 카운트한 후 50년 후의 지도에 저장하는 식으로 문제를 풀었다. 하지만 풀리지 않았다. 지도의 크기를 줄이는 과정에서 잘못되었나, 섬이 아무것도 없는 경우는 없어서 그런가 하고 여러가지 방법을 5~6번 정도 시도했지만 결국 혼자 힘으로는 풀지 못했다.. ㅠ r, c = map(int, input().split()) #r*c board = [list(input()) for _ in range(r)] dx = [0,-1,0,1] dy = [-1,0,1,0] after = [["."] * c for _ in range(r)] #50년 후의 지도를 정보 for y ..

Baekjoon/구현

[백준] 16918 봄버맨 (실버1) / 구현, 시뮬레이션

문제요약 나의 코드 및 설명 01 (시간초과) 자꾸 시간초과가 발생했다. 이 방법 말고도 3~4가지 방법을 더 사용해봤는데 혼자 힘으로 시간초과를 극복하지 못했다. 격자판 입력받는 부분도 바꿔보고, n%4 == 3 일 때의 방문처리를 다른 방법으로 하는 등 소스들을 여러 번 수정해보았는데 계속 시간초과가 발생했다. import sys r, c, n = map(int,input().split()) #r*c격자판 #n초가 흐른 후의 격자판 board = [] for _ in range(r): board.append(list(sys.stdin.readline())) check = [] for y in range(r): for x in range(c): if board[y][x] == "O": check.app..

Baekjoon

[백준] 11659 구간 합 구하기 4 (실버3) / 누적합 prefix sum

문제요약 나의 코드 및 설명 import sys n, m = map(int, input().split()) num_list = list(map(int, sys.stdin.readline().split())) # [5 4 3 2 1] #인덱스 혼동되지 않기 위해 n+1 길이의 합을 저장할 리스트 생성 prefix_sum = [0 for _ in range(n+1)] #[0,0,0,0,0,0] #리스트에 누적된 합을 저장하는 소스 코드 for i in range(n): prefix_sum[i+1] = prefix_sum[i] + num_list[i] for _ in range(m): start, end = map(int, sys.stdin.readline().split()) #누적된 합이 저장된 리스트의 (..

Baekjoon/이분탐색

[백준] 2805 나무 자르기 (실버2) / 이분탐색

문제요약 나의 코드 및 설명 n, m = map(int, input().split()) #n:나무의 수 m:목표나무의길이 tree = list(map(int, input().split())) tree.sort() # 10 15 17 20 result = [] ## 절단기의 높이를 0~나무의높이의 최대값으로 지정할 수 있음(즉, 0~20) start = 0 #절단기의 높이의 시작값:0 end = tree[-1] #절단기의 높이의 끝값: 나무의높이의 최대값 while start = mid: #설정한 절단기의 높이보다 나무가 크다면 자를 수 있으므로 cutting += (t-mid) #잘랐을때의 나무의 길이의 총합에 저장 if cutting >= m: #만약 나무의 길이의 총합이 목표값 이상이라면 result..

hellosonic
'Baekjoon' 카테고리의 글 목록 (2 Page)