목록분할정복 (5)
HS_development_log
문제 https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 | 프로그래머스 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 programmers.co.kr 문제를 쪼개서 푸는 분할정복 문제. 재귀함수 방식을 이용하면된다. 알..
문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, www.acmicpc.net 재귀적 탐색으로 문제를 작게 쪼개서 풀면되는문제. 알고리즘 4칸이 될때까지 재귀함수를 사용하여 쪼개서 들어간다 4칸이되면 Z순서대로 탐색..
문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 접근방법이 꽤 어려웠던문제. 포스트오더와 인오더의 특징을 잘 활용해야지 풀 수 있었다. 포스트오더의 특성상 맨 마지막에 오는것이 루트이다. 인오더는 루트를 기준으로 왼쪽 오른쪽이 나뉜다. 따라서 포스트오더로 루트를 찾고 인오더로 왼쪽 오른쪽 노드를 찾아서 계속 작은 트리로 노드를 쪼개서 프리오더를 해주면 된다. 알고리즘 포스트오더의 끝을 루트로 정하고 프리오더로 답을 출력해야하므로 일단 출력한다. 루트를 기준으로 인오더..
문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 종이의 개수를 세는문제 큰 배열을 작은 배열로 쪼개가면서 풀면 된다. 문제설명에서 1. ~~~이 맞다면 ~~~해라 2. ~~~~..