boj

    백준 14500 / 테트로미노 / Brute Force / JAVA / 골드 5

    오랜만에 백준 문제를 풀었다. Brute Force 부터 유형별로 차근차근 풀어보려 한다. 이 문제는 찐 Brute Force 문제이다. Brute Force는 하나하나 직접 다 해보는 방법을 말한다. 일반적으로 이 방법은 시간과 공간을 초과하기 때문에 만능은 아니지만.. 구현 방법이 떠오르지 않을 때는 가장 먼저 시도해 보면 좋은 방법이기도 하다. 이 문제는 5개의 테트로미노를 뒤집고 돌려서 종이에 놓았을 때 차지하는 4칸의 합을 가능한 경우 모두 구해준 뒤 가장 큰 값을 출력하면 된다. 테트로미노는 5개이지만 실제로 우리가 고려해야 하는 테트로미노는 다음과 같이 총 19개가 된다. 그리고 이 19개 각각에 대해 해당 종이(M*N)를 전부 돌면서 발생할 수 있는 모든 경우를 다 탐색해 주어야 한다. 이..

    백준 3012 / 올바른 괄호 문자열 / DP, 분할 탐색 / JAVA / 플레티넘 3

    오늘은 백준 3012번 문제를 풀어보려고 한다. 이 문제는 07/08 크로아티아 정보올림피아드 기출문제이다. https://www.acmicpc.net/problem/3012 3012번: 올바른 괄호 문자열 예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{}) www.acmicpc.net 크로아티아 정보올림피아드 기출 문제여서 그런지 문제에 대한 아이디어가 쉽게 떠오르지는 않았던 것 같다. (난이도도 심지어 플레티넘 3 ㄷㄷ...) 처음에는 ? 각각에 들어갈 수 있는 문자 "{", "[", "(" 등을 찾아서 경우의 수를 생각해 주어야 하나? 라고도 떠올려 봤는데 너무 생각해 주어야 할 케이스가 많았고 이 방법은 맞지 않다는 것을 깨달았다. 결국 DP를 통해 한..

    백준 2146 / 다리 만들기 / BFS / JAVA / 골드 3

    오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.https://www.acmicpc.net/problem/21462146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.net 이 문제는 엄청 어렵게 느껴지진 않았다. BFS를 익숙하게 쓸 수 있으면 큰 문제 없이 풀 수 있는 문제로 보인다. 다만 BFS를 여러 차례 써야 하는 풀이가 있어서 조금 복잡하게 느껴질 수도 있을 것 같다.BFS에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다..

    백준 1701 / Cubeditor / 문자열, KMP / JAVA

    오늘 살펴볼 문제는 백준 1701 문제이다. https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net 이 문제는 문자열 처리 관련된 유형으로 KMP 알고리즘을 사용하여 문제를 풀어야 시간 내에 맞힐 수 있다. ACM-ICPC 서울 리지널 기출문제이며, 난이도는 골드 2이다. 쉬운 문제는 아니지만 KMP 알고리즘에 대한 이해가 있다면 아이디어를 떠올리는데 도움을 받을 수 있을 것이다. 먼저 문제를 풀기 앞서서 K..

    백준 1202 / 보석 도둑 / 그리디, 우선순위 큐 / JAVA

    오늘 살펴볼 문제는 백준 1202번 문제이다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제이다. 각각의 주머니에 대해서 넣을 수 있는 최대 가격의 보석을 적절하게 넣어주면 풀 수 있는 문제이다. 처음에 내가 했던 접근은 다음과 같다. 보석을 1. 가격이 비싼 순으로 2. 같은 가격이면 무게가 가벼운 순으로 정렬되는 PriortyQueue를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한..

    백준 1507 / 플로이드 와셜(Floyd Warshall) 알고리즘 / JAVA

    이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..

    백준 2352 / LIS(최장 증가 수열), DP / JAVA

    오늘은 백준 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 / LCA 알고리즘, DP, DFS / JAVA

    오늘 살펴볼 문제는 백준 3176번 '도로 네트워크' 라는 문제이다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이 문제는 꽤 어렵다. https://solved.ac/ 라는 알고리즘 문제 난이도 측정 사이트에서는 이 문제를 플레티넘 4 레벨로 분류했다. 플레티넘 레벨은 상당수가 쉽게 해결책을 찾기 어려운 고난이도 문제이다.(나에게는) 이 문제도 그래서 사실 풀다가 다른 사람의 소스를 어느 정도 참고하였고, 천천히 상세하게 풀이를 정리..