HwangHub

유형 파악 이 문제는 2차원 배열 상의 출발지에서 목적지까지 이동시간의 최소를 구하는 문제이면서, 이동간 시간 가중치가 동일하기 때문에 전형적인 BFS 문제라고 이해할 수 있다. 아울러, 몇 개의 점을 선택하여 제거하는 경우를 세야 하므로 이 부분은 백트래킹 로직을 활용하여 풀어내 주었다. 제출 코드 구성했던 로직의 특징은, 여러 경우에서 도착지에 도달하는 시간이 도출될텐데, 그 경우 중 가장 빠른 경우에서의 시간을 구하는 것을 우선순위 큐를 활용하여 도출해줬다는 것과, 제거하려는 벽을 중복으로 선택하지 않기 위해 selected[][] 라는 배열을 운영한 것이다. 개인적으로 헤맨 부분은, 백트래킹을 통해 제거할 벽을 모두 선택했을 때 bfs를 수행하기 위해 관련 변수들을 초기화해줘야 한다는 것이다. 이..

지난 실력진단 문제에서 구성되는 마을의 최대 크기라던지, 마을의 개수를 어떻게 구할 수 있을지 쉽게 떠오르지 않았어서 해당 부분을 연습하기 위해 이 문제를 다시 풀어봤다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 접근 이 문제는 단순 반복문을 통해서는 나의 한계로 로직이 떠오르지도 않거니와, 있더라도 분명히 매우 복잡할 것이므로 패스하였다. 그 외에 순열, 조합과 같은 경우의 수를 탐색하는 경우도 아니고, 최대최소를 얻는 그리디한 바이브의 문제도 아니였다. 탐색 알고리즘 중에 이웃한 항과의 관계를 통해 답을 도출해 내는 그래프 알고리즘이 이 문..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 지난번에 풀었던 "사각형 채우기"와 같은 유형의 문제로써, 점화식을 세울 때 조금 더 생각을 해줘야 하는 문제이다. 기본적으로 n번째 자리까지 타일을 까는 경우의 수는 n-1, n-2 번째까지의 타일을 까는 경우의 수 들을 이용하여 도출해낼 수 있다는 아이디어가 DP의 기본 흐름이다.(큰 문제는 작은 문제로 쪼개어 생각한다.) 이렇게 볼 때, 1칸짜리 그리고 2칸짜리를 이용하여 f(n) = 2 * f(n-1) + 3 * f(n-2) 까지는 쉽게 구해질 것이다. 이게 만약 안보인다면 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 1. n층 높이의 계단을 오르는 경우의 수를 구하는 문제이다. -> 여기까지만 보면 아직은 어떤 알고리즘을 쓸지 확신하기 어렵다. 2. 2개 또는 3개 계단 단위로만 오를 수 있다고 한다. -> 일정 패턴으로만 진행되는 것을 알 수 있다. 이렇게 정형화된 패턴을 배치하는 경우의 수를 구하는 문제는 다이나믹 프로그래밍의 가장 대표적인 유형이다. 문제에서 요구하는 답은 n개의 계단을 오르는 경우의 수 이므로 f(n) = n번째 계단을 오르는 경우의 수 일 것이다. n번째 계단은 n-2번째 계단 또..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 가중치가 일정한 상황에서 각 귤에 도달되는 시간을 숫자로 표현하는 문제이므로 BFS 문제임을 알 수 있다. 상한 귤들은 시작점이 되고, 인접한 귤로만 이동하면서 time을 1초씩 추가하면 된다. 이를 기록하는 배열은 별도로 선언한다. 그 외에 -1, -2 와 같은 결과 출력 양식을 맞춰주기 위해서는 출력 단계에서 조건문으로 처리해주면 깔끔하다. 문제 풀이 public class 상한_귤 { private static class Pair { private int x, y; private Pair..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 가중치가 1로 동일한 경우에서의 최단 거리를 묻는 문제이므로 BFS를 돌리면 된다고 느낄 수 있다. 대표적인 유형의 문제인 걸로 느껴지는데, 지금 뇌가 정지한건지 도저히 내가 어디가 틀린지 모르겠다... 일단 내 풀이는 맞을 가망이 없었고, 아무리 봐도 모르겠어서 일단은 답안을 이해한 뒤에 내 방식대로 고쳐서 작성해 보았다. 내 풀이(틀린 풀이) 나는 인간이 있는 좌표로부터 최단거리에 있는 대피소를 BFS로 찾고, 그 최단 거리를 ans라는 정답 배열의 인간 좌표에 입력해주는 방식으..