Cooper's devlog

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)이 적합하다고 생각했습니다. 먼저 문제 풀이 방식을 설명하면 리프노드에서 출발해서 상위 노드로 올라..

[문제 접근 방법] 이번 문제는 트리 순회 문제입니다. 이 문제는 이진트리로 전위 순회, 중위 순회, 후위 순회를 탐색하는 방식을 확인하고자 하는 문제 입니다. 문제에서 제시한 것을 다시 한 번 정리하면 전위 순회 : 루트 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 중위 순회 : 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드 후위 순회 : 왼쪽 자식 노드 → 오른쪽 자식 노드 →루트 노드 순으로 탐색을 한다로 문제에서 제시합니다. 문제 풀이 방식은 먼저 (1)트리를 구현하고 (2)전위(preOrder), 중위(inOrder), 후위(postOrder)로 출력하도록 하는 로직을 작성하는 방식으로 로직을 구성하면 되겠습니다. [전체 코드] import java.io.*; import java.uti..