Hello, Freakin world!

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..

힙은 특정한 규칙을 만족하도록 구성된 이진 트리입니다. 이를 사용하면 최대[최소] 원소들을 log(N)의 복잡도로 찾아낼 수 있습니다. 규칙 - 힙의 대소 관계 - 힙의 모양 규칙 힙의 대소 관계 힙의 대소 관계는 부모 자식 관계에만 적용됩니다. 형제 간의 대소 관계는 신경쓰지 않습니다. 이 규칙으로 인해 항상 최대[최소] 원소가 루트에 위치하기 때문에 빨리 찾아낼 수 있습니다. 힙의 모양 규칙 모양 규칙에는 두 가지가 있습니다 1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. 2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다. 이 두 가지의 모양 규칙이 만족하면 노드의 개수만으로 트리의 모양이 정해지기 때문에 1차원 배열로 트리를 표현할 수 있습니다..

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 이 문제도 제겐 약간 까다로운 구현 문제에 속했습니다. 시간이 많다면 푸는데 무리는 없겠지만, 짧은 시간 내에 풀기는 힘들수도 있겠다는 생각이 들었습니다. 문제 풀이 문제에서는 초기 상태의 주사위의 면마다 번호가 매겨져 있습니다. 이 문제를 풀기 위한 핵심은 바닥에 위치한 주사위 면을 계속 추적하는 것이 핵심입니다. 어떻게 추적하느냐? 주사위의 ..