알고리즘
-
백준 1167번 트리의 지름 (Gold 2)알고리즘 2023. 7. 26. 14:59
트리에서 임의의 두 점 사이의 거리가 가장 긴 경우를 지름이라고 할 때, 이 지름을 구하는 문제입니다. 시도 1. 첫 노드부터 마지막 노드까지 순회를 하면서 가장 거리가 먼 노드를 구하고 해당 길이 중 최대 길이를 출력하도록 했습니다. 각 노드로부터의 거리를 저장하기 위한 변수 dp와 각 순회마다 노드의 방문 여부를 확인하는 visited배열도 선언해주었습니다. dp 배열과 visited 배열은 2차 배열로 선언했습니다. dp[i][j]일 경우 i 노드에서 j 노드로 가는 가장 긴 경로를 저장하고 visited[i][j]일 경우 i 노드에서 하나의 간선으로 j를 갈 수 있을 경우 i->j 로 갔었는지 여부를 저장하도록 해주었습니다. 이 후 priorityqueue를 이용해 현재까지 이동 거리가 긴 경우부..
-
백준 알고리즘 풀이 (Gold) 1753번, 1655번알고리즘 2023. 7. 25. 13:16
1. 최단 경로 (1753번) 단방향 간선과 간선에 대한 가중치가 주어졌을 때, 시작점에서 다른 정점으로의 최단 경로를 출력하는 문제입니다. 정점에서 다른 정점으로 이동하는 최단 거리를 구하는 문제로 다익스트라 알고리즘을 활용했습니다. 첫 번째 시도 기존의 최단 거리를 구하는 문제들처럼 dfs와 정점까지의 가중치의 합을 저장하기 위한 dp배열을 선언하여 문제를 풀어주었습니다. stack = [[K,0]] dp[K] = 0 while stack: node,weight = stack.pop() for v,w in edges[node]: if weight+w
-
백준 DP 문제 풀이 (Silver) 11053번, 1932번, 1912번, 9461번 python알고리즘 2023. 7. 21. 15:03
1. 가장 긴 증가하는 부분 수열 (11053번) 숫자 수열이 주어질 경우 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다. 예시) {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50}이고 길이는 4입니다. 앞에서부터 차례로 자신을 포함하는 가장 긴 부분 수열을 구하면 됩니다. 자신을 포함한 가장 긴 수열을 구하는 방법은, 자신보다 앞에 위치하면서 자신보다 작은 숫자 중 현재 가장 긴 증가하는 부분 수열을 가지는 숫자에 자신을 붙이면 됩니다. 위의 예시 중 4번째 인덱스의 30을 포함한 부분 수열을 구하는 예를 들어보겠습니다. 30보다 앞에 위치한 숫자 중 30보다 작은 10,20,10 중 증가하는 부분 수열 중 가장 긴 숫자는 20입니다. 그러므로..
-
프로그래머스 요격 시스템 (LV 2)알고리즘 2023. 7. 9. 10:29
이번 문제는 A나라가 B 나라에 미사일 공격을 할 때, B가 A의 공격을 막아낼 수 있는 최소의 미사일 개수를 구하는 문제입니다. A에서 발사된 미사일은 (s,e) 형태로 주어지고 지상과 평행한 직선으로 s~e 사이를 개구간으로 이동합니다. B의 미사일은 x 지점에서 지상과 수직으로 날아가 x좌표에 걸쳐 있는 모든 A의 미사일을 격추시킬 수 있습니다. targets, s와 e 입력의 범위가 큰 것을 확인했고 최대한 반복문을 자제해야겠다는 생각이 들었습니다. 처음 이 문제를 확인했을 때 관련된 문제를 풀어본 경험이 없어 어떻게 풀어야할지 생각이 떠오르지 않았습니다. 우선, 알고리즘적으로 어떤 미사일을 먼저 격추시키는 것이 최소한의 미사일을 사용할 것인지 생각했습니다. 시도 1. e-s 크기가 작은 미사일에..
-
1248. [S/W 문제해결 응용] 3일차 - 공통조상알고리즘 2023. 7. 8. 14:38
이 번 문제는 이진 트리가 주어지고 두 정점이 주어졌을 때, 이 두 정점에서 가장 가까운 공통 조상을 찾는 문제입니다. 처음 이 문제를 접 했을 때, 각 노드에 대한 방문 여부를 확인할 수 있는 visited 배열을 이용하여 문제를 해결할 수 있다고 생각했습니다. 주어진 접점1에서 루트 노드인 1로 올라가면서 방문하는 접점을 표시하고 접점2에서 루트 노드인 1로 다시 올라가면서 처음으로 방문한 노드가 나온다면 해당 노드가 가장 가까운 공통부모일 것이라고 생각하고 문제를 풀게 되었습니다. 시도 1. 이번 문제의 입력이 "부모 자식" 순서로 간선에 연결된 접점을 알려주었습니다. 그래서 부모에서 자식으로 뻗은 간선은 parentEdges, 자식에서 부모로 뻗은 간선을 childEdges에 저장했습니다. 각 2..
-
[S/W 문제해결 응용] 4일차 - 보급로알고리즘 2023. 7. 7. 19:24
이 문제는 2차원 배열이 주어지고 각 칸마다 높이가 주어진다. 각 칸을 이동할 때 각 칸에 적힌 숫자만큼 머무를 때, 0,0에서 부터 N-1, N-1 칸으로 이동하는 가장 빠른 시간을 출력하는 문제입니다. 마지막 칸에 가장 빠르게 도착하기 위해서는 각 칸에 가장 빠르게 도착하는 시간을 알고 있어야 한다고 생각했습니다. 그렇기 때문에 각 칸에 가장 빠르게 도착한 시간을 저장할 수 있는 dp라는 배열을 N*N 크기로 선언을 해주었습니다. 이 후 각 칸에 방문하는 방법은 queue를 이용해 bfs로 각 칸을 탐색할 수 있도록 해주었습니다. 맨 처음에 0,0을 queue에 넣어줌으로써 bfs로 탐색할 수 있도록 해주었습니다. x,y 칸에서 nx,ny로 이동할 경우 nx, ny칸이 방문하지 않은 칸이거나, (현재..
-
SW Expert Academy 1868. 파핑파핑 지뢰찾기 (D4)알고리즘 2023. 7. 5. 19:51
1868. 파핑파핑 지뢰찾기 이 문제는 N*N 크기의 지뢰 찾기 게임이 주어지고 지뢰의 위치를 사용자가 안다면, 최소 몇 번의 클릭을 통해 지뢰를 제외한 모든 지역에 숫자를 표시할 수 있는지 출력하는 문제입니다. 이번 문제는 지뢰찾기 룰에 대해 조금 알고 문제풀이에 들어가는 것이 좋습니다. (이번 문제는 사용자가 지뢰의 위치를 알고 있기 때문에 지뢰를 클릭했을 때의 상황은 넘어가도록 하겠습니다.) 표의 각 칸을 클릭했을 때, 그 칸의 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 8칸에 대해 몇 개의 지뢰가 있는지 0에서 8 사이의 숫자로 클릭한 칸에 표시가 됩니다. 만약, 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정이기 때문에 해당 8방향의 칸도 자동으로 숫자를 표시해줍니다. 즉, 클릭한 칸..
-
SW Expert Academy D4 문제 풀이 (1)알고리즘 2023. 7. 4. 16:42
7465. 창용 마을 무리의 개수 N명의 사람에 대해서 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면 이러한 사람들을 모두 다 묶어서 하나의 무리라고 합니다. 서로를 알고 있는 사람의 관계가 주어질 경우 해당 마을의 무리의 개수를 구하는 문제입니다. 이 문제는 각 노드마다 부모 노드를 지정해주고, 같은 부모 노드를 가리키는 노드들은 같은 무리로 지칭하는 유니온 파인드(Union-Find)를 활용하여 문제를 풀었습니다. parent[N+1] 배열의 모든 원소를 자신의 인덱스로 지정해줍니다. int[] parent = new int[N+1]; for(int i=0;i