본문 바로가기
반응형

알고리즘63

백준 #1230 문자열 거리 문자열 거리 문제는 "최장 공통 부분 문자열" 문제와 유사합니다. 동일하게 동적 프로그래밍 기법을 이용해야 하지만, 구현하려고 한다면, 조금 생각을 해야 합니다. 난이도는 Gold II 입니다. 정답률 32.7%의 문제네요. 정답자 40명정도로 난이도 책정된 것에 비해서는 상당히 적습니다. 문제의 내용을 두개의 문자열이 주어졌을 때, 첫번째 문자열에 원하는만큼 문자열을 삽입해서 두번째 문자열을 만들고자 할 때, 문자열 삽입을 최소로 하고자 하는 문제입니다. 예를 들어서 "abcd" 란 문자열과 "abNORMAL cOMEdY"란 문자열이 주어졌다면, ab 와 c 사이에 "NORMAL "이란 문자열과 c와 d 사이에 "OME"라는 문자열, 그리고 d 뒤에 "Y"란 물자열을 삽입해야 하기 때문에 최소의 문자열.. 2020. 1. 9.
백준 #1229 빅뱅의 여섯번째 멤버 이 문제는 수학적 법칙을 좀 생각해보면 더 빨리 풀 수 있을 것 같은데, 일단 복잡해서 패스를 했습니다. Gold IV 난이도이지만, 단순 무식한 방법으로 프로그램을 짰네요. 다각수라는 것은 도형을 확장하면서 생기는 점들의 수입니다. 3각수는 잘 알려져 있고, 이 값은 1부터 n까지의 합과 동일합니다. 여기서는 6각수가 나오는데, 6각수는 \(n(2n-1)\) 의 수식으로 표현되며, 1, 6, 15, 28, ... 형태로 늘어나는 수입니다. 이 6각수를 적절하게 더해서 모든 수를 표현할 수 있습니다. 6각수의 첫번째 수가 1이므로, 최악의 경우에는 1을 여러번 더할 수가 있습니다. 어떤 수가 주어졌을 때, 6각수를 몇개 가지고 표현할 수 있는지 알아보라는 것이 문제입니다. 수학적으로 분석을 할 필요가 있.. 2020. 1. 8.
백준 #1215 잘못 작성한 요세푸스 코드 꽤 재미있는 문제였던 것 같습니다. 요세푸스 문제를 해결할 때, 큐를 이용해서 매번 풀었는데, 모듈라 연산으로 풀 수도 있었구나를 생각하게 만들었네요. Platinum V 문제이긴 하지만, 적절한 알고리즘이 알려진 상태가 아니라는 점을 감안하면 좀 더 난이도를 높게 주는 것이 맞을 듯 하네요. 그런데 오리지널 코드 그대로도 통과가 되는 것 같은데, 만약 그렇다면, 오히려 난이도가 떨어져야 할지도 모르겠네요. 이번문제는 다음의 코드를 적절하게 바꾸어서 같은 결과를 나오게 하는 것입니다. 결과 검증하기도 좋습니다. 실제 코드를 실행해보면, 아주 큰 수에 대해서 그래도 기다려줄 수 있는 속도가 나오니까요. 요세푸스 문제는 큐를 배울 때, 자주 등장하는 문제입니다. 큐를 구현하고, 큐에 데이터를 넣고 빼는 것을.. 2020. 1. 7.
백준 #1202 보석 도둑 이번 문제는 knapsack 문제라고 볼 수 있는데, 전혀 다른 문제네요. 그래도 탐욕 알고리즘을 적용하기 위해서 방법을 강구해야 합니다. 난이도는 Gold II 문제입니다. 정답률 23%로 상당히 낮습니다. 왜 틀릴까 생각했었는데, 틀린 이유들을 보면, 짐작이 갑니다. K개의 가방에 보석을 1개씩만 넣을 수 있는데, 각 가방에는 최대 넣을 수 있는 보석의 무게가 정해져있습니다. 보석에 무게와 값이 주어질 때, 가장 값어치가 높게 보석을 챙겨올 때, 그 값어치를 구하라는 문제입니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi.. 2020. 1. 6.
백준 #1194 달이 차오른다, 가자 이번 문제는 재미있는 문제였다고 봅니다. 스토리가 있긴 한데요. 난이도는 Gold I입니다. 정답률 25.9%, 정답자 1,001명입니다. 한지민이 인생의 미로를 탈출하려고 합니다. 자신이 처해있는 상황을 해결하기 위해서는 탈출구로 탈출해야 합니다. 그런데, 간혹 해결할 수 없는 문제에 도달합니다. 이 문제를 해결하기 위해서는 키를 구해야 하는데, 키는 그 문제에 맞는 키여야 해당 문제를 해결할 수 있습니다. 키는 a~f까지 존재하며, 문제는 A~F까지 존재하고, 각각이 대응되는 키와 문제입니다. 해결할 수 없는 문제는 #입니다. 0은 출발점이고, 1은 새로운 탈출구입니다. 봄이 가기전에 가장 빨리 탈출구로 탈출하려고 합니다. 늙어서 김혜자가 되면 안 되거든요. 문제는 전형적인 BFS 알고리즘 문제에서 .. 2020. 1. 6.
백준 #1153 네 개의 소수 골드바흐의 추측과 관련해서는 한두번 이상은 들어보았을겁니다. 유명한 문제이긴 하지만 아직 증명이 안 되었죠. 사실 수학적 가치가 크다고 볼 수는 없는 문제입니다. 쉽게 증명될 것이라는 예상과는 달리 아직까지 미해결 문제입니다. 골드바흐의 추측은 2보다 큰 수는 세개의 소수의 합으로 만들 수 있다였습니다. 사실 당시에는 1이 소수로 취급되었을 때였기 때문에, 3=1+1+1, 4=2+1+1, 5=2+2+1 로 표현이 가능했습니다. 현대 소수 개념으로는 6이상의 수는 세개의 소수의 합으로 표현할 수 있다입니다. 이번 문제는 Gold IV 난이도입니다. https://www.acmicpc.net/problem/1153 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프.. 2020. 1. 5.
728x90

티스토리툴바