본문 바로가기
반응형

알고리즘63

백준 #1074 Z 이번 문제는 자기 복제 개념이 들어가 있는 문제입니다. 큰 모양에서도 Z를 이루고, 작은 모양에서도 Z를 이루는 형태로 배열을 채울 때, 주어진 행과 열에 어떤 숫자가 있는지 알아내는 문제입니다. 난이도는 Silver I입니다. 위의 그림과 같이 2x2라면 Z 모양대로 숫자를 배치합니다. 그런데 배열 갯수가 늘어나면, 과 같이 복잡한 형태가 됩니다. 여기서 주어진 칸의 숫자를 알아내면 됩니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N .. 2019. 12. 30.
백준 #1068 트리 이번 문제는 트리에서 어떤 노드를 삭제하고 나서의 말단 노드(leaf node)의 갯수를 구하는 것입니다. 위의 그림에서처럼 트리가 있는데, 1번 노드를 삭제하면, 3번 노드와 4번 노드도 같이 삭제되어서 2번 노드 하나만 말단 노드가 됩니다. 그 갯수를 구하면 됩니다. 난이도는 Silver I으로 되어 있지만, 구현은 어렵지는 않습니다. 문제의 원 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acm.. 2019. 12. 30.
백준 #1067 이동(FFT) 이번 문제는 Platinum II 난이도 문제입니다. 이 문제를 풀기 위해서는 길쌈 코드(Convolution Code)에 대한 이해가 필요합니다. 길쌈 코드는 크게 순환하지 않는 코드와 순환하는 코드가 있습니다. 이 문제에서는 순환하는 코드와 관련된 문제입니다. 길쌈 코드는 통신에서 많이 사용되기는 하지만, 보통 시스템을 이해하는데 있어서 중요한 개념 중 하나입니다. N개의 수를 가지고 있는 두개의 수열 X, Y가 있습니다. 이 수열을 순환하는 길쌈 코드로 만들 때, 가장 큰 값을 찾아야 합니다. 길쌈 코드라는 것은 무엇인가를 알아야 합니다. 두개의 수열 { 1, 3, 2, 4 } 와 { 1, 2, 3, 4 } 가 있다고 해보죠. 이 두 수열을 길쌈 코드로 작성하면 다음과 같이 됩니다. 두개의 수열을 .. 2019. 12. 30.
백준 #1057 토너먼트 토너먼트 경기는 두개의 팀 또는 선수가 싸워서 이기면 한단계씩 올라가는 경기입니다. 기본적으로 이진트리 형태를 가지고 있습니다. 문제의 내용은, 1부터 N까지 선수들을 일렬로 세웠을 때, A번 선수와 B번 선수가 언제 경기를 하게 될 수 있는지를 찾는 것입니다. 이게 이진 트리라는 성격을 알면 의외로 쉽게 풀 수 있습니다. Silver II 문제로 되어 있지만 그보다는 난이도는 너 낮다고 보입니다. 그림과 같은 토너먼트 표가 있다고 하고, 왼쪽부터 1, 2, 3, 4, 5, 6, 7, 8 이라고 숫자가 매겨졌다고 해보죠. 대한민국은 5번이 됩니다. 그런데 캐나다와는 언제 붙을 가능성이 있는지 알아보자고 한다면, 캐나다는 2번에 있습니다. 그러면 결승에 가서야 캐나다와 경기할 가능성이 있습니다. 대한민국과.. 2019. 12. 29.
백준 #1051 숫자 정사각형 문제 자체는 상당히 간단합니다. 난이도도 Silver III로 크게 어렵지 않은 문제입니다. 정답비율은 37%정도로 낮은 편이네요. NxM 의 숫자 행렬이 주어지는데, 이 중에 정사각형을 이룰 수 있는 4개의 숫자를 골라야 하는데, 행과 열에 평행하면서 4개의 숫자가 같은 숫자여야 합니다. 가장 작은 경우는 1x1 정사각형이 될겁니다. 아래는 실제 문제의 링크입니다. https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다. www.acmicpc.net 전 .. 2019. 12. 29.
백준 #1049 기타줄 이 문제는 간단한 형태의 나눗셈과 적절한 곱 연산만 하면 풀 수 있는 문제입니다. Silver IV 문제로 분류되어 있지만, 그보다는 난이도는 더 쉬워보입니다. 단지 정답률이 29.3%로 상당히 낮습니다. 이 문제는 선입관이 있으면 실수할 수도 있다고 봅니다. 묶음상품의 단가가 개별상품의 가격보다 싸야할거라는 것과 묶음상품이 싼 곳이 개별상품 가격도 쌀거라는 선입관을 버리면 쉽게 풀 수 있습니다. 문제의 내용은 기타줄을 사는데, 필요한 기타줄의 갯수가 주어지고, 그 갯수에 맞추어서 기타줄 상점에서 파는 6개들이 묶음상품과 개별 상품을 적절하게 사서 가장 싼 가격에 필요한 기타줄을 사는 문제입니다. 다음은 이 문제의 링크입니다. https://www.acmicpc.net/problem/1049 1049번:.. 2019. 12. 28.
728x90

티스토리툴바