불광천 IT 외노자

IT/Algorithm

[Java] 알고리즘 PS에 적용할만한 짱짱빠른 I/O

초심자들에겐 Scanner/System.out.println, 조금 더 나아가면 BufferedReader/Writer를 많이 쓰실 것입니다. 실제로 백준, 삼성 코딩테스트 수준에선 BufferedReader/Writer로 충분합니다만, 백준에서 풀이 시간을 적은 노력으로 단축하고자 한다면 아래 링크를 참조하시기 바랍니다. https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/?ref=rp Fast I/O in Java in Competitive Programming - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought..

IT/Algorithm

[BOJ 9375] 패션왕 신해빈

서론 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 어려운 문제는 아니었지만 갯수를 세는 아이디어가 괜찮아서 올려봅니다. 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 ..

IT/Algorithm

[BOJ 1092] 배

서론 그리디 문제가 너무 재밌습니다. 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다..

IT/Algorithm

[BOJ 17839] Baba is Rabbit

서론 사랑하는 나의 모교 UNIST에서 개최한 첫 알고리즘 대회의 문제다. 나는 2회 대회에 참가했는데, 알고리즘 준비가 전혀 안되어 있던 상태였기 때문에 허겁지겁 1회 대회 문제를 풀어보았던 기억이 있는데... 그 때는 이 문제조차 어렵게 느껴졌는데 2달 정도 공부하고 나서는 편하게 느껴졌다. 전형적인 solved.ac 실버 수준의 그래프 탐색 문제로, 이 문제를 잘 풀수 있다면 대다수의 실버 그래프 탐색 문제는 풀 수가 있을 것이다. 17839번: Baba is Rabbit Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다. www.acmicpc.net 문제 원이는 요즘 유행하는 게임을 하고 있다. 이..

IT/Algorithm

[BJ 3344] N-Queens

서론 3344번: N-Queen 첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다. www.acmicpc.net N-Queens의 매운 맛 문제가 있길래 시도해봤는데 시간초과로 박살이 났다. 인풋으로 99999가 들어가는데 시간 초과가 나는건 자명했는데 아무 생각없이 정답률을 까먹었다. 대체 어떻게 푸는건가 싶어서 구글링해봤는데, 이 문제에만 특별히 적용되는 알고리즘이 있었다. 태그에 백트래킹이 붙어있지 않을 때 알아봤었어야 했는데... Eight queens puzzle - Wikipedia The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so..

IT/Algorithm

[BJ 18768] 팀 배정

서론 최근에 그리디 알고리즘 문제를 집중적으로 풀어보고 있습니다. 그리디 알고리즘을 사용하는 문제라고 파악이 되면, 어떤 기준을 가지고 최적의 선택을 해야할지 고민해 보아야 합니다. 이 문제는 쉽게 풀 수 있을 것 처럼 보이는 문제지만 기준을 정교하게 세워야 통과할 수 있는 문제입니다. www.acmicpc.net/problem/18768 18768번: 팀 배정 각 테스트 케이스 마다 능력치 합의 최댓값을 한 줄에 하나씩 출력한다. www.acmicpc.net [팀 배정] 문제 사내 해커톤 대회에서 팀 배틀 보안 해커톤을 하기로 했다. 대회는 주어진 보안 서버를 공격(해킹)하는 역할의 팀 A와 방어(보안)하는 역할의 팀 B로 나누어서 진행한다. 참가자는 총 n명이고, 각 참가자의 공격 능력과 방어 능력은..

IT/Algorithm

[BOJ 1256] 사전 (풀이 미완성, DP사용 X)

서론 DP 태그가 떡하니 붙어있는데 DP 복습을 안하고 풀어서 DP로 풀 아이디어가 없었다. 대신에 수학적인 개념을 이용해 풀어보았다. 설명이 잘 될진 모르겠다. 거지같은 코드에 괴상한 아이디어다. 2 2 x 케이스 a는 0으로, z는 1로 보기로 했다. 그래서 a와 z의 갯수를 충족하는 이진수를 작은 순부터 나열하기로 했다. 0011 // index = 0 0101 0110 1001 1010 1100 // index = 5 처음 나오는 1의 위치를 x라고 두면, 기준으로 0을 배열할 수 있는 경우의 수가 2C0이다. 0

IT/Algorithm

[BOJ 3078] 좋은 친구

문제 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net [좋은 친구] 상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다. 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아. ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해..

IT/Algorithm

[BOJ 4884] FIFA 월드컵

서론 백준 4884번 FIFA 월드컵은 solved.ac 기준 Bronze 1 문제임에도 불구하고, 정답자가 30%밖에 되지 않습니다. 문제 자체의 난이도는 높지 않으나, 간과하기 쉬운 부분이 있어서 많이 틀리지 않았을까 생각합니다. 4884번: FIFA 월드컵 FIFA는 월드컵의 대회 형식을 약간 수정하려고 한다. 현재, 월드컵은 32개팀이 참가하며, 2개의 라운드로 이루어져 있다. 첫 번째 라운드는 조별 리그이고, 32개팀은 8개의 조에 배정된다. 각 팀은 www.acmicpc.net [FIFA 월드컵 문제] FIFA는 월드컵의 대회 형식을 약간 수정하려고 한다. 현재, 월드컵은 32개팀이 참가하며, 2개의 라운드로 이루어져 있다. 첫 번째 라운드는 조별 리그이고, 32개팀은 8개의 조에 배정된다. ..