Hello, Freakin world!

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 다익스트라 알고리즘으로 풀기 전에 DP로 풀 수 있지 않을까? 라고 생각했지만 어렵겠다고 결론을 내렸습니다. 이유는 수빈이가 x-1로도 움직일 수 있기 때문입니다. 점화식은 구해지지만 이 경우 재귀로 풀어야 하는데 시간복잡도가 O(3^n)이 되므로 불가능합니다. 전형적인 다익스트라 알고리즘에 약간 추가로 생각해줘야 할 점이 있습니다. 그래프 노드의 범위를 정해주는 겁니다...

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 이 문제의 핵심은 1의 상황을 2로 바꿔서 풀 수 있다는 걸 이해하는 겁니다. 다익스트라는 단일 시작점을 기준으로 모든 정점 간의 최단 거리를 계산하기 때문에 1번과 경우에 1,2 정점에서 X까지의 최단 거리를 구하려면 1,2 정점 각각에서 최단 거리를 구해야합니다. 이 경우는 비효율적이기 때문에 2번처럼 간선을 역전시켜 1번의 상황을 한번의 다익스트라 알고리즘을 통해서 해결할 ..

no1linux.org/hottips/28242 No1.Linux 팁및 강좌 - [시스템] Alternatives(Update-altenatives)로 하나의 심볼릭 링크로 여러 패키지 관리 하나의 심볼릭 링크로 여러 개의 패키지 관리하기 - update-alternatives 1. 개 요 버전이 각기 다른 패키지에 대해서 동일한 심볼릭 링크를 사용해야 할 경우에 어떻게 해야 할까? 원하는 버전으로 � no1linux.org

freestrokes.tistory.com/61 Ubuntu 자바(JAVA) 설치하기 Ubuntu JAVA 설치 및 환경 변수 설정 JAVA 7 버전을 Ubuntu에 설치하고 환경 변수를 설정하는 방법을 알아보겠습니다. JDK Download 아래 경로에서 JDK 설치 파일(tar.gz)을 다운로드 받습니다. http://www.oracl.. freestrokes.tistory.com

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 적용하기 전에 그래프 모델링이 필요합니다. 하나의 칸을 하나의 노드라고 할 때 이전의 칸에 상관없이 목적지 칸의 값이 1(벽)이면 1의 가중치를 적용하고 0인 경우 0의 가중치를 적용합니다. 그리고 A -> B, B -> A 와 같이 양방향으로 간선을 정해줘야 합니다. 하지만 다행히 직접 구현할 필요는 없습니다. 가중치가 이전 칸의 종류에 상관없이 목적지 칸..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 주의할 점은 출발지와 도착지가 같지만 가중치가 다른 간선이 주어질 수 있다는 점입니다. 이 점 때문에 인접 행렬이 아니라 인접 리스트로 간선을 표현해야 합니다. ... /* 최소 비용 구하기 https://www.acmicpc.net/problem/1916 */ public class Main { static int n,m; static long INF = Long.MAX_VA..

www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 문제 풀이 이 문제의 핵심은 임의로 붙여진 부분은 신경쓸 필요가 없다는 사실을 간파하는 겁니다. 문제에서 초기의 문자열 A가 주어지고 이 문자에 앞,뒤에 임의의 문자를 붙여 B와 길이를 맞춘다고 했습니다. 문자열 간의 다른 부분을 최소화하기로 했으므로 임의로 붙인 문자열은 B에 대응하여 같은 부분이여야 합니다. 이 상황을 이해하면 문제가 간단해집니다. 초기 문자열 A가..

www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 완전 탐색을 통해 조합을 찾고, 조합들을 문자열로 변환해 set에 저장합니다. 그리고 set에 저장된 문자열을 다시 정렬해 출력합니다. 주목할만한 부분은 Comparator 구현 코드입니다. "1 2 3 10 11", "1 2 3 4 5" 과 같은 문자열 두 개가 있다고 할 때, 이 두 문자열을 사전식으로 정렬하려면 단순하게 제공되는 라이브러리만으로는 정렬할 수 없습니다. 그냥 Arrays.sort를..

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 디버깅하는데 정말 하루 꼬박 걸렸던 문제였습니다. 문제를 풀면서 테스트의 중요성을 다시금 느꼈습니다. 특히 구현 문제에서는 더욱더. 구현 문제의 경우 알고리즘의 난이도 자체가 높다기보다 복잡도가 올라가면서 나타나는 실수들 때문에 발목을 잡히기 쉽습니다. 적절하게 메서드로 분리하고 메서드마다 테스트를 착실히 하는게 중요하다고 느껴졌습니다. 저도 테스트 메서드를 작성하고 나서야 짧은 시..