오늘도 개발로그

알고리즘/문제풀이 (55)

[백준 1564번] 팩토리얼5: 정식 풀이

문제 링크https://www.acmicpc.net/problem/1564 문제 요약N이 주어졌을 때, N!의 마지막 0이 아닌 5자리 수를 출력하는 문제이다. 예를 들어, N이 10인 경우 10!은 3628800이며, 마지막 0이 아닌 5자리 숫자는 36288이 된다. 문제 풀이BigInt와 같은 큰 수 자료형을 사용해 팩토리얼을 직접 계산하기 위해서는 많은 시간과 공간 복잡도가 필요하다. 따라서 더 효율적인 방법이 필요하다. 얼핏 보면 팩토리얼의 마지막 다섯 자리만 유지하면 될 것 같지만, 팩토리얼 값의 끝에 붙는 0, 즉 트레일링 제로를 제거하고 출력해야 하기 때문에 단순히 마지막 다섯 자리만 유지하는 것으로는 문제를 해결할 수 없다. 핵심은 트레일링 제로가 언제 생기는..

더 읽기

[백준 21925번] 짝수 팰린드롬

문제 링크https://www.acmicpc.net/problem/21925 문제 요약길이가 인 수열이 가 주어진다. 수열 를 길이가 짝수인 부분 수열들로 나눌 때, 짝수 팰린드롬을 최대한 많이 만드는 문제이다. 문제 풀이이 문제는 부분 수열의 팰린드롬 여부를 미리 계산하는 전처리와 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다. 1. 부분 수열의 팰린드롬 여부를 미리 계산하기부분 수열이 팰린드롬인지 여부를 나타내기 위해, boolean 타입의 2차원 배열 isPalindrome을 사용한다. 이 배열에서 isPalindrome[j][i]는 인덱스 부터 까지의 부분 수열이 팰린드롬인지를 나타낸다. 만약 가능한 모든 와 \..

더 읽기

[백준 20040번] 사이클 게임

문제 링크https://www.acmicpc.net/problem/20040 문제 요약개의 점이 있다. 이때 서로 다른 두 개의 점을 연결하는 선분들이 차례대로 주어졌을 때, 사이클이 생기는 순간을 찾는 문제이다. 문제 풀이각 점을 노드로, 선분을 간선으로 하는 무향 그래프로 모델링을 한다. 새로운 간선을 추가할 때마다 두 노드가 같은 집합에 속해 있는지 확인한다. 만약 같은 집합에 속해 있다면, 해당 간선을 추가하면 사이클이 형성되는 것이다. 반대로, 같은 집합에 속해있지 않으면 두 집합을 합쳐서 하나의 집합으로 만든다. 유니온 파인드(Union Find) 자료구조를 이용해 집합을 효율적으로 관리할 수 있으며, 제한시간 내에 문제를 해결할 수 있다. 소스 코드더보기더보기#include #inc..

더 읽기

[백준 17216번] 가장 큰 감소 부분 수열

문제 링크https://www.acmicpc.net/problem/17216 문제 요약주어진 수열 에서 합이 가장 큰 감소하는 부분 수열을 찾는 문제이다. 문제 풀이감소하는/증가하는 부분 수열을 찾는 문제는 전형적인 동적 계획법(Dynamic Programming) 문제들 중 하나이다. 이 문제 역시 점화식을 세워 동적 계획법으로 문제를 해결할 수 있다. 점화식을 세우기 전에 DP 배열부터 정의를 해보자. 는 수열 에서 로 끝나는 감소 부분 수열의 합 중에서 가장 큰 값을 저장하는 배열이다. 그다음으로 DP 배열을 초기화한다. 각 원소는 자기 자신만을 포함하는 감소 부분 수열이 될 수 있으므로, 의 초기값을 로 설정한다. 이제..

더 읽기

[백준 22742번] Make Friendships

문제 링크https://www.acmicpc.net/problem/22742 문제 요약이팍이는 파티에서 여러 여자친구를 새롭게 사귀었고, 이들과 데이트 일정을 잡으려고 한다. 이삭이는 한 번에 한 명의 여자친구만 만날 수 있으며, 만날 수 있는 시간은 정해져 있다. 또한 각 여자친구마다 이삭이를 만날 수 있는 시간이 정해져 있다. 이 때 이삭이가 최적의 일정으로 스케줄링을 했을 때 최대한 만날 수 있는 여자친구들의 수를 구하는 문제이다. 문제 풀이이삭이가 사용할 수 있는 시간들을 왼쪽 노드로, 각 여자친구들을 오른쪽 노드로 설정하면 문제를 이분 그래프로 모델링 할 수 있다. 아래 그림은 예제 입력을 이분 그래프로 모델링 한 결과이다. 이제 문제는 이분 그래프에서 최대 매칭을 구하는 문제로 바뀌었고, 이분..

더 읽기

[백준 3632번] Drying

문제 링크https://www.acmicpc.net/problem/3632 문제 요약개의 빨래와 각각의 빨래가 가지고 있는 초기 물의 양이 주어진다. 모든 빨래는 1분마다 물의 양이 1씩 줄어들며, 매 분마다 한 개의 빨래를 선택해 라디에이터에 올릴 수 있다. 라디에이터에 올린 빨래는 물의 양이 1분마다 씩 줄어든다. 모든 빨래의 물의 양이 0이 되는 최소한의 시간을 구하는 문제이다. 문제 풀이만약 분 내에 모든 빨래를 말릴 수 있는 방법이 존재한다면, 분보다 더 큰 시간 내에서도 모든 빨래를 말릴 수 있다. 반대로 분 내에 모든 빨래를 말릴 수 없다면, 분 보다 더 작은 시간 내에 모든 빨래를 말릴 방법은 존재하지 않는다. 이 특성을 이용해 최적화 ..

더 읽기

[백준 17610번] 양팔저울

문제 링크https://www.acmicpc.net/problem/17610 문제 요약이 문제는 서로 다른 무게의 추 개가 주어졌을 때, 양팔저울을 한 번만 사용하여 1부터 주어진 추들의 무게의 합인 사이의 모든 무게 중 측정이 불가능한 무게의 개수를 구하는 문제이다. 문제 풀이이 문제를 해결하기 위해서는 개의 추를 가지고 만들 수 있는 모든 가능한 무게 조합을 고려하는 완전 탐색을 이용할 수 있다. 각 추에 대해 우리는 세 가지 선택을 할 수 있다.추를 사용하지 않는 경우양팔저울의 왼쪽에 올려놓는 경우양팔저울의 오른쪽에 올려놓는 경우각 추를 위와 같은 세 가지 선택지 중 하나로 결정한 후, 양팔저울의 왼쪽과 오른쪽에 놓인 추들의 무게 차이를 계산한다. 이렇게 계산된 모든 ..

더 읽기

[백준 17608번] 막대기

문제 링크https://www.acmicpc.net/problem/17608 문제 요약일렬로 세워진 막대기를 오른쪽에서 바라봤을 때, 보이는 막대기의 수를 구하는 문제이다.  문제 풀이주어진 막대기들을 오른쪽에서 왼쪽으로 하나씩 살펴보는 방법으로 문제를 해결할 수 있다. 오른쪽 끝의 막대기부터 시작해서, 현재까지 본 막대기들 중 가장 높은 것과 현재 막대기의 높이를 비교한다. 만약 현재 막대기의 높이가 지금까지 본 막대기들 중 가장 높은 막대기의 높이보다 크다면, 그 막대기는 오른쪽에서 봤을 때 보이는 막대기이다. 이 과정을 가장 왼쪽에 있는 막대기까지 반복하면, 오른쪽에서 봤을 때 보이는 막대기의 수를 구할 수 있다. 소스 코드더보기더보기#include int n, A[100010];int main(..

더 읽기

[백준 32072번] 트리 뽑아내기

문제 링크https://www.acmicpc.net/problem/32072 문제 요약문제에서 정의한 뽑아내기 연산을 수행할 때마다 루트에 있는 가중치의 값을 출력하는 문제이다. 뽑아내기 연산을 수행할 때는 특별한 경로를 찾아야 하는데, 한 정점에서 이동할 자식을 결정할 때는 직계 자식들만 비교하면 된다는 것에 유의하자. (한 정점의 자손들 중 가장 작은 가중치를 가지는 정점으로 이동하는 경로를 찾아야 하는 것으로 문제를 잘못 이해해 시간을 너무 많이 날렸다...🤦‍♂️) 문제 풀이뽑아내기 연산을 수행한다고 하지 말고, 루트 정점에 있어야 하는 정점들을 순회한다고 접근하면 문제를 조금 더 쉽게 풀 수 있다. 그렇다면 어떤 순서대로 정점을 방문해야 할까? 뽑아내기 연산을 할 때, 특별한 경로에 있는 정점..

더 읽기

[백준 25571번] 지그재그 부분배열

문제 링크https://www.acmicpc.net/problem/25571 문제 요약길이가 인 배열이 주어졌을 때, 만들 수 있는 연속된 부분배열들 중 지그재그인 부분배열의 개수를 찾는 문제이다. 배열이 지그재그라는 뜻은 배열의 원소가 감소와 증가 또는 증가와 감소를 반복하는 배열을 의미한다. 문제 풀이만들 수 있는 모든 부분배열 에 대해서 지그재그인지 검사하면 답을 구할 수 있다. 하지만 이 방법은 시간복잡도가 이라서, 이 10만 일 때 제한시간 내에 문제를 해결하지 못하므로 더 효율적인 풀이가 필요하다. 지그재그 부분배열의 특징을 살펴보면 이 지그재그이고, 가 지그재..

더 읽기

[백준 32070번] 색깔 모으기

문제 링크https://www.acmicpc.net/problem/32070 문제 요약같은 색깔의 공을 하나의 상자에 모으는 데 필요한 최소 이동 횟수를 구하는 문제이다. 각 상자는 최대 두 개의 공을 담을 수 있다. 공을 꺼낼 때는 상자의 위에 있는 공만 꺼낼 수 있으며, 공을 넣을 때는 빈 상자나 같은 색깔의 공이 있는 상자에만 넣을 수 있다. 문제 풀이같은 색깔의 공을 하나의 상자에 모으기 위해 공을 옮기다 보면 연쇄적으로 다른 공들도 움직여야 하는 상황이 발생한다. 이 과정에서 연쇄적으로 움직이는 공들을 추적하다 보면 하나 이상의 싸이클이 만들어지는 것을 발견할 수 있다.위 예시를 보면 1, 2, 3, 4번 공의 싸이클과 5, 6, 7번 공의 사이클은 답을 구하는 과정에서 서로 영향을 끼치지 않..

더 읽기

[백준 32069번] 가로등

문제 링크https://www.acmicpc.net/problem/32069 문제 요약수직선 도로 위해 개의 가로등이 위치해 있다. 각 위치에서 가장 가까운 가로등까지의 거리를 계산하고, 그 거리들을 오름차순으로 정렬한 뒤 앞에서부터 개 출력하는 문제이다. 문제 풀이문제에서는 어두운 정도를 각 위치로부터 가장 가까운 가로등까지의 거리로 정의하고 있다. 그래서 처음에는 각 위치별로 가장 가까운 가로등까지의 거리를 모두 계산해야 한다고 생각할 수 있다. 하지만 도로의 길이 이 최대 까지 될 수 있기 때문에, 모든 위치를 전부 탐색하는 완전탐색은 사실상 불가능하다. 이 문제를 해결하기 위해서는 가로등을 기준으로 생각할 필요가 있다. 각 가로등들을 중심으로 가까..

더 읽기

Copyright © 오늘도 개발로그 All Rights Reserved

Designed by JB FACTORY

티스토리툴바