어제밤부터 고민하고 고민하던 문제! 이제는 그냥 외워야겠다라고 싶을 만큼 도전했다 ㅎㅎ.. 1. 출처 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 2. 설계 처음에는 조상이라고 해서 크루스칼로도 생각해봤는데, 그건 찐 조상! 나의 최상위 조상을 찾아주는 알고리즘이기 때문에 아니라고 생각했다. 그 후에는 트리를 직접 만들어서 같은 두 노드를 같은 depth로 만들어 준 후 함께 올라가는 시나..
쉬운 문제일줄 알았는데, 시간과의 싸움이었던 문제 바로 기록 들어간다!!! 1. 출처 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 시간 초과와의 싸움 ㅠ 아래 설계에서 실패 이유까지 설명하겠다. 3. 설계 1) 실패한 설계 문제를 보면, 문자열 W가 랜덤순서이다. 만약 abcd라고 해보자 그럼 W는 abcd일 수도 있고, cdab일 수도 있다. 그리고 내가 찾은 벽화의 기록된 마야 문자열 S에 abcd, cdab라는 문자열이 부분 문자열로 포함되어 있는지를 찾는 문제이다. 그..
설탕배달2가 생각보다 빠르게 풀린 것 같아 내가 못풀고 쟁여놨던 경비원 문제를 풀어보았다. 그동안 프로젝트하면서 함수를 장난아니게 만들었더니 함수를 이용해 차근차근 푸는 능력이 생겼나보다. 잘 해결해내었다. 좀.. 비효율적인 코드인 것 같지만... ^^ 아무튼 시작! 1. 출처 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 이것도 3달 전엔 못풀었던 문제다...ㅎㅎ 알고를 한동안 쉬다가 오니 머리가 리프레쉬라도 되었나...^^ 2. 설계 일단 문제 자체 이해는 쉽다. 경비원 X가 (동/서/남/북) 위치에서 가게(..
1학기 마지막 프로젝트도 끝내고... 하나금융티아이 1차 면접도 끝내고... 넘 오랜만에 알고리즘으로 돌아왔다 ㅠ 뭔가 그리웠음... 한 번 코테를 쳐봐서 그런지 제대로 코딩테스트를 준비하고 싶어져서 [무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의 IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런 www.inflearn.com 이 강의를 보며 100제 풀어보려고 한다! 내가 풀다가 처음보다시피 한 문제 풀이 방법이 있어 가져왔다. 바로 누적합 문제이다. 1. 출처 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는..
골드 5 길래 얼른 풀고 시험공부 할라했더니 3시간 순삭했던 문제...;; 나의 실패썰과 성공썰을 공유하겠다. 1. 출처 처음엔 그냥 무작정 브루트포스 방식으로 알고리즘을 짰는데, 조합으로 풀지 않으면 답이 나오지 않겠다라는 생각을 하게 해 준 글이 있었다. 그래서 2번째 알고리즘은 조합으로 풀었더니 정답이 나왔다. 2. 설계 / 전체코드 1) 실패한 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Node { int r; int c; publi..
2일 전에 풀기 시작 한 문제... 프림으로 풀어서 안풀려가지고... 크루스칼로 도전해보았다. 1. 출처 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 2일 전엔 프림으로 풀다가 틀렸고, 오늘은 크루스칼로 풀다가 부모를 비교하는 과정에서 험난한 과정을 겪었다. 2. 설계 반례 참고 : https://www.acmicpc.net/board/view/48609 글 읽기 - 반례를 못..
이제 곧 싸피데이!!! 싸피데이를 즐기기 전 숨바꼭질3 문제를 풀고 공부 기록 시작한다 ㅠ 1. 출처 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 왜이리 어려운 것이냐?... 처음 이 문제를 보고, 어떻게 문제를 풀어야할지 감이 잡히지 않았다... 그래서 결국 구글링을 통해 다른 사람들의 코드를 보며 어떻게 문제를 짜야할지 봤던 문제.. https://www.acmicpc.net/board/view/115423 글 읽기 - dp 문제가 아닌지, 다익스트라 문제인지 어떻게 판..
매주 토요일이면 충남대 할리스를 가서 공부를 하는데, 옆에서 지연이가 어떤 문제를 보며 해시맵 어렵다고 하여 나도 알려달라고 해 풀어보았다. 그동안 백준/SWEA에서 문제 풀면서 해시맵을 쓴 적이 없었던 것 같은데, 좋은 경험이 되었다. 1. 문제 출처 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 번호를 쳐도 나오지 않는 문제 ... 오늘도 역시 실패한 설계와 성공한 설계를 둘 다 쓸 것이다. 2. 설계 1) 실패한 설계 해시맵으로 포켓몬 번호와 이름을 저장해서 퀴즈에 포..
