본문 바로가기

알고리즘 문제 풀이89

[백준 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.

[백준 10808] 알파벳 개수 문제 출처 : https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 어려운 문제가 아니지만 방법을 모르면 귀찮은 문제라 할 수 있습니다. a부터 z까지 해당 문자가 나타날 때 1씩 더해주면 됩니다. 하지만 이렇게 문제를 푼다면 a부터 z까지 26개의 변수를 만들고, 26개의 비교문을 만들어야 합니다. 이럴 때 사용하는 방법이 앞선 포스트에서 배웠던 ord를 이용하여 문자를 숫자로 바꿔주는 방법 입니다. 문자를 숫자로 바꿔서 무엇을 할 수 있을까요? 바로 리스트의 인덱스로 사용하는 것입니다. 문제 이해하기 문자 a를 숫자 0으로 바꿔줄.. 2023. 11. 23.

[백준 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.

[백준 9465] 스티커 문제 출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 간단한 DP 문제 입니다. DP에 대해 잘 모른다면 어렵게 느껴질 수 있습니다. 스티커의 품질이 좋지 않기 때문에 어떤 스티커를 떼면 그 스티커의 상, 하, 좌, 우에 있는 스티커는 사용할 수 없습니다. 따라서 왼쪽부터 첫 번째 줄의 스티커를 떼었을 때, 두 번째 줄의 스티커를 떼었을 때, 아무것도 떼지 않았을 때, 이렇게 세가지의 경우를 생각해서 문제를 해결해야 합니다... 2023. 10. 5.

[백준 1976] 여행 가자 문제 출처 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행을 갈 수 있는지, 없는지 확인하는 문제 입니다. 문제를 보면 쉽게 도시들을 DFS를 통해 방문이 가능한지 불가능한지 따지면 해결될 것으로 보입니다. 하지만 이렇게 문제를 풀게 되면 시간초과가 발생할 수 있습니다. 왜냐하면 의도적으로 끝에서 끝으로 이동하는 경로만 입력이 들어온다면 방문하는데 시간이 오래걸릴 수 있습니다. 따라서 이 문제는 DFS가 아니라 유니온 파인드, 즉 분리.. 2023. 10. 4.

[백준 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.

[백준 1725] 히스토그램(세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 히스토그램은 다양한 풀이 방법으로 유명한 문제 입니다. 스택, 분할정복, 세그먼트 트리로 풀 수 있습니다. 여기서는 세그먼트 트리의 다양한 응용에 대해 배우기 위해 세그먼트 트리로 푸는 방법을 알아보겠습니다. 문제 이해하기 문제 풀이를 위한 개념은 이렇습니다. 아래와 같은 히스토그램이 있습니다. 처음부터 끝까지를 모두 포함하는 직사각형은 가장 낮은 높.. 2023. 9. 18.

[백준 28325] 2023 정올 "호숫가의 개미굴" 문제 출처 : https://www.acmicpc.net/problem/28325 28325번: 호숫가의 개미굴 KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 $1$부터 $N$까지의 번호가 붙은 $N$개의 방이 차례대로 원형으로 배치되어 있으며, 모든 $i$ ($1 \le i \le N-1$)에 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제입니다. 이 문제를 풀기 위해서 생각해야 하는 부분을 알아보겠습니다. 쪽방 사용 개미굴에 쪽방이 있다면 쪽방을 이용하는 것이 최선 입니다. 그림과 같이 여러 개미굴이 있는 곳의 일부를 보도록 하겠습니다. 2번 개미굴에 쪽방이 하나 연결되어 있습니다. 쪽방인 4번을 선.. 2023. 9. 15.

[백준 1517] 버블 소트(merge sort로 풀기) 문제 출처 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 이 문제의 이름은 버블 소트이지만 버블 소트로 문제를 풀려고 한다면 시간초과로 문제를 해결할 수 없습니다. 이 문제는 앞에서 배운 Inversion Counting 으로 해결할 수 있습니다. 앞에서 세그먼트 트리로 푸는 방법을 배웠다면 이번에는 merge sort를 사용하여 문제를 풀어보도록 하겠습니다. 세그먼트 트리의 문제점 세그먼트 트리로 풀 수 있지만 머.. 2023. 9. 13.

[백준 2579] 06 정올 초등부 "계단 오르기" 문제 출처 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 2006년 정보올림피아드 시. 도 지역 본선 초등부 4번 문제 입니다. 지금으로 따지면 1차 대회에서 초등부 가장 어려운 문제 였습니다. 지금이라면 2~3번 수준의 문제이지 않나 생각합니다. 시간이 흐르면 흐를수록 문제가 어려워지고 있는것 같습니다. 계단을 오르는 규칙을 지키면서 얻을 수 있는 점수의 최댓값을 구하는 문제 입니다. 이런 유형의 문제는 다이나믹 프로그래밍(DP)로 해결할.. 2023. 9. 6.

[백준 14428] 수열과 쿼리 16 문제 출처 : https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net 세그먼트 트리를 조금 응용한 문제 입니다. 기존에는 리스트의 값을 출력 하였다면 이 문제에서는 해당 인덱스를 출력하는 문제 입니다. 이처럼 세그먼트 트리를 어떤 값을 찾는 것이 아니라 보조적인 수단으로 사용하는 문제가 많이 출제되니 이런 케이스의 문제를 많이 풀어봐야 합니다. 이 문제를 푸는 방법은 .. 2023. 9. 5.

[백준 10972] 다음 순열 문제 출처 : https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net permutations 함수를 사용하면 쉽게 해결 가능한 문제로 보입니다. permutations에 대해 잘 모른다면 다빈치코딩 알고리즘 브루트포스를 확인 바랍니다. 하지만 막상 해결이 쉽지 않습니다. 무작정 해보기 for문을 통해 순열들을 호출해서 입력된 배열과 비교하여 같은 것이 나올 때까지 찾습니다. 같은 것이 나오면 마지막 순열이면 -1을 출력하고, 아니면 다음 순열을 출력하면 됩니다. 하지만 막상 이렇게 풀면 시간초과가 됩니다. 시간.. 2023. 9. 4.

[백준 2517] 2012 정올 고등부 2차 "달리기" 문제 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 이 문제는 2012년 정보 올림피아드 고등부 문제 입니다. 앞에서부터 자신보다 실력이 높은 사람의 수를 세어 자신의 최고 등수를 찾는 문제 입니다. 단순한 문제이지만 입력의 숫자가 많아 문제를 풀기는 단순하지 않습니다. 등수 찾기 맨 첫 번째 선수는 무조건 1등을 할 수 있습니다. 그리고 다음 선수는 첫 번째 선수보다 실력이 높다면 1등, 실력이 낮다면 2등 입니다. 즉 어떤 .. 2023. 8. 31.

[백준 1865] 웜홀 문제 출처 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 웜홀은 시간이 거꾸로 가는 곳입니다. 따라서 최단 경로를 구할 때 음의 가중치를 가진 간선이라 생각하면 됩니다. 이 문제에서는 음의 사이클이 존재하는지 존재하지 않는지 확인하는 문제입니다. 벨만 포드 알고리즘을 사용하여 음의 사이클이 있다면 YES를, 음의 사이클이 없다면 NO를 출력하는 문제입니다. 다빈치코딩 알고리즘에 벨만포드 알고리즘을 설명해 놓았습니다. 벨만포드 .. 2023. 8. 30.

[백준 15791] 세진이의 미팅 문제 출처 : https://www.acmicpc.net/problem/15791 15791번: 세진이의 미팅 모태 솔로인 세진이는 이번에는 꼭 여자친구를 사귀어야겠다는 마음으로 형진이가 주최한 미팅에 참석하게 된다. 하지만 안타깝게도 컴퓨터공학과는 남초학과이기 때문에 항상 남자의 수가 여 www.acmicpc.net 이 문제는 결국 남자와 여자가 짝이 되는 모든 조합의 개수를 구하는 문제 입니다. 조합의 개수를 구하기 위해서는 다빈치코딩 알고리즘 조합의 개수에 설명하였습니다. 따라서 이 문제는 결국 아래 식의 값만 구하면 됩니다. $$ _nC_m = \frac{n * (n-1) * (n-2)... (n-m+1)}{m * (m-1) *(m-2) *... * 2 * 1} $$ 숫자가 너무 커지는 것을 방지.. 2023. 8. 28.

[백준 7812] 중앙 트리(파이썬) 문제 출처 : https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 트리 DP의 문제 입니다. 트리와 DP를 합친 문제로 복잡하게 느껴질 수 있지만 하나하나 해결해나가면 문제를 풀 수 있습니다. 이 문제를 풀기 위해서는 모든 정점들의 거리를 계산해야 합니다. 중앙 정점이 어디가 될지 모르기 때문입니다. 무작정 문제를 푼다면 다음과 같이 진행 하면 됩니다. 먼저 A를 중앙 정점으로하여 모든 정점까지의 거리를 구해줍니다. A-B =.. 2023. 8. 28.

[백준 11729] 하노이 탑 이동 순서(파이썬) 문제 출처 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 하노이 탑은 프랑스 수학자 에두아르 뤼카(Edouard Lucas)가 발표한 게임 입니다. 왼쪽의 읬는 원판을 오른쪽 원판으로 이동시켜야 합니다. 이 때 다음의 규칙이 적용되어야 .. 2023. 8. 24.

[백준 28219] 2023 정올 1차 주유소 문제 출처 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇 www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 1차 중등부 3번, 고등부 2번 문제 입니다. 문제 이해하기 N개의 마을이 있는데 도로가 N - 1개가 있습니다. 정점의 갯수보다 간선의 갯수가 1개 적다면 트리 모형이 아닌가 고민해봐야 합니다. 여기에 임의의 두 마을에 대해 두 마을을 잇는 경로가 정확히 하나 존재한다고 합니다. 이 말은 트리 형태의 마을이.. 2023. 8. 23.

[백준 1655] 가운데를 말해요 문제 출처 : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 활용한 재미있는 문제입니다. 기초 알고리즘을 소개하는 다빈치 코딩 알고리즘(https://wikidocs.net/book/10280)에 등록하기에는 고난이도 문제라 판단되어 블로그에 등록합니다. 데이터가 입력될 때마다 배열의 중간 값을 찾는 문제 입니다. 배열을 만들어 정렬된 위치에 데이터를 넣는다면 중간값은 쉽게 찾을 수 있습니다. 하지만 배열이 커지.. 2023. 8. 22.

[백준 28326] 2023 정올 고기파티 문제 출처 : https://www.acmicpc.net/problem/28326 28326번: 고기 파티 오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 $N$개 놓여 있다. 그릴을 $10^9$ 의 길이를 가진 선분이라고 하고, 그릴의 왼쪽 끝을 좌표 $0$, 오른쪽 www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 2차 초등부 4번, 중등부 3번 문제 입니다. 문제의 이해 먼저 문제를 이해하도록 해보겠습니다. 첫 번째 예제를 함께 보면서 무엇을 해야하는지 알아보겠습니다. 이와같이 그릴에 고기가 쌓여 있습니다. 여기서 왼쪽 오른쪽에 꼬치를 꽂고 가져갑니다. 가져간 고기들의 맛의 합을 구하는 문제 입니다. 이 때 꼬치 양쪽 모두에 꽂힌 고기만.. 2023. 8. 21.

[백준 25402] 2022 정올 트리와 쿼리 2022년도 정보올림피아드 2차 데회에서 초등부, 중등부, 고등부 모두 나왔던 문제입니다. 그럼 같이 풀어보도록 하겠습니다. 문제의 예제를 살펴 보겠습니다. 아래와 같이 연결 되어 있는데 S = {1, 2, 3, 4, 5, 6} 입니다. 7만 연결이 안되어 있는 상태 입니다. 이것을 아래와 같이 표현할 수 있습니다. 연결되어 있는 노드들을 확인해보면 다음과 같습니다. (1 - 2), (1 - 3), (1 -5), (2 - 3), (2 - 5), (3 - 5), (4 - 6) 이렇게 7개가 연결 되어있고, 연결강도가 7임을 확인할 수 있습니다. 즉 각 노드들이 연결 되어 있는 노드들의 갯수를 확인하는 것이 이 문제 입니다. 모두 구해보기 가장 쉽게 생각하면 S에 포함된 노드들이 각각 연결되어 있는지 확인하.. 2023. 8. 18.

[백준 22344] 2021 정올 그래프 균형 맞추기 문제 출처 : https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 이 문제는 2021년 정보올림피아드 2차 초등부, 고등부 문제 입니다. 초등부 문제이지만 고등부에서도 출제된 문제인 만큼 쉽지 않은 문제 입니다. 문제 자체를 이해하는건 어렵지 않습니다. 간선의 가중치가 있고, 간선과 이어진 두 정점의 합이 간선의 가중치가 되면 됩니다. 예제 입력을 보면서 이해해 보겠습니다. 정점 1, 2, 3을 값과의 혼란을 피하기 위해 A, B, .. 2023. 8. 16.

[백준 21762] 2021 정올 공통 부분 수열 확장 문제 출처 : https://www.acmicpc.net/problem/21762 21762번: 공통 부분 수열 확장 어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab는 $X$ = ababca의 부분수열이지만, $Y$ = cbabba의 부분수열은 아니다. 두 개의 수열이 주 www.acmicpc.net 이 문제는 2021년 정보올림피아드 1차 고등부 문제 입니다. 두 개의 수열 X, Y의 부분수열 W를 확장 가능한지, 불가능한지 확인 하는 프로그램을 작성하는 것입니다. 예제 입력에 있는 X, Y, W를 살펴 보겠습니다. X = ababca Y = cbabba W = baa X, Y에 W는 공통부분수열이기 때문에 무조건 존재합니다. 이 부분수.. 2023. 8. 15.

이전 1 2 3 다음

티스토리툴바