CS/알고리즘 문제풀이 (8) 썸네일형 리스트형 [BOJ 2482] 색상환 난이도가 있는 dp문제다. 언제나 그렇듯이 dp는 테이블로 시작해서 테이블로 끝난다. dp는 테이블만 잘 설계한다면 물리적으로 내부동작이 어떻게 되든지 상관없이 논리적으로 답이 도출된다. 테이블이 설계가 안된다면 수열을 노가다로 찾아야 하는데 실수할 여지도 많고 시간이 얼마나 걸릴지도 알수 없다. 테이블을 잘 설계하면 이전값들의 결과가 현재값에 영향을 끼쳐야하는 형태가 돼야한다.(끊어지지 않고 이어지는 형태) 서론은 여기까지 하고 이제 이문제를 풀어보자. 일단 d[i][j]는 i개 중에서 j개를 선택하는 경우의 수라고 테이블을 설계했을때 딱 두가지 경우만 생각하면 이문제는 풀린다. 1. 첫번째 색을 포함할 것인가? -> 첫번째를 제외한(이미 뽑았음으로) 나머지 n-1개 중에서 k-1개를 마저 뽑는다. 2.. [BOJ 2293] 동전 1 나는 왜 이문제를 못풀었을까? dp문제를 풀때 규칙이 바로 보이지 않으면 손을 놓고 머리속으로만 풀려고 하는 안좋은 습관이 있다. 규칙이 보이지 않으면 손을 부지런히 움직여서 규칙이 보일때까지 시행착오를 겪으면서 발견해야하는데 발견하지 못할것 같다는 두려움과 손을 놀려야 한다는 귀찮음 때문인것 같다. 그렇다고 머릿속으로만 생각하면 난 천재처럼 머리속에 화이트보드가 있는것도 아니니 초 스피드로 사라지는 휘발성 메모리를 가지고 dp 문제를 풀라고하니 가당치가 않았던 것이다. 고등학교 수열과 마찬가지로 dp는 무조건 규칙 찾기이고 그때 당시 '자기 손으로 지저분하게라도 직접 풀어내는것이 베스트'라는 어떤 수학강사의 말이 다시금 떠올랐다. 다시한번 상기하자 dp는 수열이고 수열의 핵심은 규칙찾기고 노다가를 해서.. [BOJ 11055] 가장 큰 증가하는 부분 수열 다이나믹 프로그래밍에서 가장 중요한것은 테이블을 어떻게 정의하는것이다. 항상 문제를 푼다는 마음이 급해서 테이블 정의를 소홀히해서 오히려 문제를 못풀고 헤매는 경우가 많았다. 따라서 DP 문제는 반드시 테이블을 정의하는것이 시작이라는것을 깨달아야 한다. 테이블에 따라서 문제가 간편해 질수도 복잡해 질수도있다. (일단 테이블이 내가 말하는대로 생각한대로 무조건 동작한다고 가정하자.) 테이블만 잘 설계하면 나머지 조건식들은 적절히 구성해서 답을 도출할수 있다. 수학처럼 점화식으로 떨어지기도 하거나 전에 구했던 식에서 한단계씩 확장하는 모습일수도 있다. 이문제에서는 증가하는 수열의 합인데 DP로 풀지 않는다면 증가하는 이라는 조건을 그때그때 조건식으로 추려내기가 쉽지가 않다. 그렇다면 DP를 이용해서 전단계에.. BOJ 복습용 필수문제 큐 + 코테 팁 인덱스가 헷갈리면 머리로 풀어서 번아웃 오지 말고 노트에 적으면서 진행해라 EASY MODE: 개념 복습용 문제 큐 HARD MODE: 심화 코테용 문제 큐 스택 2493 탑 HARD MODE 6198 옥상 정원 꾸미기 HARD MODE 17298 오큰수 HARD MODE 덱 11003 최솟값 찾기 HARD MODE BFS 4179 불! EASY MODE 7569 토마토 EASY MODE 5427 불 EASY MODE 9466 텀 프로젝트 EASY MODE 2206 벽 부수고 이동하기 EASY MODE 2146 다리 만들기 HARD MODE 1600 말이 되고픈 원숭이 HARD MODE 14442 벽 부수고 이동하기 2 HARD MODE 16933 벽 부수고 이동하기 3 HARD MODE 16920 확장.. [BOJ 1799] 비숍 이문제를 일반적인 백트래킹 방식으로 풀면 N이 최대 10일때 최대 2^100 경우의수가 생겨 시간초과가 된다. 그래서 발상의 비약이 필요한 문제고 그 아이디어는 체스판을 분할하는것이다. 체스판을 보면 흑과 백으로 나뉘어지는데 이것이 비숍의 공격방향과 일치한다. 비숍의 입장에서는 흑과 백은 서로 독립적이라 붙어만 있을뿐이지 서로 영향을 미치지 못한다. 따라서 흑과 백으로 나누면 N이 10일때 N이 5인 체스판 두개로 생각할수 있고 시간복잡도는 2^(25) = 33554432로 충분히 시간안에 해결할수 있는 문제가 된다. 비숍의 공격방향은 대각선이라 BFS같이 상하좌우로 움직이는것과는 달리 약간의 수학적 테크닉이 사용된다. / 방향 대각선은 x+y로 나타낼수있다. \ 대각선은 x-y+n-1로 나타낼수 있다... [BOJ 1600번] 말이 되고픈 원숭이 BFS 문제는 일반적으로 기본문제만 풀수있는 수준과 심화 문제를 풀수있는 수준이 극명하게 갈리는데 이 문제는 바로 그 경계선이 되는 수준의 문제인것 같다. 정답률이 20퍼다. 본인이 번뜩이는 창의성이 부족한 평범한 사람이라면 분명히 이 문제에서 막히게 될것이고 이것은 발상의 비약이 필요한 순간이라고 할수 있다. 물론 내 이야기다. 알고리즘을 풀면서 어떻게 이런 생각을 하는지 감탄을 넘어서 존경하게되는 순간과 희열을 느끼는 순간과 벽을 느끼는 순간이 종종 있는데 이 문제도 그런류의 문제인것 같다. 나 역시 이문제를 좀 고민해보고 답지를 본 입장으로서 새로운 발상에 눈을 뜬 기분이였다. 일단 딱봐도 BFS를 발상하는것은 어렵지 않다. 문제는 원숭이는 말처럼 움직이는 횟수가 최대 K번이기 때문에 일반적인 BF.. [BOJ 2504번] 괄호의 값 이번문제는 스택 괄호쌍의 응용으로 쉽지 않은 문제였다. 다른 사람의 풀이 설명은 알고리즘이 동작하는 것 위주로 설명하는데 나로서는 쉽게 받아들여지지 않았다. 단순히 이 알고리즘 풀이만 외운다면 이 문제야 풀수 있겠지만 응용력은 기를수 없어보였다. 항상 어떤 문제를 풀때 아이디어가 뭐고 어떻게 발상했는지를 모르면 다른문제에 적용을 할수가 없어서 나는 내 언어로 완전히 바꾸고 이해를 해야 하는 타입이였다. 그래야만 한문제를 풀어도 열문제를 푼 효과를 얻을수 있기 때문이다. 모르는 문제를 답지를 보고 풀고 그 아이디어를 제대로 배웠다면 수십가지의 응용들도 해결할 능력을 얻기 때문에 모르는 것 위주로 문제를 풀어야하고 그게 좋은 방향인걸을 스스로 잘 알지만 역시 문제 앞에서 지고 말았다는 생각이 들어 항상 기분.. [BOJ 11003번] 덱을 이용한 최솟값 문제 처음에 이문제를 보고 덱을 이용해서 원소를 앞뒤로 삭제 추가 해주면서 포인터를 이용해서 최솟값만 그때 그때 뽑아주면 된다고 생각했지만 최악의 경우 N은 1000000 인데 시간복잡도가 N^2logN 이 돼서 아무리 최적화 해봐도 통과되지 않았다. 일단 원소가 앞에서는 삭제되고 뒤에서는 추가 되니까 덱을 발상하는것을 어렵지 않았다. 그리고 한칸씩 슬라이딩 윈도우가 지나가면서 변하는 최솟값을 구하는것인데 이부분을 구현하기가 어려웠다. 그래서 답을 확인했고 이번에 덱의 활용법을 새로 배웠다. 일단 한칸씩 이동하기 때문에 덱 전체를 그때마다 sorting하는것은 너무 낭비라는것을 이해해야 한다. 이 부분에서 시간초과가 났다 이미 알고있는 원소를 충분히 활용하면서 최솟값을 찾아내는 방법은 덱의 성질을 이용하는 것.. 이전 1 다음
