본문 바로가기

전체 글

백준 11066 파일 합치기 오랜만이다. 역시 DP 문제이다. 처음 접근했을때는 어 이거 저번에 풀었던 행렬 곱셈 순서랑 너무 비슷한데? 해서 최대한 풀이를 보지 않고 접근해보았다. 일단 dp[i][j] 배열은, i번째 장에서부터 j번째 장 까지 합친 비용의 최소값이다. 추가로, sum[i] : 0 ~ i번째 원소까지 누적합을 저장하는 배열도 선언해준다. 그럼 이제 몇개의 예시를 돌려보자. dp[i][i] = sum[i] - sum[i - 1] dp[i][i+1] = sum[i + 1] - sum[i - 1] dp[i][i+2] = min(dp[i][i] + dp[i+1][i+2], dp[i][i+1] + dp[i+2][i+2]). 만약 1~10 장의 합치는 개수를 구하고 싶으면(dp[1][10]), dp[1][1] + dp[2][.. 더보기
[문을 편하게 열고 싶다] 스마트폰/갤럭시 워치로 문을 열어보자(실패기) 작년 11월에 이사를 온 집은 공동현관을 열고 올라와 집 대문을 여는 2번의 과정이 필요하다. 하지만 이게 귀찮다. 공동현관이 터치로 입력하게 되어있는데 약간 확률론적으로 터치를 인식한다. 물론 오터치를 방지하기 위한 구현인것 같지만, 그래도 한번 인식이 안되면 한글자만 지울 수 있게 하는 기능이 없는것은 너무했다. 물론 카드키가 있다. 하지만 나갈때/들어갈때 두번 쓰겠다고 카드 하나를 들고 가는것은 또 너무 귀찮다... 이정도면 필요 / 사치 판별기에서 필요에 속하지 않을까?(아무튼 답은 정해뒀다. 필요하다.) 그렇다면 솔루션을 찾아본다. 겁나 비싼 아파트는 유저 등록을 해두고 UWB를 사용해서 각 유저 기기가 공동현관문에 접근시 자동으로 인식하는 방식도 있다고는 들었다. 실제 구현이 되어있을지는 모르.. 더보기
백준 1520 내리막 길 오늘도 DP 문제이다. 2차원 지도를 입력으로 받아 0, 0 위치에서 N - 1, M - 1 위치까지 경로가 몇개 있는지 찾는 문제이다. DP 없이 그냥 문제 푼다고 생각하면 DFS를 써서 탐색을 돌려버릴 것 같다. 하지만 맵 크기가 작은 편이 아니라 그렇게 돌리면 Timeout이 발생할 가능성이 크다. 처음에 DP 접근을 dp[i][j] = 0, 0에서부터 i, j 까지 경로의 수 라고 생각을 해봤는데 생각을 아무리 해봐도 잘 답이 나오지 않았다. 그러고 한번 뒤집어 접근을해봤다. dp[i][j] = i, j 에서부터 N-1, M-1 까지 경로의 수로 생각을 하고 접근을 했다. 이 방향이 더 좋았던 것 같다. 그리고, dp 배열을 채우는 과정은 DFS로 흘러가게 된다. 현재 픽셀에서, 다음 픽셀을 찾고.. 더보기
백준 11049 행렬 곱셈 순서 어제에 이어 오늘도 DP 접근 문제이다. 이 문제도 학교 알분시간에 한번 다뤘었던 기억이 나는데 꼭 항상 학교에서 한것은 했다는 그 사실만 기억나고 내용은 기억이 나지 않는다... 하하하... DP 문제에서 관건은 문제가 쪼개지는지, 그 문제들의 합이 전체 해가 되는지인것같다. 만약 이 조건이 만족한다면 DP적 접근을 해보는게 좋을 것 같다. 해당 문제는 어떤 특정 부분의 최소값이 전체 최소값의 부분을 차지한다. 따라서 DP적 접근을 하는게 좋아보인다. DP 배열은 dp[i][j]일때, i번째 행렬부터 j번째 행렬까지 곱의 최소횟수를 의미한다. 처음 초기화는 전부 0으로 하고, 이웃한 배열끼리의 곱은 무조건 고정되어있으므로, 0~N-1 배열까지 이웃한 값을 채워줄 수 있다. 이후로는 저번 문제들과는 다르.. 더보기
백준 12865 평범한 배낭 역시 DP 접근 문제이다. 처음 접근은 2*물건의 수 DP 배열을 만들어 물건마다 넣고빼고를 적어두고 다음 물건을 볼 때 두 조건 중 max값을 사용하면 되지 않을까? 싶었는데 머리로 몇번 돌려보니 너무나도 쉽게 전체 탐색이 안되는구나... 하며 고민했다. DP 배열은 물건의 수*가방의 무게 크기로 생성한다. DP[i][j] 는, i 번째 물건까지 사용했을때, j무게 가방에 넣을 수 있는 물건 최대 가치이다. 처음 행은 당연히 첫번째 물건을 넣는 경우이고, 한번 값이 들어가기만 한다. 이후로는 모든 물건을 순회(현재 물건 무게 : curWeight, 현재 물건 가치 : curValue)하면서 DP를 채우게 된다. 매 물건마다 가방 크기를 1씩 늘리면서, 현재 가방 크기가 현재 물건을 넣을 수 있으면 저번.. 더보기
백준 9251 LCS 추석 연휴 끝나고 DP를 해보려고 잡은 문제이다. DP의 개념은 살짝 알고 있고, 관련 문제도 몇 번 푼 적이 있지만 제대로 좀 훑고 싶었다. Dynamic Programming은 문제를 푸는 과정에서 계속 부분부분 정답을 기록해가며 문제에 대한 해답을 풀어가는 방식이라고 생각한다. 근데 이게 나중에 보고 나면 아...~ 하는데 접근하기가 너무 어려운 것 같다. 이번 문제는 두 문자열이 있고, 그 문자열들의 부분 수열 중 가장 긴 공통 부분 수열의 길이를 찾는 문제이다. 처음 DP 쓰고 어 문자열~ 하고 접근했을 때, 1차원 배열을 선언해서, 먼저 받은 문자열을 쭉 스캔하면서 거기 기준으로 다른 문자열 어떤 위치까지 만들 수 있는가를 저장하는 방식으로 작성했다. 근데 아무리 생각해도 그렇게 접근하게 되면.. 더보기
백준 2473 세 용액 바로 이전에 푼 문제보다 조금 쉬운 문제이다. 저번 문제는 3명의 합이 0인 개수를 구하는 문제였고, 이번에는 합의 절대값이 최소인 것만 찾으면 된다. 정말 간단하다. 투 포인터 방향은 쉽게 잡았다. 문제도 유사해서 문제에서 제공하는 테스트케이스는 돌아가게 쉽게 만들었다. 문제는, 악마는 디테일에 있다는 것. 생각없이 int로 만든것을 보고 long long으로 바꿨다. 그래도 특정 %에서 틀렸습니다가 나왔다. 문제질문 보면 다양한 사례가 있더라. int - long long 범위 문제도 많았고, 중간에 특성값 계산할때 절대값 연산을 하는게 편한데 그때 abs() 함수에서 문제가 발생한 사례도 있었다. 컴파일러 구현체마다 std::abs가 아닌 그냥 abs를 int abs(int , int) 이렇게 받을.. 더보기
백준 3151 합이 0 오늘은 좀 쉬운거 잡고 오전에 다른거 해야지 했는데 예상보다 날 많이 괴롭혔다 이 문제가. 투 포인터를 사용하는 나쁘지 않은 편한 문제이다. 처음 보았을 때 정렬을 해두고 어떤 한 원소를 고정해두고 나머지 원소들을 투 포인터로 탐색하며 조합을 찾으면 좋겠다고 생각했다. 처음에는 선정한 한 개를 빼고 나머지들에서 투 포인터 탐색을 구현했다. 그렇게 되니 막 중복으로 찾고 난리가 나더라. 다시 생각해보니 어떤 원소 하나를 정하고 그 다음것부터 마지막까지만 계산하면 되는 문제였다. 그렇게 짜고 나니, 같은 값의 원소가 많이 있을 수 있다는 점이 걸렸다. L과 R이 가르키는 원소가 조합을 만족할 때, 우리는 두가지 상황에 빠진다. 하나는 두 원소가 값이 같을 경우. 이 때는 해당 값이 몇개 있는지 확인하고, k.. 더보기

티스토리툴바