본문 바로가기
반응형

백준44

[백준 1504] 특정한 최단 경로 문제 출처 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 설명 최단 경로를 구하는 다익스트라 알고리즘 문제 입니다. 다익스트라 알고리즘에 대해서 잘 모른다면 아래 링크를 통해 확인해 보시기 바랍니다. https://wikidocs.net/206944 01. 다익스트라 알고리즘 # 다익스트라 알고리즘 다익스트라 알고리즘(Dijkstra Algorithm)은 그래프에서 최단 경로를 구하는 알고.. 2023. 12. 9.
[백준 11438] LCA 2 문제 출처 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 앞서 풀어보았던 LCA 문제의 심화 버전 입니다. 입력과 출력의 형식이 똑같지만 주어지는 N과 노드의 쌍 M의 수가 늘어나 있습니다. 따라서 기존의 LCA 문제를 푸는 방식으로는 시간초과가 발생합니다. LCA의 풀이 방법을 생각해 보겠습니다. 두 정점의 깊이를 맞춰 준다. 깊이가 같다면 공통 조상이 나올 때까지 하나씩 위로 올라간다. 이 두 가지 방법으로 LCA를 찾아주었습.. 2023. 11. 15.
[백준 24955] 숫자 이어 붙이기 문제 출처 : https://www.acmicpc.net/problem/24955 24955번: 숫자 이어 붙이기 철수는 수를 이어 붙이는 놀이를 좋아한다. 1과 2를 이어 붙이면 12가 되고, 17과 13을 이어 붙이면 1713이 된다. 100과 1000을 이어 붙이면 1001000이 된다. 1과 2를 이어 붙이되, 순서를 반대로 해서 2와 www.acmicpc.net 문제 이해하기 방문한 순서대로 숫자들을 이어 붙여서 출력하는 문제 입니다. 사실 이 문제는 LCA 항목에 있어서 LCA를 연습하려고 풀어본 문제인데 단순한 DFS로 해결되는 문제였습니다. 다만 이 문제에서 신경 쓸 부분은 두가지 입니다. 숫자들 더해주는 것이 아니라 이어 붙이는 것입니다. 답을 숫자가 아닌 문자열로 관리해야 합니다. 숫자.. 2023. 11. 10.
[백준 11812] K진 트리 문제 출처 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 문제 이해하기 최소 공통 조상(LCA)를 찾는 문제 입니다. 다만 일반적인 방법으로 풀 수 없습니다. 왜냐하면 메모리 사용을 최소로 해야 풀리는 문제이기 때문입니다. 그냥 LCA를 푸는 방식으로 풀게되면 메모리 초과를 경험하게 됩니다. 결국 이 문제는 K진 트리의 특성을 이용하여 각 노드의 부모와 깊이를 찾아 해결해야 합.. 2023. 11. 6.
[백준 4195] 친구 네트워크 문제 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 간단한 유니온 파인드 문제 입니다. 기존의 유니온 파인드와 다른 두 가지 때문에 쉽게 문제를 풀 수 없습니다. 그럼 문제점을 파악해보고 문제를 풀어보도록 하겠습니다. 문제점 이 문제의 가장 큰 문제는 노드가 숫자가 아닌 친구 이름이라는 것입니다. 해결할 수 있는 여러가지 방법이 있겠지만 저는 딕셔너리를 이용하여 해결하였습니다. 다음으로 친구가 몇명이 있는지 알아야 합니다... 2023. 10. 13.
[백준 25405] 2022년 정보 올림피아드 2차 "레벨 업" 문제 출처 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 이 문제는 2022년 정보올림피아드 2차 중등부 4번, 고등부 3번 문제로 출제되었습니다. 레벨의 균형을 맞춰가며 올리는 문제 입니다. 매번 트레이닝 할 때마다 레벨이 낮은 K개의 캐릭터의 레벨을 1씩 M번 올리면 해결 되는 간단한 문제 입니다. 문제는 캐릭터가 총 10만이고, K값의 최대값도 10만이며 올려야하는 레벨의 최대값은 10억이라는 것입니다. 따라서 .. 2023. 10. 11.
[백준 11437] LCA 문제 출처 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 가장 기본적인 형태의 LCA 문제 입니다. LCA 알고리즘의 설명은 이전에 게시한 알고리즘 설명으로 대신하겠습니다. 2023.10.06 - [알고리즘 설명] - 최소공통조상(LCA) 최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리.. 2023. 10. 10.
[백준 15686] 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다. 알고리즘 지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루.. 2023. 9. 27.
[백준 12015] 가장 긴 증가하는 부분 수열 2 문제 출처 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1,.. 2023. 9. 20.
반응형

티스토리툴바