Breath everything

이것 저것

IT/백준

1. 생각정리 탑을 쌓을 때 고려해야 하는 사항은 세 개다. 무거운 것은 무조건 아래 밑면이 넓은 것은 무조건 아래 위의 두 조건들을 만족시키면서 가장 높은 탑을 쌓을 수 있어야 함 일단 '밑면의 넓이' 혹은 '무게' 중 하나에 대해 정렬을 해준 뒤 코드를 짜면 생각해야 할 조건이 하나 줄어든다. 그리고 dp를 이용해서 하나씩 영역을 확장시키며 쌓을 수 있는 가장 높은 높이를 구할 수 있지 않을까? 여기서 "첫 번째까지 고려한 최대 높이는 dp [1]에", "두 번째까지 고려한 최대 높이는 dp [2]에"... 이렇게 dp를 채운 뒤 dp리스트의 최댓값이 쌓을 수 있는 최대 높이이다. 그리고 mapp과 dp를 바탕으로 하나씩 기억을 더듬어가면 문제가 원하는 답을 도출할 수 있다. 2. 성공 코드 N = ..

2021. 10. 23.

IT/백준

1. 생각 정리 전체 map에서 배추가 심어져 있는 위치를 입력받고, 몇 개의 지렁이가 필요한지 구하는 문제 지렁이는 인접한 배추로 이동할 수 있기 때문에 연결되어있는 배추 지역에는 지렁이가 하나만 있어도 됨 결국 전체 map에 0(배추x), 1(배추 o)로 입력을 받고 섬처럼 생긴 1 지역이 몇 개인지? 구하는 접근을 가지면 됨 DFS와 BFS 둘 다 활용하여 풀어보자 2. BFS 시간초과 코드 한번 탐색한 부분은 다시 탐색하지 않게 전체 map과 같은 크기인 visited 리스트를 따로 만들어서 정보를 관리했더니 시간 초과가 떴다. #bfs 시간초과 from collections import deque def bfs(start): q=deque() q.append(start) dir = [(-1,0)..

2021. 10. 13.

IT/백준

1. 생각 정리 수빈이의 위치에서 동생의 위치까지 무조건 동생과 가까워지는 루트만 따라가면 오히려 시간이 오래 걸릴 수도 있다. 그러므로 각 프로세스마다 (프로세스 단계 * 3)만큼 다양해지는 모든 경우를 고려하여 그중 동생의 위치까지 갔을 때 지금까지 소요된 시간 출력 크기가 100001인 일차원 리스트에 각 위치마다 시간이 얼마나 걸렸는지 갱신하며 동생을 찾을 수 있는 가장 빠른 시간을 구하기 2. 메모리 초과 코드 #메모리 초과 from collections import deque N,K = map(int, input().split()) def bfs(n,k): q = deque([N]) result = 0 count = 1 while q: pos = q.popleft() if pos == K: p..

2021. 10. 12.

IT/백준

1. 생각 정리 처음에 간선 정보 입력을 2차원 리스트에 [[1,2], [1,3]]이런 식으로 담으려 했는데 문제를 더 간단히 풀기 위해서는 빈 2차원 리스트를 생성한 뒤 1행에 1과 연결된 정점 넣어주기, 2행에 2와 연결된 정점 넣어주기... 의 느낌으로 입력받는 게 더 편함 visited 리스트를 따로 만들어서 이미 탐색된 정점에 대한 정보를 관리 DFS의 경우에는 재귀함수로, BFS의 경우에는 deque를 이용하여 구현 2. 코드 구현 from collections import deque #정점 개수 N, 간선 개수 M, 탐색 시작 정점번호 V N, M, V = map(int, input().split()) mapp = [[] for _ in range(N+1)] #두개의 정점이 연결되어있다는 간..

2021. 10. 12.

IT/백준

1. 생각 정리 무조건 다음 숫자가 지금 보다 크다고 해서 수열에 포함시키면 정답을 구하지 못할 수도 있다 수열의 시작부터 전체로 확장해나가며 가장 긴 수열의 길이를 찾아보자 길이가 4인 [10,20,10,30] 수열이 있으면 [10]이면 1, [10,20]이면 2, [10,20,10]이면 2, [10,20,10,30]이면 3처럼 확장해나가며 정답을 도출해보자 2. 코드 구현 N = int(input()) arr = list(map(int, input().split())) dp = [1]*N for i in range(1,N): for j in range(i): if arr[j]dp[i]: dp[i]+=1 print(max(dp))

2021. 10. 11.

IT/백준

1. 문제 조건 N개의 물건이 있고 각 물건은 무게 W와 가치 V를 가짐 무게 K까지 담을 수 있을 때 물건의 가치합 최대값 구하기 2. 풀이 전 생각정리 각각의 물건을 한번씩 훑으며 가능한 모든 경우에 대한 가치합을 리스트에 저장한다. 무게 7까지 담을 수 있고 물건 2개의 (무게, 가치)가 (2,3), (4,2)라면 3 3 2 5 이런 식으로 저장하며 물건들의 가치합 최댓값은 5 임을 알 수 있다. 무게 합이 K를 초과하는 경우에는 담을 수 없음을 고려한다. 3. 테스트 케이스만 통과한 코드 N, K = map(int, input().split()) mapp = [] for _ in range(N): W, V = map(int, input().split()) mapp.append([W,V]) dp =..

2021. 10. 11.

IT/백준

1. 문제 조건 곡의 개수 N, 시작 볼륨 S, max 볼륨 M 매번 곡 연주를 시작하기 전에 볼륨 조정을 하는데 볼륨 조정이 가능한 값이 V리스트에 담겨있음 ex) max 볼륨이 10, 시작 볼륨이 5, V[0]이 3이면 될 수 있는 볼륨 값은 2 or 8 2. 풀이 전 생각정리 볼륨 조정이 들어갈 때마다 가능한 볼륨의 가짓수는 2배로 늘어난다. 단 가능한 볼륨값 범위 안에 속하지 않은 옵션들은 없애줘야 한다. 볼륨 조정이 있을 때마다 가능한 볼륨의 크기를 담고, 다음 볼륨 조정이 있을 때 다시 확장시키는 방법? (N+1)*(M+1) 크기의 0으로 초기화된 리스트를 만들어 볼륨 조정을 하나씩 해가며 발생할 수 있는 경우를 1로 표시해놓기? 3. 메모리 초과 뜬 코드 볼륨 조정을 하기 전마다 가능한 볼륨..

2021. 10. 5.

IT/백준

1. 문제 조건 첫째줄과 둘째 줄에 비교할 수열이 주어짐(각각의 길이는 같지 않을 수 있음)(최대 1000글자(알파벳 대문자)) 문자열을 비교했을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기 2. 풀이 전 생각정리 수열 x와 y가 주어졌을 때 (x[0]과 y전부 비교하여 dp 갱신, x[1]과 y전부 비교하여 dp 갱신...) 이런 식으로 차근차근 dp를 갱신해보자 dp의 크기는 (x의 길이+1) * (y의 길이+1) / 처음에는 다 0으로 채워넣어주기 이중 for문을 돌면서 두 가지 상황이 발생 x의 값과 y값이 같을 때 dp[i][j] = dp[i-1][j-1]+1 x의 값과 y값이 같지 않을 때 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) dp를 다 갱신하고 dp..

2021. 10. 5.

IT/백준

1. 문제 조건 지도는 NxM 이차원 격자(1

2021. 8. 24.