오랜만에 백준 문제를 풀었다. Brute Force 부터 유형별로 차근차근 풀어보려 한다. 이 문제는 찐 Brute Force 문제이다. Brute Force는 하나하나 직접 다 해보는 방법을 말한다. 일반적으로 이 방법은 시간과 공간을 초과하기 때문에 만능은 아니지만.. 구현 방법이 떠오르지 않을 때는 가장 먼저 시도해 보면 좋은 방법이기도 하다. 이 문제는 5개의 테트로미노를 뒤집고 돌려서 종이에 놓았을 때 차지하는 4칸의 합을 가능한 경우 모두 구해준 뒤 가장 큰 값을 출력하면 된다. 테트로미노는 5개이지만 실제로 우리가 고려해야 하는 테트로미노는 다음과 같이 총 19개가 된다. 그리고 이 19개 각각에 대해 해당 종이(M*N)를 전부 돌면서 발생할 수 있는 모든 경우를 다 탐색해 주어야 한다. 이..
오늘은 백준 3012번 문제를 풀어보려고 한다. 이 문제는 07/08 크로아티아 정보올림피아드 기출문제이다. https://www.acmicpc.net/problem/3012 3012번: 올바른 괄호 문자열 예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{}) www.acmicpc.net 크로아티아 정보올림피아드 기출 문제여서 그런지 문제에 대한 아이디어가 쉽게 떠오르지는 않았던 것 같다. (난이도도 심지어 플레티넘 3 ㄷㄷ...) 처음에는 ? 각각에 들어갈 수 있는 문자 "{", "[", "(" 등을 찾아서 경우의 수를 생각해 주어야 하나? 라고도 떠올려 봤는데 너무 생각해 주어야 할 케이스가 많았고 이 방법은 맞지 않다는 것을 깨달았다. 결국 DP를 통해 한..
오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.https://www.acmicpc.net/problem/21462146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.net 이 문제는 엄청 어렵게 느껴지진 않았다. BFS를 익숙하게 쓸 수 있으면 큰 문제 없이 풀 수 있는 문제로 보인다. 다만 BFS를 여러 차례 써야 하는 풀이가 있어서 조금 복잡하게 느껴질 수도 있을 것 같다.BFS에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다..
오늘 살펴볼 문제는 백준 1701 문제이다. https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net 이 문제는 문자열 처리 관련된 유형으로 KMP 알고리즘을 사용하여 문제를 풀어야 시간 내에 맞힐 수 있다. ACM-ICPC 서울 리지널 기출문제이며, 난이도는 골드 2이다. 쉬운 문제는 아니지만 KMP 알고리즘에 대한 이해가 있다면 아이디어를 떠올리는데 도움을 받을 수 있을 것이다. 먼저 문제를 풀기 앞서서 K..
오늘 살펴볼 문제는 백준 1202번 문제이다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제이다. 각각의 주머니에 대해서 넣을 수 있는 최대 가격의 보석을 적절하게 넣어주면 풀 수 있는 문제이다. 처음에 내가 했던 접근은 다음과 같다. 보석을 1. 가격이 비싼 순으로 2. 같은 가격이면 무게가 가벼운 순으로 정렬되는 PriortyQueue를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한..
이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..
오늘은 백준 2352번 '반도체 설계' 문제를 보려고 한다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 난이도는 그렇게 어렵지 않았다.(골드 3) 이 문제는 LIS(최장 증가 수열)와 DP로 풀 수 있는 문제이다. 먼저 LIS에 대해서 간단하게 설명을 해 보려고 한다. LIS는 어떤 수열이 주어졌을 때 그 수열의 부분 수열 중에서 가장 길이가 긴 수열을 의미한다. 여러가지 방법으로 이 수열을 구할 수 있겠지만, 가장 일..
오늘 살펴볼 문제는 백준 3176번 '도로 네트워크' 라는 문제이다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이 문제는 꽤 어렵다. https://solved.ac/ 라는 알고리즘 문제 난이도 측정 사이트에서는 이 문제를 플레티넘 4 레벨로 분류했다. 플레티넘 레벨은 상당수가 쉽게 해결책을 찾기 어려운 고난이도 문제이다.(나에게는) 이 문제도 그래서 사실 풀다가 다른 사람의 소스를 어느 정도 참고하였고, 천천히 상세하게 풀이를 정리..
