본문 바로가기

전체 글

 (131)
[BOJ] 트리의 부모 찾기_11725 각 노드의 부모를 나타내는 문제이다. 1을 매개변수로 받아서 while stack구문으로 해당 노드가 가지는 자식을 가져왔고, 그 자식에 해당 노드를 대입하며 부모 노드를 구하였다. 이러한 문제를 풀 때, 내가 자주 헷갈리는 것은 visited[x] = True의 위치이다. 위 코드도 처음에는 if not visited[i]: 안에 있었다. 그렇다면 왜 if not visited[i]안에 있으면 안되고, 그 위에 있으면 가능한 것인가? -> visited는 방문 처리를 해주는 것이다. 위 코드에서는 stack에서 pop을 한 후, 방문처리를 하고 이후 작업들을 수행한다. 하지만 if not visited안에서 visited방문 처리를 해주면, 아직 append만 되었고 pop을 하지도 않았는데 방문처리를..
[BOJ] 계단 오르기_2579 해당 문제는 DP를 이용해서 풀었다. dp[4] 이상부터는 dp[i] = max(dp[i - 2] + data[i], dp[i - 3] + data[i] + data[i - 1])코드로 dp값을 구할 수 있다. 그렇다면 왜 저 코드가 최대값을 의미하는가? 나는 dp를 풀 때, 문제를 보고 직접 써보며 규칙을 찾아내려고 하는 편이다. 그래서 찾은 규칙: 4번째부터는 해당 값이 최대가 되려면, 4보다 두칸 적은 계단까지의 최대값(dp[2])와 data[4] or 4보다 3칸 적은 계단까지의 최대값(dp[1])과 data3+data4를 더한 후 이 두개 중 최대값이 dp[4]값이 된다. 이 문제를 풀 때 dp[i-1]+data[i]와 같은 식으로 풀려고 했으나 그럼 dp[i-1]이 두칸 연속으로 얻은 값인지 ..
[BOJ] 1로 만들기_1463 위 문제는 전형적인 DP문제이다. 우선 문제를 리뷰하기 전에 DP의 탑다운 방식과 바텀업 방식의 차이에 대해 짚고 넘어가자. 동적 계획법이란? 큰 문제를 작은 문제들로 나누어 푸는 것을 일컫는 말이다. 동적 프로그래밍 방법 작은 문제로 나누어 해결할 떄, 중복된 값을 구하지 않고 메모제이션 하는 것이다. 메모제이션을 하는 방식과, 그렇지 않은 방식에 대해 설명하겠다. F는 피보나치 함수이다. 메모제이션을 하지 않고, 탑 다운 방식으로 피보나치 수열을 구한다면 작은 단위의 값을 반복해서 여러번 계산해야 한다. 이를 바텀업 방식으로 해결할 수 있다. 위와 같이 작은 단위의 값을 배열에 저장하여, 해당 값이 필요할 떄 작은 단위를 반복하여 계산하지 않게 된다. 1로 만들기 문제도 이러한 방식으로 해결할 수 있..
[BOJ] 단어 정렬_1181 이 문제는 내가 몰랐던 파이썬 문법으로 해결할 수 있었다. data.sort(key = lambda x: (x[1], x[0])) 을 하면 x[1]을 기준으로 정렬할 떄, 우선순위가 같은 것이 있다면 x[0]으로 비교해서 정렬하는 것이다. 그리고 word[0]에는 그냥 문자열을 넣었는데, data.sort(key = lambda x: (x[1], x[0]))에서 x[0]을 통해 파이썬에서 알아서 정렬해준다.
백준 빙산 2573 해당 문제의 정답 코드이다. 더보기 from _collections import deque import copy n, m = map(int, input().split()) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] data = [list(map(int, input().split())) for _ in range(n)] # 얼음아 녹아라. def melting(): data_copy = copy.deepcopy(data) for i in range(n): for j in range(m): if data_copy[i][j] != 0: for z in range(4): nx, ny = i + dx[z], j + dy[z] if 0
백준 16236 파이썬 더보기 from _collections import deque n = int(input()) data = [list(map(int, input().split())) for _ in range(n)] shark_size = 2 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] cnt = 0 size_count = 0 def search_fish(): result = n ** 3 nx, ny = 0, 0 global cnt global shark_size global shark_point global size_count for i in range(n): for j in range(n): if data[i][j] != 0: if data[i][j] < shark_size: move_size ..
[BOJ] 연구소_14502.. 위 사진은 답안의 전체 소스 코드이다. 이 문제를 이해하는데 총 3일이 걸렸다... 3일 동안 이 문제를 본 것이 아니지만, 너무 이해가 안가서 딴짓하다 오기를 반복하며 시간을 많이 소비했다. (알고리즘 때려치고 싶었다...) 문제를 대충 이해하고 푼 지금에도 2주 뒤에 풀라고 한다면 못 풀 것 같다.. 우선 가장 이해가 가지 않았던 부분. 1. 벽 세우기. 전체 벽을 세워야 하니까... 중첩 반복문으로 n*m중에 3개를 뽑는 경우의 수를 모두 고려해 줘야 한다. 지금도 헷갈리는게 build_wall가 모든 경우를 고려해 준 것이 맞는지 잘 모르겠다... (이해하기 위해 그림으로 그린 후, 이해한 것을 기록하자.) 그리면서 대충은 이해한 것 같은데,, 아직 확신이 안든다. 이것만 잡고 있을 순 없으니 일..
[BOJ] 잃어버린 괄호_1541 이 문제는 쉬웠는데,,, 내가 잘 생각하지 못하는 파이썬 문법이라 암기가 필요할 것 같다. 처음 data = list(map(str, input().split("-")을 사용했는데, 이건 input().split("-")랑 당연히 똑같다. map을 통해 split로 나눈 배열을 str자료형으로 바꾸는 것을 -> list배열로 만드는 것인데.. input으로 받아오는 데이터는 원래 자료형이 str이라 바꿔줄 필요가 없었고, split로 나누면 배열로 만들어지기 때문에 그냥 input().split("-")을 사용하면 되는 것이였다.. 이번 문제는 input().split("문자")에 대해 다시 한번 떠올리게 되는 문제여서 좋았다. 그리고 아직 파이썬 문법에서는 list, map, input().split(..

티스토리툴바