본문 바로가기

Programming456

#1325 효율적인 해킹(DFS) 이번 문제는 Silver II 난이도의 문제입니다. 저는 처음에 너무 단순하게 생각해서 한번 틀렸네요. 신뢰관계의 종속성이라는 문제때문인데요. A 가 B를 신뢰하고, B가 C를 신뢰하면, A가 C를 신뢰한다는 사실입니다. 이에 대한 이해도가 틀리면, 해결방법도 당연히 틀리겠죠. 문제의 요지를 살펴보면, N개의 컴퓨터들이 있고, M개의 신뢰관계가 존재할 경우에, 신뢰를 받는 최상위 컴퓨터를 찾는 것입니다. 예를 들면 다음의 그림과 같이 5대의 컴퓨터가 있고, 4개의 신뢰관계가 주어졌다고 해보죠. 화살표 방향으로 신뢰관계가 주어집니다. E는 C를 신뢰하고, C는 A와 B를 신뢰합니다. 직관적으로 보면, 저 위의 그림의 경우에 A 또는 B를 해킹하면, 총 4대의 컴퓨터를 한번에 해킹할 수 있습니다. 전 이 문.. 2020. 1. 24.
#1322 X와 K(Mathematics) 이번 문제는 Gold IV 난이도 문제이지만, 수학적인 원리를 알고 있으면 아주 쉽게 풀 수 있습니다. 주어진 X에 대하여 다음을 만족하는 Y를 구하는데, K번째 Y를 구하는 문제입니다. \[ X + Y = X | Y \] 여기서 | 연산자는 Bitwise OR 로 비트합을 계산합니다. 비트합은 각 비트끼리 논리합(Logical OR)을 합니다. 이를 만족하는 Y 는 X의 비트 중, 1인 부분은 반드시 0이어야 하고, 0인 부분은 1이든 0이든 상관이 없습니다. 만약, X의 비트 중 1인 부분에 같은 위치의 Y의 비트가 1이라고 한다면, 비트합에서는 1이 되지만, 덧셈에서는 0이 됩니다. 어떻게 잘 조합하면 될 것이라고 생각할 수 있지만, 그럴 수 없습니다. X의 비트와 Y의 비트중 같은 위치에 1이 있.. 2020. 1. 23.
#1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19.
#1303 전쟁 - 전투 (DFS) 이번 문제는 Silver I 문제로 기초적인 DFS 문제입니다. 핵심은 연결된 지역의 수를 알아내는 것으로, "섬의 개수" 등과 같은 문제와 동일합니다. MxN 지역(보통은 NxM인데, 여기서는 MxN입니다.)에 W로 마킹된 곳과 B로 마킹된 곳이 있습니다. 대각선으로는 이어질 수 없고, 상하좌우로만 이어집니다. 서로 이어진 곳을 하나의 집단이라고 한다면, 그 집단의 구성수의 제곱을 합한 것이 전투력이 됩니다. 이 전투력을 각각의 집단 'W'와 'B'를 표시하면 됩니다. DFS로 해결해도 되고, BFS로 해결해도 되는 문제입니다. 저는 개인적으로 DFS를 선호합니다. 결국 큐 자료구조를 선호하느냐 아니면 스택자료 구조를 선호하느냐의 차이겠죠. 또한 경계선 검사를 할 때, 미리 더 넓은 지역을 잡아놓고 새.. 2020. 1. 19.
#1300 K번째 수 (이분탐색) k번째 수를 찾는 문제는 알고리즘 강의 시간에 시험문제로 나온 적이 있습니다. 퀵정렬 알고리즘을 가지고 k번째 원소를 찾는 문제였습니다. 사실 C++에 k번째 수를 찾는 함수를 제공하고 있으니, 이를 이용하면 아주 쉽게 찾을 수 있습니다. 가장 쉽게 풀 수 있는 방법은 정렬한 후에 k번째 원소를 출력하면 되겠지만, 이것은 너무 뻔한 이야기겠죠. 문제에서도 정렬한 다음에 K번째 수를 찾는다고 이야기가 나와있습니다. 이렇게 뻔한 방법으로 문제를 풀라는 것은 당연히 아닙니다. 숫자의 범위가 꽤 큽니다. \(10^{10}\) 이니까, 그러면 int 자료형을 예상했을 때, 자료저장공간만 해도 \( 4 \times 10^{10} \) 이니까, 128MB 메모리 제한에 당연히 걸립니다. 자료공간에 필요한 40GB 입.. 2020. 1. 16.
알고리즘 기초 알고리즘이란? 알고리즘이란 "문제 해결 절차를 체계적으로 기술"한 것입니다. 그러면 알고리즘에서 말하는 문제는 무엇일까요? 알고리즘에서 말하는 문제는 주어지는 입력이 있다면, 그 입력에 맞는 출력을 내는 것을 말합니다. 문제에는 입력과 출력이 명시되어야 하며, 어떤 출력을 원하는지 문제에서 충분히 설명되어야 합니다. 입출력의 예로 들어볼께요. 문제 해결 절차를 체계적으로 기술한다는 의미는 입력을 받아서, 그 입력을 바탕으로 출력을 만드는 기술을 의미합니다. 2020. 1. 15.
728x90

티스토리툴바