Computer Sci./Algorithms

이번 포스팅에서는 킥스타트 2020 Round F에 대한 문제 풀이를 공유하고자 한다. 1. ATM Queue 나는 이 문제를 우선순위 큐를 가지고 풀었다. 배열에 담겨진 각각의 출금액을 A1, A2, A3, ... , An 이라고 했을 때 그 출금액의 인덱스(몇 번째에 출금을 하는지)와 1회 최대 출금액(X)으로 나눈 몫을 가지고 클래스를 만들어서 출금액 몫 오름차순, 그리고 몫이 같을 경우 인덱스 오름차순이 되게 클래스의 기준을 만들어서 우선순위 큐에 넣으면 자동으로 정렬이 되어서 출력된다. 시간복잡도는 O(NlogN) 2. Metal Hervest 이 문제는 그리디 알고리즘으로 풀었다. 추수 기간이 오버랩 되지 않는다고 해서(These time intervals do not overlap) 문제가 ..

이번 포스팅에서는 킥스타트 2020 Round E에 대한 문제 풀이를 공유하고자 한다. 이전 문제풀이 2020 Round D 2020 Round C 2020 Round B 2020 Round A 1. Longest Arithmatic 주어진 배열을 한 번 반복문을 돌면서 가장 긴 등차수열을 찾으면 쉽게 풀 수 있는 문제이다. 시간복잡도는 O(N) 2. High Buildings 이 문제는 전체 빌딩 숫자, 왼쪽에서 Andre가 바라본 건물의 숫자, 오른쪽에서 Sule가 바라본 건물의 숫자, 그리고 두 명이 같이 볼 수 있는 건물의 숫자를 입력받아 각각의 건물들이 가질 수 있는 높이의 예시를 출력하면 되는 문제이다. 만약 가능한 경우가 없으면 "IMPOSSIBLE"을 출력한다. 조금 케이스 분류를 해 주는..

이번 포스팅에서는 킥스타트 2020 Round D에 대한 문제 풀이를 공유하고자 한다. 1. Record Breaker 배열을 반복하면서 조건문을 통해 카운팅을 하면 쉽게 풀 수 있는 문제이다. 시간복잡도는 O(N) 2. Alien Piano 이 문제는 Greedy 알고리즘을 사용해서 풀었다. 먼저 배열을 통해 각각의 note의 pitch를 받아서 채워준다. 이 때 연속해서 같은 값이 나오게 되면 같은 alien piano key를 사용하게 되므로 배열에 넣어주지 않아도 된다. 이렇게 배열을 넣어 주었을 때 만약 다음과 같이 배열이 생겼다고 가정해 보자. 이 때는 연속해서 두 숫자가 같은 경우는 존재하지 않을 것이다. [1, 8, 9, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 3, 5, 7]..

이번 포스팅에서는 킥스타트 2020 Round C에 대한 문제 풀이를 공유하고자 한다. 1. Countdown 간단한 배열 문제이다. 배열의 반복문을 돌면서 주어진 숫자부터 시작되는 카운트 다운이 총 몇 개인지를 세어 주면 된다. 한 번 배열을 순환해서 답을 구할 수 있기 때문에 시간복잡도는 O(N). 2. Stable Wall 그래프 개념을 가지고 풀어야 하는 조금 까다로운 문제이다. 나의 경우 다른 사람의 풀이를 조금 참고하면서 풀었다. 문제를 이해하는 것 부터 쉽지가 않았던 것 같다. 위상 정렬(topological sort)과 DFS를 사용하였다. N개의 폴리노미노(polynomino)가 있고 이것들이 stable한 경우, 즉 각각의 폴리노미노가 바닥에 붙어 있거나, 다른 폴리노미노 위에 올라타 ..

킥스타트 2020 라운드 B 문제 풀이를 해 보도록 한다. 내년 2021 킥스타트나 코드잼을 준비하시는 분들, 또는 알고리즘 공부를 하시는 분들에게 많은 도움이 되길 바란다. 1. Bike Tour 기초적인 탐색 문제이다. 전체 체크포인트 N개를 배열에 저장한 후 처음부터 끝까지 탐색하며 peak가 몇 개인지 파악하면 된다. 시간복잡도는 O(N). import java.io.*; import java.util.*; public class KickStart_2020B_1 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

지금까지 백준만 풀다가 올해 남은 기간동안에는 구글 킥스타트 문제들을 좀 풀어보기로 했다. 구글 킥스타트는 구글에서 매년 개최하는 알고리즘 대회이다. 전 세계의 수만명이 참가하여 코딩 실력을 겨룬다. 1년에 여러 차례 대회가 열리는데(2020년 기준 한 달에 한 번꼴) 매번 대회가 끝나면 등수가 공개되어서, 객관적인 나의 수준도 판단할 수 있다. 매년 조금씩 바뀌지만 올해는 각 라운드당 3시간동안 네 문제를 푸는 형식으로 진행이 되고 있다. 나는 올해 중반부터 시작했고, 처음이다보니 아직 문제를 막 잘 풀지는 못했다. 그래서 2020년에 출제된 기출문제를 하나씩 풀어보면서 연습하고 그 내용을 블로그에 정리해 보려고 한다. 총 4문제 중에 4번 문제는 못 풀었고, 1~3번 문제만 풀어서 이에 대한 간단한 ..

오늘은 백준 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에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다..