본문 바로가기
반응형

BOJ50

#1342 행운의 문자열(Back tracking) 이번 문제는 주어진 문자열에 대해서 인접하는 문자가 같은 경우가 없도록 배치할 수 있는 경우의 수를 출력하는 것입니다. 예를 들어서 aabb 란 문자열이 주어진다면, 서로 인접한 문자가 같지 않게 배치될려면, abab baba 두가지 경우가 가능하겠죠. 그러면 2를 출력하면 됩니다. 난이도는 Gold III인데, 딱히 어려운 문제라는 생각은 안 들었습니다. 제 경우에는 빈도를 계산해서, 그 빈도를 이용해서 백트래킹 기법을 이용해서 모든 경우를 계산했습니다. 동적 프로그래밍으로 중복을 줄여서 계산할 수도 있을 것 같기는 했지만, 그건 포기했습니다. 문자열 길이가 10밖에 안 되니까 어찌어찌 가능할 것 같기는 하지만요. 문자가 소문자로만 주어지는지 몰라서 처음에 빈도로 계산 안 하고, 정렬을 통해서 해결했었.. 2020. 1. 26.
#1339 단어 수학(Mathematics) 이번 문제는 복면산과 비슷한 개념의 문제입니다. A~Z까지의 문자가 사용되며, 각각의 문자는 서로 다르면서 0~9까지의 숫자 중 하나가 사용될 수 있습니다. 복면산 문제들은 퍼즐 형태로도 나와서 아마 풀어본 분들이 많을겁니다. 대표적인 복면산 문제들이 몇가지가 있죠. 예를 들어서 아래 그림과 같이 "Send More Money"라는 문구를 가지고 만든 복면산은 널리 알려져 있습니다. 이번문제는 A~Z로 이루어진 여러개의 단어의 합을 최대로 하기 위해서 적절한 숫자를 대입해서 그 합을 출력하는 것입니다. 문제 자체는 아주 쉽고, 사실 풀이도 어렵지 않지만, 난이도 Gold IV 문제입니다. 제가 푼 방식은 단어가 나올 때마다, 각 자릿수의 문자를 기록하고, 그 합을 계산했습니다. 예를 들어서 ABC, BC.. 2020. 1. 26.
#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.
#1300 K번째 수 (이분탐색) k번째 수를 찾는 문제는 알고리즘 강의 시간에 시험문제로 나온 적이 있습니다. 퀵정렬 알고리즘을 가지고 k번째 원소를 찾는 문제였습니다. 사실 C++에 k번째 수를 찾는 함수를 제공하고 있으니, 이를 이용하면 아주 쉽게 찾을 수 있습니다. 가장 쉽게 풀 수 있는 방법은 정렬한 후에 k번째 원소를 출력하면 되겠지만, 이것은 너무 뻔한 이야기겠죠. 문제에서도 정렬한 다음에 K번째 수를 찾는다고 이야기가 나와있습니다. 이렇게 뻔한 방법으로 문제를 풀라는 것은 당연히 아닙니다. 숫자의 범위가 꽤 큽니다. \(10^{10}\) 이니까, 그러면 int 자료형을 예상했을 때, 자료저장공간만 해도 \( 4 \times 10^{10} \) 이니까, 128MB 메모리 제한에 당연히 걸립니다. 자료공간에 필요한 40GB 입.. 2020. 1. 16.
728x90

티스토리툴바