Hello, Freakin world!

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 퀸을 놓을 때 위치 정보를 스택에 저장했었다. 백트래킹은 보통 재귀호출 이후에 상태정보를 복구해야 되기 때문에 이를 pop 메서드를 이용해 편하게 구현하기 위함이었다. 그런데 자꾸 시간초과가 나길래 다른 코드들도 훑어봤지만 코드 패턴은 비슷했다. 도대체 영문을 알 수가 없었는데, Stack의 순회 성능 때문이었다. Stack 역시 List 인터페이스를 구현하고 있기 때문에 그러려니 하고 사용했는데 ArrayList에 ..

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 디버깅하는데 정말 하루 꼬박 걸렸던 문제였습니다. 문제를 풀면서 테스트의 중요성을 다시금 느꼈습니다. 특히 구현 문제에서는 더욱더. 구현 문제의 경우 알고리즘의 난이도 자체가 높다기보다 복잡도가 올라가면서 나타나는 실수들 때문에 발목을 잡히기 쉽습니다. 적절하게 메서드로 분리하고 메서드마다 테스트를 착실히 하는게 중요하다고 느껴졌습니다. 저도 테스트 메서드를 작성하고 나서야 짧은 시..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 재귀를 이용한 완전 탐색도 통과할 수 있습니다. 입력이 최대 15이므로 2^15가 32768이기 때문에 충분히 통과할 수 있습니다. dp와 완전탐색 각각의 방식이 이 문제에서는 별다른 속도 차이를 보이지 않았습니다. 문제가 단순해서인지 결국 DP를 이용해 푼 방식이 재귀를 이용한 완전탐색을 그저 for문으로 바꾼 것일 뿐이었는데 DP의 정의에 대해 다시 한번 생각해보게 되네요. DP라는게 그저 for문을 이용한 바텀업 방식의 완전탐색일 뿐인 아니지 않나? 라는 생각이 들었습니다. DP의 최적 부분 구조를 찾는데 항상 애를 먹었는데, ..

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 시계, 반시계를 헤깔려서 한참 헤맸다. 후... 구현을 좀 더 직관적으로 하기 위해서 톱니바퀴를 Gear라는 클래스로 표현했다. 기어 개수가 몇개 안되게 때문에 관계를 설정해주, 해당 톱니 바퀴를 돌리면 다른 톱니 바퀴가 돌아가도록 dfs로 구현했다. ... /* 백준 14891번 - 톱니바퀴 https://www.acmicpc.net/problem/14891 */ public class Main { ..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 꽤 까다로운 구현 문제였다. 생각보다 훨씬 신경써줘야 할 것들이 많았다. 풀이 방법은 1. 기울이는 방향에 따라 다른 공은 신경쓰지 않고 벽이나 구멍이 나타날때까지 이동시킨다. 2. 겹치는 경우 이전 위치들과 비교해 위치를 수정해준다. 3. 정리된 위치들을 재귀함수로 넘겨서 다시 1로 돌아간다. 재귀함수가 리턴되면 이동시킨 위치들을 다시 원상복귀 해줘야 한다.(..

www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 단순히 정렬해서 풀 수가 없었기 때문에, 이것저것 찾아보다가 Quick select라는 알고리즘을 발견하게 됐습니다. 뭐 그리 대단한건 아니고 퀵 소트에 사용된 연산을 약간 응용한 버전입니다. 퀵 소트에서 피봇이 정해지면 피봇의 값을 기준으로 왼쪽에는 그보다 작은 값, 오른쪽에는 그보다 큰 값이 오도록 배열의 값을 수정하는 연산이 있습니다. 자세한 건 퀵 소트 관련글들을 참고해주세용. (링크 - 퀵 소트 참고글) 중요한 점은 한번의 연산이 끝날 때마다 피봇의 위치..

www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. �� www.acmicpc.net 해싱 자료구조를 이용하는 문제입니다. 자바에서 지원하는 Hash 자료구조를 사용할 경우, 자료구조에 저장되는 커스텀 객체는 hashcode(), equals() 를 필수로 오버라이딩 해야합니다. String의 경우 이미 구현되어 있기 때문에 그대로 사용하면 됩니다. 문제 해결 방법은 집합 A,B 중 하나를 골라 모두 해시 자료 구조에 저장합니다. 그리고 다른 집합의 원소들이 해시 자료 구조에 포함되어 있..

www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 미래의 나에게 dfs 함수의 여러 패턴들에 익숙해지도록. 아래의 dfs 함수의 구현에서 종결 조건이 어떻게 구현되는지, int area의 초기값이 왜 1인지, area = area + dfs(), area = dfs() + 1 등이 어떻게 다른지 눈 여겨보기 바람 ... public class Main { static int n, m, k; static int[][] board; static..

www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net import java.io.*; import java.util.ArrayList; import java.util.List; /* 백준 11279번 - 최대 힙 https://www.acmicpc.net/problem/11279 */ public class Main { static int n; static List heap = new ArrayList(); public static void m..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net import java.io.*; import java.util.ArrayList; /* 백준 1927번 - 최소 힙 https://www.acmicpc.net/problem/1927 */ public class Main { static int n; static ArrayList heap = new ArrayList(); public static void main(String[] args) thr..