본문 바로가기

Problem Solving

 (152)
[백준/C++] 25824번 빠른 오름차순 메시지 전달 그냥 주위 친구가 풀어낸 거 보고 나도 풀어볼까? 하고 문제를 풀게 되었다. 문제를 처음 봤을 때는 BFS / 다익스트라 or 플로이드와샬 이라고 생각했는데 BFS로만 풀릴 것 같았다. 다시 생각해보니 input이 12로 제한되어있고 이진트리로 가지치며 나오는 최종 경우의 수를 생각해봐도 leaf에서 2^6으로 모든 경우의 수가 128보다 적다. 3초나 주어지는 것을 보니 브루트포스로 풀어낼 수 있을 것 같았다. 풀며 식을 세우다가 느꼈는데 DP로 식을 세울 수 있어 보였다. 물론 dp식을 세우는데 실패해서 시간을 낭비하고 브루트포스로 구현하였지만 맞춘사람을 보니 BFS와 DP로 풀어낸 경우도 확인할 수 있었다. 브루트포스를 이진트리 느낌으로 구현하다보니 조금 귀찮아 골드 문제가 아니였나 싶다. #inc..
[백준/C++] 23306번 binary는 호남선 비오길래 구글에 binary호남선 쳤다가 이 문제까지 오게된 건 안비밀.. 인터렉티브를 처음 풀어봐서 난해했다. 인터렉티브는 출력문을 통해 입력을 받아올 수 있는 다소 신박한 문제였는데 인터렉티브 문제에서 팁을 주자면 표준 입력 버퍼를 비워주지 않으면 버퍼에 남아있는 쓰레기 값이 들어가게 된다. 이 문제에서는 매 입력마다 (여기서는 출력문을 통해 입력을 받으므로) 버퍼를 비워줘야 하니 endl 사용이 적합하다. 쉽다고 생각하고 무지성 제출했다가 틀려서 다시보니 질문을 log2(N)번 밖에 못하는 조건이 있었다. 곰곰히 생각해보니 문제에서 힌트를 모두 제공하고 있었다. 시작과 끝만 비교해서 올라간 횟수가 많은지 내려간 횟수가 많은지 확인할 수 있다.(00이나 11은 don't care이고) 0으로 시작해 ..
[백준/C++] 6549번 히스토그램 분할정복 증명 일단 그리디 하게 풀어서는 문제의 정답을 구할 수 없고, dp로 풀기에는 배열의 크기가 압도적으로 모자란 것으로 확인했다. HTML 삽입 미리보기할 수 없는 소스 그래서 분할 정복으로 왼쪽 오른쪽 나눠서 진행하면 어떨까? 하는 생각을 하게 되었지만, 각각 방향에서 최댓값은 찾을 수 있으나 다른 방향을 걸쳐서(가운데 부분에서) 최댓값을 구하는 경우면 어떻게 하나 고민하게 되었다. 고민 결과 아래와 같은 이유로 가운데가 포함된 경우 그리디 하게 모든 직사각형을 가져가는 것이 맞다고 생각하게 되었다. Prove 가운데가 포함된 직사각형에서 더 큰 방향의 막대를 포함하여 크기를 계산하면 최댓값을 구할 수 있다. Basis 가운데 막대가 포함된 경우에서 최댓값이 있다고 가정한다. 가운데를 제외한 왼쪽 부분의 최댓..
[백준/C++] 2447번 별 찍기 - 10 처음 문제를 읽었을 때 N이 3의 제곱이니 3으로 나누다가 3이 된 순간, 가장 작은 형태를 바로 출력해주려고 했었다. 그런데 string 배열에 담아놓기도 힘들고 3줄씩 출력을 미리 하기도 힘들다고 판단해 다른 방법을 생각하게 되었다. 가지고 있는 N을 3x3으로 나누어야 하는데 어떤 식으로 분할을 진행할까 고민했는데 각 위치에 대하여 사이즈를 줄여가며 그 위치가 빈칸이 될 위치(흰색)인지 별이 찍힐 위치(파랑)인지 확인해가는 방법으로 결정하였다. 코드를 짜다가 공통점을 찾아봤는데 row와 column을 (0, 0)으로 시작하여 N까지 진행하면 9의 크기에서는 row와 column이 각 각 (1, 1) (1, 4) (1, 7) ... 일 때로 row % 3 == 1 & column % 3 == 1인 순..
[백준/C++] 1744번 수 묶기 처음 문제를 읽고는 엥? 이게 왜 골드지...? sort하고 0이 아닌 양수 음수 각각 절대값이 큰 수부터 묶어나가면서 계산하면 되지 않나? 라는 생각을 하였다. (설마 출력이 2^31이라고 int 써서 통과 못하는 사람들이 생겨서 그런가 했다. 묶었을 때 2^31보다 커진 후 음수를 빼며 int 범위 내로 돌아갈 수 있는 걸 낚는 낚시인가 싶었다.) 운이 좋게도 예제 4번이 반례가 되어 -1 0 1 인 경우를 해결하지 못했다. 이 경우(-1 0) + 1 로 풀어야 하는데 내 알고리즘은 그렇지 못했다. 추가적으로 -5 -4 -1 0 5 10이라는 테스트 케이스를 생성한 후 고민해보았는데 양수 음수를 나눠서 양쪽으로 묶는 행위를 진행해야겠다 라는 생각이 들었다. 그런데 투 포인터로 설계하기에는 다소 어려움..
[백준/C++] 1700번 멀티탭 스케줄링 컴퓨터 구조 시간에 Memory Replacement Algorithm에 대해 배운 적이 있는데 그 때 LRU 등등 다양한 알고리즘을 배우다가 뒤에 올 것이 무엇인지 알면 가장 직후에 사용될 것을 찾는 방법이 optimal한 방법이라고 하였다. 그 때는 뒤에 어떤 것이 올지 알 수 없었지만 문제에서는 알 수 있으니 greedy하게 풀어낼 수 있을 것이라고 생각했는데 가지고 있는 것들 중에 더 일찍 재사용될 친구를 찾는다는게 생각보다 어려워서 숫자도 100으로 크지 않으니 queue를 각 아이템마다 만들어서 풀어내려고 하였다. 들어오는 순서대로 queue에 넣고 다음에 오는 숫자가 가장 느린 친구를 pop시켜주고 이미 가지고 있다면 continue 하는 방식으로 코드를 구현하였다. 코드를 구현할 때 이미 ..
[백준/C++/KOI] 2437번 저울 증명 및 풀이 문제를 처음 읽었을 때 dp라는 생각이 스쳐지나갔는데 100만개의 저울추가 1000까지의 숫자를 가지면 배열로 만들 수 없을만큼 큰 수가 되니 포기하고 1초라면 1억번 연산이니 최대 N log N 일 것이라고 생각하였다. sorting 한 번으로 구할 수 있다는 소리인데... 도저히 그리디로 풀 방법이 떠오르지 않아 질문 게시판의 도움을 얻으니 배열에서 다음에 오는 숫자가 기존 숫자들의 합보다 작으면 다음에 오는 숫자까지 더한 값까지 모든 수를 나타낼 수 있다 라는 힌트를 얻었고 이를 증명하고자 한다. Prove S(k) = ∑a[k] 이고 S(K)는 1 ~ S(K)까지 모든 수를 표현할 수 있을 때, S(k) + a[k+1]는 S[k] + a[k+1]까지 모든 수를 표현할 수 있다. Basis S(1)..
[백준/C++/KOI] 25381번 ABBC 문제를 처음 읽었을 때 그냥 그리디하게 풀면 되지 않나? 라는 생각이 들어 제한조건을 보니 S < 300000이었다. 2가지 지우는 방법을 모두 실행한다고 가정하여도 2 * 300000 이라 시간제한이 너무 널널해 잘못된 풀이인가? 하고 고민했다. 3초면 n logn 풀이가 있는 것인가 하고 고민하였는데 아무리 생각해도 그리디로 풀릴 것 같아서 편하게 짠 첫 코드는 5점을 맞았다. 처음 짠 코드는 2번 예제에 문제점을 해결할 수 있도록 뒤에서부터 C의 갯수를 세고 C의 앞에 B가 있다면 지워주는 방식을 생각했다. 지운 B의 위치를 bool로 체크해준 후 A를 세고 A의 앞에 B가 있다면 지우는 형식으로 짰었다. 틀린 이유를 고민하다가 발견한 반례는 BABC였다 CB를 먼저 지우면 A가 혼자 떨어지기 때문..

티스토리툴바