Cooper's devlog

[문제 링크] 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 이번 문제는 전화번호 목록입니다. 문제를 간략히 말씀드리면 전화번호 목록에 접두어가 중복되는 경우가 있는지를 확인하는 문제입니다. 만약 접두어가 중복되는 전화목록이 존재한다면 false 접두어가 중복되지 않는다면 true를 반환하는 문제입니다. [1.O(n^2) 접근법] import java.util.*; class Solution { public boolean solution(String[] phone_book) { Arrays.sort(ph..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net [문제를 접근방법] 이 문제는 컨셉을 어떻게 잡느냐에 따라서 문제를 푸는 시간이 좌지우지되는 문제입니다. 여기서 문제의 핵심은 '괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.' 여기서 적절히라는 의미는 괄호를 여러개 쳐도 상관없다는 것을 의미합니다. 이 것을 식을 통해서 확인해보겠습니다. 30 +40 -45 +60 + 75 - 80 + 20 이 경우를 확인해보면 괄호를 어떻게 쳐야 할까요? 30 + 40 -(45 + 60 + 75) - (80 +..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 이번 문제는 Z라는 문제를 풀어보았다. 이전에는 이 문제를 해결하지 못해 다른 블로그를 참고해서 문제를 풀었었다. 그리고 한동안 나는 이 문제를 알고 있다고 생각했지만 다시 풀려고 하다보니 계속해서 빗발치는 틀렸습니다를 확인하였다;; 그래서 이번에 문제를 직접 풀어보고 다시 한번 로직을 정리하고자 글을 작성한다. 확실히 내가 직접 고민해보지 않으면 소용이 없는 것 같다. [1. 간략한 분할정복 설명] 여기서 핵심을은 충분히 쪼개야 한다는 점이다. 충분히 ..

[문제 설명] 말그대로 최단거리를 구하는 문제입니다. 그렇다면 최단거리는 어떻게 구해야 하는걸까요? 최단거리를 구하기 위해서는 다익스트라(dijkstra) 알고리즘에 대해 알고 있어야 합니다! 문제 풀이에 들어가기에 앞서 다익스트라에 대해 간략히 설명드리고 문제를 풀어보도록 하겠습니다. [다익스트라 알고리즘] 다익스트라(dijkstra) 알고리즘은 다이나믹(dp) 프로그래밍을 활용한 최단 경로(Shortest Path) 알고리즘 입니다. 특정한 하나의 정점을 기준으로 해서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 다만 '음의 간선을 포함할 수 없다'는 점을 유의하세요! 자세한 문제 접근 방법은 해당 문제를 예로 들어서 설명하도록 하겠습니다. [문제 접근 방법] 자 이제 시작해보도록 하겠습니다! ..

[문제 설명] 이번 문제는 '양 구출 작전 '입니다. 문제를 간략히 설명하자면 각각의 섬들은 연결된 상태로 존재한다. 1번을 제외한 섬에는 양 혹은 늑대가 산다. 양을 싣고 이동하는 중에 늑대가 있는섬을 만나면 늑대는 양을 잡아먹는다.(늑대 1마리당, 양 1마리) 1번 섬으로 구출할 수 있는 양의 수를 찾는다. [문제 접근 방법] 문제의 내용에 '각각의 섬들은 연결된 상태로 존재한다.' 이 문구를 확인하고 트리 구조로 문제를 접근해야겠다고 생각했고 각 LeafNode들에서 출발해서 1번 섬에 도달할 때까지 양들이 살아남는 경우를 구하는 것이었습니다. 그러기 위해서는 순회 방법 중 후위순회(postOrder)이 적합하다고 생각했습니다. 먼저 문제 풀이 방식을 설명하면 리프노드에서 출발해서 상위 노드로 올라..