알고리즘
-
백준 9328번 열쇠알고리즘 2023. 8. 10. 15:41
빈칸, 벽, 문서, 열쇠, 문이 있는 평면도가 주어졌을 때, 최대로 가질 수 있는 문서의 개수를 구하는 문제입니다. 문과 같은 경우 초반에는 모두 잠겨있으므로 열쇠를 먼저 얻어야지만 문을 통과할 수 있습니다. 초반에 열쇠가 주어질 수도, 안 주어질 수도 있습니다. 처음 들어갈 수 있는 위치는 평면도의 가장자리입니다. 사용 변수들 X # 행 크기 Y # 열 크기 maps # 문제에서 주어진 평면도. 크기 : maps[X][Y] keys # 열쇠를 저장할 집합 door # 평면도 탐색 중 열지 못한 문의 좌표 저장 visited # 평면도 방문 여부 저장. 크기 : visited[X][Y] 시작 위치 선정 들어갈 수 있는 부분은 평면도의 가장자리입니다. 그렇기 때문에 반복문을 통해 시작점의 위치를 찾을 수 ..
-
백준 2042번 구간 합 구하기알고리즘 2023. 8. 9. 09:19
N개의 수가 주어지고 연속된 어떤 부분의 합을 구하는 문제입니다. 중간에 i번째 수를 X로 바꾸어주기도 합니다. 이번 문제의 풀이에 앞서 이번 문제의 알고리즘 분류인 세그먼트 트리에 대해 알아보았습니다. 세그먼트 트리 세그먼트 트리는 여러 개의 연속된 데이터가 존재 할 경우 연속된 어떤 부분의 데이터 합을 구하는 방법에 관한 알고리즘입니다. N개의 변 할 수 있는 데이터에서 연속된 수 M개의 합을 여러번 구하는 방법은 무조건 M번의 반복을 통해서 구할 수 있습니다. N과 M이 엄청 큰 수라면 오랜 시간이 걸리게 될 것입니다. 세그먼트 트리는 트리의 서브트리에 포함된 연속된 범위의 데이터들의 합을 각 서브트리의 루트 노드에 저장 할 수 있도록 해줌으로써 좀 더 빠르게 특정 범위의 데이터의 합을 구 할 수 ..
-
백준 1069번 집으로알고리즘 2023. 8. 8. 12:18
X,Y에서 0,0으로 갈 수 있는 가장 빠른 시간을 구하는 문제입니다. 이동하는 방법은 두 가지로 걷거나 점프 할 수 있습니다. 걷기는 1초에 1만큼씩 움직이는 것입니다. 점프는 T초에 D만큼 움직일 수 있고 일직선으로만 할 수 있고 정확하게 D칸만 움직일 수 있습니다. 시도 1. 초반에는 입력에 대한 출력을 이해하는 것도 잘 되지 않았습니다. 예제 입력 1 # 입력 6 8 5 3 # 출력 6.0 6,8에서 0,0까지의 거리가 10이므로 두 번의 점프로 이동하면 0,0에 도착 할 수 있습니다. 예제 입력 1, 2, 3은 어느정도 생각하면 바로 떠올랐지만 예제 입력 4나 6은 바로 생각이 떠오르지 않아 힘들었습니다... 예제 입력 4 # 입력 400 300 150 10 # 출력 7.0 400,300에서 0..
-
백준 2470번 두 용액알고리즘 2023. 8. 7. 16:52
많은 종류의 산성 용액과 알칼리성 용액이 있을 때, 어떠한 두 용액을 섞었을 경우 두 용액의 특성값의 합이 0에 가장 가까운 용액을 구하는 문제입니다. (산성 용액의 특성값은 1~1,000,000,000까지의 양의 정수이고, 알칼리성 용액의 특성값은 -1 ~ -1,000,000,000까지의 음의 정수입니다.) 시도 1. 용액의 오름차순으로 정렬하고, 특성값의 합이 0에 가장 가까운 두 용액을 찾기 위한 방법을 고민했습니다. 입력 설명에 모든 용액이 산성 용액 혹은 알칼리성 용액으로만 주어지는 경우가 있다고 하여, 0에 가장 가까운 숫자를 찾는 것에 집중했습니다. 아래는 제가 생각한 예시였습니다. -101 -90 -5 10 12 110 위와 같이 용액이 주어졌을 경우 제 생각에는 0에 가까울수록 다른 특성..
-
백준 1937번 욕심쟁이 판다, 2437번 저울 (python)알고리즘 2023. 8. 4. 13:44
욕심쟁이 판다 (1937번) n * n 크기의 대나무 숲에서 판다가 움직이며 대나무를 먹을 때, 이동하는 칸의 대나무가 이전 칸의 대나무보다 많아야지만 이동 할 수 있을 때 판다가 이동 할 수 있는 칸의 수의 최대값을 출력합니다. 판다가 처음 이동을 시작하는 칸도 주어지지 않았기 때문에 모든 칸을 시작점으로 생각하여 이동을 해봐야 된다고 생각했습니다. 하지만, 모든 칸에서 이동 할 수 있는 칸의 수를 세는 것은 시간이 오래 걸릴 것으로 예상했습니다. 그래서, 각 칸마다 해당 칸에서 이동 할 수 있는 최대 칸의 개수를 저장해서 이전에 방문했던 칸이라면 다시 순회하지 않도록 했습니다. dp 문제는 이전의 어떤 로직에 의해 발견된 값과 현재 다시 이 칸을 방문했을 때의 값을 비교해서 다른 값을 채워넣는 식의 ..
-
백준 1202번 보석 도둑알고리즘 2023. 8. 3. 09:38
N개의 보석의 무게 Mi 와 가격 Vi 가 주어지고, K개의 가방이 담을 수 있는 최대 무게 Ci가 주어졌을 때, 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제입니다. (가방 한 개에는 최대 한 개의 보석만 담을 수 있습니다.) 시도 1. 가장 큰 가격의 보석을 넣을 수 있는 가장 작은 크기의 가방을 선택하여 넣어주도록 했습니다. 우선 가방을 오름차순으로, 보석은 가격순으로 내림차순으로 정렬했습니다. 현재 보석의 무게보다 같거나 큰 가방 중 가장 작은 가방을 선택하도록 했습니다. 이를 위해 이분탐색을 선택해 대입했습니다. def search(num): s,e=0,len(bags)-1 m=(s+e)//2 while snum: e=m-1 else: s=m+1 m=(s+e)//2 while m
-
백준 11437번 LCA , 11438번 LCA2알고리즘 2023. 8. 2. 12:21
LCA란 Lowest Common Ancestor로 두 정점의 가장 가까운 공통 조상을 찾는 문제입니다 시도 1. 루트 노드인 1번 노드부터 연결된 간선을 통해 자식 노드들을 내려가게 됩니다. 이 때, 자식노드의 부모노드를 모두 저장하면서 내려가도록 합니다. 여기서 중요한 것은 주어지는 입력이 루트노드로부터 가까운 순이 아니므로, 모든 간선의 입력을 받은 뒤 부모노드와 자식 노드를 분간해야 된다는 것입니다. 모든 노드의 부모노드를 찾은 뒤, 두 정점으로부터 가까운 공통 부모를 찾아줍니다. 한 노드로부터 부모노드로 계속 이동하여 루트 노드까지 방문하고 방문한 노드에 표시를 해줍니다(visited 배열을 통해). 그 다음 다른 노드 또한 부모노드로 계속 이동하여 루트 노드까지 이동하는데 visited 배열에..
-
백준 2048 (Easy) (Gold 2)알고리즘 2023. 7. 27. 10:18
2048 게임을 어느 방향이든 5번 실행했을 경우 가장 큰 숫자를 출력하는 문제입니다. 문제를 읽고 이번 문제는 2048게임 구현 + 모든 경우의 수를 살펴 봐야겠다는 생각을 했습니다. 우선 구현부분에 대해 생각해봤습니다. 2048게임 동작 원리 한 가지 방향에 대해 밀기를 할 때 동작하는 원리에 대해 우선 파악했습니다. 밀었을 때 일어나는 현상은 간단하게 두 가지 였습니다. 두 블럭이 같은 숫자라면 합쳐진다. 두 블럭이 다른 숫자라면 나란히 놓여진다. 여기서, 몇 가지 조건이 추가되는데 이는 빈 공백이 있을 경우입니다. 이 게임은 모든 칸에 숫자가 적혀있는 것이 아니라 공백이 있을 수도 있기 때문에 공백이 있을 경우도 생각하며 구현을 해야합니다. 구현 숫자를 가져오고 합칠 수 있는 방법에 대해 많이 고..