[SWEA] 19189 순열의 아름다움
2024. 1. 22. 21:03
Algorithm/DP
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYzIcBsq_agDFAQ9&categoryId=AYzIcBsq_agDFAQ9&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 접근 여러 가지 접근이 있는데 필자가 접근한 단계로 차근차근 진행해 보도록 하겠다. BruteForce 구현 모든 경우의 수를 구해야 하는데... 문제를 보면 $1 \leq N \leq 250000$ 이다. 우리가 찾는 아름다운 쌍을 찾기 위해서는 먼저 $250000!$ 개의 행들을 훑어야 하는데 당연히 시..
[BOJ] 13265 색칠하기
2024. 1. 22. 19:54
Algorithm/BFS, DFS
문제 https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 접근 예제를 그래프로 그려서 확인해 보자. 각 노드를 R, G로 색칠해야 한다고 하자. 1번을 R로 색칠하면 문제의 조건에 의해 2, 3이 G로 색칠되어야 한다. 그런데 2번과 3번도 연결되어 있으므로 서로 다른 색이 되어야 하는데 G로 동일하므로 해당 그림은 두 가지 색으로 색칠할 수 없다. 이를 확인하는 방법은 BFS를 사용하여 구현할 수 있다. 시작 노드를 하나의 색으로 정해 칠한 뒤, 자신과 인접한 노드들..
[BOJ] 14629 숫자 조각
2024. 1. 22. 19:44
Algorithm/BFS, DFS
문제 https://www.acmicpc.net/problem/14629 14629번: 숫자 조각 곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫 www.acmicpc.net 접근 기본적인 백트레킹(DFS) 문제 N이 1,000,000,000,000 까지로 매우 크다. 그런데 생각해보면 0부터 9까지 만들 수 있는 것은 9자리로 한정되고 그마져도 9876543210 을 초과하는 순간 답은 9876543210으로 고정된다. 그 이외에는 0부터 9까지를 사용하도록 DFS를 만들면서 만들어진 수가 $N$과 얼마나 차이가 나는지를 확인하고 갱신해주면 해결된다. 정답 ..
[백준][BOJ 2343] - 기타 레슨
2023. 10. 10. 19:41
Algorithm/BinarySearch
문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 접근 나이브한 접근법으로는 블루레이의 크기를 1씩 올려가며 몇 개의 블루레이 디스크가 나올 수 있는지를 확인하는 것이다. 1씩 증가시켜 확인할 때 M개의 블루레이 디스크로 나뉘어질 수 있다면 해당 크기를 반환하고 종료하는 코드를 구현하면 될 것이다. 하지만 해당 방식을 사용하면 매우 비효율적일 수 있다. 당장 강의의 수가 10만까지 올라갈 수 있고, 각 강의의 길이가 1만분까지로 되어 있을 때..
[백준][BOJ 2257] - 화학식량
2023. 10. 9. 16:19
Algorithm/DataStructure
문제 https://www.acmicpc.net/problem/2257 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net 문제 접근 문제를 보면 다음과 같은 특징을 가진다. 먼저 숫자가 들어갈 경우, 직전의 화학식량 * 숫자 로 값을 계산해야 한다. 괄호가 들어간 경우, 괄호 내부의 화학식량을 우선해서 계산해야 한다. 예를 들면 다음과 같다. $CH(CO2H)3$ 을 보자 C, H는 각각 12, 1로 저장된다. 괄호가 열려 있으므로 괄호가 닫힐 때 까지의 화학식량을 계산해야 한다. $CO2H$는 O 뒤에 2가 존재하므로 C = 12, O2..
[백준][BOJ 12789] - 도키도키 간식드리미
2023. 10. 7. 15:01
Algorithm/DataStructure
문제 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 접근 따로 뺄 수 있는 대기열이 존재하고 이 대기열의 구조는 먼저 들어간 사람이 가장 마지막으로 나오는 구조이다. 따라서 LIFO의 특성을 가진 stack을 사용하여 이 대기열을 만들 수 있다. 일반적인 줄의 경우 대기열이기 때문에 queue로 모델링할 수 있다. 문제를 해결하는데 있어 가장 핵심적인 로직은 현재 간식을 받을 번호표와 지금 줄의 맨 앞에 서 있는 사람의 번호표가 서로 ..
[백준][BOJ 2805] - 나무 자르기
2023. 10. 5. 22:26
Algorithm/BinarySearch
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 접근 $N$과 $M$이 매우 크기 때문에 일반적인 완전탐색 알고리즘으로는 해결할 수 없다. 따라서 다른 방식을 찾아야 한다. 적어도 $O(logN)$이 되어야 할 것이다. 적어도 M미터의 나무를 가져가야 하는데 목재 절단기의 높이 $H$를 이분 탐색으로 확인할 수 있다. 가져가려하는 나무의 길이 M은 모든 나무의 높이 합까지 될 수 있기 때문에 절..
[백준][BOJ 17266] - 어두운 굴다리
2023. 10. 5. 21:38
Algorithm/BinarySearch
문제 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 문제 접근 나이브한 풀이로는 완전 탐색을 사용하는 방법이 있다. 가장 심플한 풀이 방식으로 가로등의 높이로 있을 수 있는 모든 범위($1 \leq h \leq N$)에 대하여 길의 모든 부분이 밝혀질 수 있는지를 체크하는 방법을 사용하는 것이다. 하지만 해당 방식을 사용하면 적어도 $O(N^2)$의 시간이 걸리기 때문에 $h$가 10만까지 올라가는 특성 상 시간 초과가 나게 될 것이다. 다른 방..
[백준][BOJ 5883] - 아이폰 9S
2023. 10. 5. 16:40
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/5883 5883번: 아이폰 9S 사람 9명이 줄을 서있고 각 사람이 원하는 용량의 크기는 2, 7, 3, 7, 7, 3, 7, 5, 7 이다. 용량 3을 원하는 사람을 줄에서 빼버리면, 줄은 2, 7, 7, 7, 7, 5, 7가 되고, 7을 원하는 사람이 4명이 연속된 구간이 www.acmicpc.net 문제 접근 특정 용량을 원하는 사람을 줄에서 제거했을 때 같은 용량을 원하는 연속된 사람의 길이의 최대값을 구하는 문제 모든 경우의 수를 탐색해야 한다. 예를 들어 0 0 1 2 0 0 3 0 3 3 이라는 입력이 있을 때 제거하는 경우의 수는 각각 0, 1, 2, 3이다. 이 모두를 탐색하면 된다. 즉 종류를 한번 카운팅해야 한다는 것이며..
[백준][BOJ 3758] - KCPC
2023. 10. 5. 15:58
Algorithm/Simulation, Implement
문제 https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 문제 접근 여러 조건에 따라 데이터를 정렬하는 문제 데이터만 잘 저장해 놓으면 나머지는 조건에 따라 정렬식을 구현하면 되는 문제였다. 필자의 경우 람다를 활용하여 정렬식을 구현하였다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; pu..