# Foundation/백준풀이 (43) # Foundation/백준풀이 백준 1439 풀이 및 해설 개요 어떤 문제들은 입력을 짧게 치환해도 상관없는 경우가 있습니다. 이 문제가 그러한 것 중의 하나이며, 이 문제를 쉽게 풀려면 연속된 구간을 압축해야 합니다. 특정 값이 연속되는 구간은 나중에 같이 뒤집혀져야 하므로, 각 구간을 대표값 하나로 축약할 수 있겠죠. 축약 전: 1100000011 축약 후: 101 직관적으로 풀기 입력형식 되새김하기 이제 우리는 숫자가 연속되는 경우를 생각할 필요가 없습니다. from을 to로 바꿔야 한다고 했을 때, 다음과 같이 간략화된 입력만 생각하면 되는 것입니다. from으로 시작하는 경우: from from-to from-to-from from-to-from-to ... ... to로 시작하는 경우: to to-from to-from-to to-from-to-fro.. 2020. 12. 3. 16:45 # Foundation/백준풀이 백준 2437 풀이 및 해설 개요 매우 복잡해보이는 문제가 그림으로 풀면 매우 단순하게 풀리는 경우는 그리 드문일이 아닙니다. 이 문제는 수학적 귀납법으로도 풀 수 있지만, 수직선을 사용하면 훨씬 직관적이고 쉽게 풀립니다. 핵심은 측정할 수 있는 무게의 구간을 끊기지 않게 확장시키는 것 입니다. 핵심 현재 닫힌구간 [1, 10]을 측정할 수 있는 상태에서 무게가 5인 무게추가 더 주어졌다면, 기존에 측정할 수 있었던 무게 + 5를 측정할 수 있으므로, 1부터 10까지 순회하면서 5를 더한값을 추가로 측정할 수 있습니다. 즉, 닫힌구간 [1+5, 10+5]를 추가로 측정할 수 있습니다. 그렇다면 닫힌구간 [1, 5]를 측정할 수 있는 상태에서 무게가 7인 무게추가 더 주어지면 어떻게 될까요? 닫힌구간 [1, 12]를 전부 커버할 수 .. 2020. 12. 2. 19:04 # Foundation/백준풀이 백준 2136 풀이 및 해설 개요 보자마자 팟 하고 떠오르지 않으면 매우 고생하는 문제입니다. 어느 문제나 그렇겠지만, 이러한 애드 혹 분류의 문제는 이런 경향이 더 심합니다. 핵심은 개미간 충돌을 고려하지 않는다입니다. 해설 충돌 무시하기 아래와 같이 충돌 직전의 두 개미를 생각해보겠습니다. 1초 뒤에 두 개미는 서로 충돌하여 개미의 진행방향이 다음과 같이 바뀔 것입니다. 여기서 개미가 아닌 화살표에 집중해볼까요? 화살표만 바라보았을 때, → 화살표는 ← 화살표가 있든 없든 상관없습니다. 항상 4에서 5로 이동함을 알 수 있습니다. 마찬가지로 ← 화살표도 → 화살표가 있든 없든 상관없이, 항상 5에서 4로 이동함을 확인할 수 있습니다. 위의 이유로, 각 화살표는 다른 화살표를 신경쓰지 않고 제 갈길만 가면 된다는 결론에 도달합니다.. 2020. 11. 28. 21:50 # Foundation/백준풀이 [LCS] 백준 1958 :: LCS 3 LCS 3 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB29661390108848.615%문제문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.입력첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)출력첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한.. 2019. 7. 10. 00:30 # Foundation/백준풀이 [LCS] 백준 9252 :: LCS 2 LCS 2 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB83723392258841.897%문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.LCS가 여러 가지인 경우에는 아무거나 출력한다.예제 입력 1 복사ACAYKP CAPCAK 예제 출력 1 복사4 ACAK 문제 풀이1.. 2019. 7. 10. 00:21 # Foundation/백준풀이 [LCS] 백준 9251 :: LCS LCS 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB138355899435242.097%문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1 복사ACAYKP CAPCAK 예제 출력 1 복사4 문제 풀이1차 풀이 ( 5896 KB, 8 ms)Top-Down 방식의 LCS 알고리즘 활용.두 단어 .. 2019. 7. 10. 00:15 # Foundation/백준풀이 [LIS] 백준 4198 :: 열차정렬 열차정렬 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB123824616621.364%문제에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는.. 2019. 7. 9. 11:54 # Foundation/백준풀이 [LIS] 백준 2568 :: 전깃줄 - 2 전깃줄 - 2 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB3233102759032.435%문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 .. 2019. 7. 9. 11:48 이전 1 2 3 4 ··· 6 다음
