흔적을 기록하는 노트

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제도 N-Queue 문제처럼 시간을 단축시킬 수 있는 방법을 찾는게 관건인 것 같다. 아래와 같은 방식을 사용하지 않으면 시간초과가 일어나는지는 모르겠지만, 굳이 단축시키지 않을 이유는 없으니.. 우선, 수빈이가 동생보다 더 오른쪽에 있다면 가능한 방법은 (X-1)뿐이다. 왼쪽으로 한칸씩 총총 이동하는 방법밖에 존재하지 않으니, (N>=K) 일 때 걸리는..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 와... 힘든 문제였다. 사실 이 문제는 이전에 해결한 문제였다.(그때도 힘들게 다른 코드 참고하며 풀었던 걸로 기억함) 그래도 풀어봤던 문제니 복습겸 가볍게 풀자~ 싶었는데 이 녀석이 며칠을 고생시킬 줄 몰랐다. 약간 참고해가며 그래도 구동은 시켰는데, 문제는 시간 초과.. 이 문제를 풀며 다시 한 번 깨달은 점은, 난 정말 필요하지 않은 부분까지 신경쓰고 집착한다는 것이다. 더보기 더보기 import java..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 새로운 도전의 연속인 코딩 연습에서, 새로운 도전에 시간이 많이 걸리는 내겐 참 어렵다... LCS를 이해하는 데에도 많은 시간이 걸렸다. 어려워서가 아니라 배움이 귀찮아서...ㅠ 얼른 습관을 다시 찾아야겠다...!! LCS는 부분집합?(공부를 안하니 이제 용어도 가물가물하다..) 같은 느낌으로 적절히 연산해주는 문제였다. 가령 {A, B}와 {B}를 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 직전에 해결했던 1753번 문제의 알파 문제다. 이 문제에서 조금만 수정해도 충분히 통과할 수 있다. 더보기 더보기 https://stepping-coding.tistory.com/5 [Java]BaekJoon.AC 1753 : 최단경로 (다익스트라, 인접리스트 사용) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 와, 대장정의 기록이다.. 평소 시간초과나 메모리초과를 일으키는 함정은 없는지 돌다리를 두드리는 편이다. 근데 이 점에 몰두하다보면 브루트포스 같은 방식은 시도하기가 꺼려지더라. 브루트포스가 제일 나은 방법인데도 설마 아니겠지 싶은 생각에 사로잡혀 아이디어도 덜 떠오르고.. 그래서 고작 몇 문제 쉬는 연습을 했더니... 덫에 걸린 것이다!ㅎㅎ (변명의 시간이었..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 와! 내가 생각해도 효율성 꽝인 코드다ㅋㅋㅋ 사실 효율성이라기보다 코드가 참 길다.. 코딩하면서도 '하... 이게 아닐텐데...' 무한반복하며 끝끝내 완성했다!^^ 내 우물파기 실력과 인내심과 자존감에 박수를 보낸다. (훌륭한 성적으로) 채점을 통과했음을 인지하곤 그냥 뿌듯하기만 하더라;;ㅋㅋ 「이 문제의 핵심은 브루트포스 알고리즘을 이용해 모든 경우를 다 조사하는 것이다. 그러기 위해선 모든 칸..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net (문제 이름이 DSLR이라 카메라 문제인 줄 알았는데... 이상한 계산기 문제였다..) 처음엔 TreeMap을 이용해 숫자와 나열을 저장하려 했다. 그런데 시간이 많이 걸릴 것 같기도 했고, visit 배열과 비교도 번거로웠다. 또한 bfs를 구현하고 싶었는데, 구현이 쉽지 않았다. 아무리 머리를 굴려도 각이 안서길래, 역시 첫발은 항상 틀리는ㄱ... 내게 이 문제가 어려웠던 이유는 ..