Cooper's devlog

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

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

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

[문제 처음 접할 때] 간단히 문제를 설명하자면 성적순으로 이름을 정렬했을 때 범위 안에 들어가고 이름 길이가 같은 친구을 찾는 문제 입니다. 성적과 이름이 같다는 것으로 친구을 찾는 과정이 슬프지만 일단 문제를 한번 보겠습니다. 문제 풀이 수가 많은 문제가 일반적인 문제라고 생각해서 해당 문제를 선정했습니다. 문제 풀이에 앞서 투포인터에 대해 한마디로 정의하자면 두 개의 포인터를 사용한 방법으로 필요한 범위만 연산하고자 하는 방법에서 고안되었습니다. 기본적인 투포인터 문제는 좌우 인덱스를 선언해서 범위를 선정하는 방법으로 접근했지만 해결하지 못했고 이름의 길이를 담은 Queue를 생성한 접근 방법으로 문제를 해결했습니다다. [문제 접근 방법] 1. 이름 인덱스를 담는 Queue를 원소로 하는 배열을 생..

[문제를 처음 접했을 때] 이번 문제는 '합이 0인 네 정수 문제' 입니다. 문제를 간단히 설명드리면 말그대로 합이 0일 때 a,b,c,d의 조합 갯수를 구하는 문제 입니다. 처음 문제를 보고 생각한 접근 방법은 반복문을 이용한 완전탐색(Brute Force)를 생각했습니다.하지만, 입력의 크기가 4000이므로 시간 복잡도가 O(N^4)인 비효율적인 시간 복잡도가 발생합니다. 다른 접근법을 생각해야 합니다. 이 정도 연산은 컴퓨터에겐 괜찮지만 문제를 해결 못하는 답답함에 고통 받습니다;; 이를 개선하기 위해서는 투포인터(Two Pointer)을 이용해야 합니다. 투포인터(Two Pointer)은 아래 블로그에 잘 정리되어 있기 때문에 하단에 링크를 들어가셔서 내용 보시는 것을 추천하고 밑에 단계별 코드 ..