본문 바로가기

백준

백준 1562 계단 수 비트마스킹 문제이다. 근데 또 보니까 DP 문제이다... 으... DP... 이걸 어떻게 구현을 해야하나... 하다가 DFS로 탐색을 돌까 했는데, 탐색 수가 너무 많이 나와 솔루션 나오기 전에 내 복장부터 터질것 같아 그만 뒀다. 머리 쥐어 뜯다가 좀 검색을 해봤다. DP를 사용한 해결 방법이 대부분이었다. 그 중에는 DFS에 DP를 붙인 것도 있고, 단순히 for를 사용하면서 탐색을한 방법도 있었다. 그 중 for 문을 사용한 BFS탐색이 더 마음에 들어 코드를 보면서 다시 짜봤다.. 일단 DP 배열을 선언한다. dp[i][j][b] = 현재 자리수가 i이고, 마지막으로 사용한 숫자가 j이면서 사용한 숫자의 상태가 b 비트마스크일때, 가능한 계단 수 이다. 이제 이걸 i와 j, b를 늘리면서 배열을 .. 더보기
백준 11578 팀원 모집 오늘도 비트마스킹 문제이다. 너무 시간이 늦어 쉬운거를 잡았다. 스스스슥 풀어서 다행이다. 2트만에 패스띄웠다... 학생과 알고리즘 모두 10개까지밖에 안들어온다. 그냥 전체를 순회하면서 돌아도 오래 걸리지 않을 듯 하다. 학생을 입력 받을때, 학생이 풀 수 있는 알고리즘들을 비트마스킹된 값의 배열로 저장을 한다. 이후, 학생이 뽑힐 수 있는 경우의 수(학생이 m번까지 있으므로, 2^m 가지의 수)를 순회하면서, 포함된 학생들이 풀 수 있는것들을 전부 or처리한다. 그 상태가 모든 문제를 풀 수 있는 상태(5 문제이면 ~00011111) 인지 확인하고, 이때마다 최소값을 구해주면 된다. N과 M이 더 많이 커지면 이 방법으로는 되지 않을 것 같다. 경우의 수가 크지 않아 전체 탐색으로도 오래 걸리지 않았.. 더보기
백준 13701 중복 제거 비트마스킹 중에서 무난하게 풀고 자려고 적당한것을 골라봤다. 숫자를 입력받는데, 중복으로 입력된것을 제외하고 주르륵 출력하면 된다. 처음 든 생각은 bool[] 배열을 선언해서 중복이면 true, 중복이 아니면 false 로 체크를 하는 것. bool[] 배열을 사용하는 구현은 정말 쉽게 구현이 되었는데, 바로 메모리 초과가 떴다. 33554432바이트 = 33MB 언저리 이므로 8MB만 허용하는 메모리 용량을 한참 초과한다. 처음엔 bool이 당연히 1bit 크기겠지 했는데 아니었다... 그럼 그냥 한 바이트짜리 변수에 각 비트로 표시하자... 는 생각으로 char배열을 선언했다. 그리고 각 배열의 값과 비트는 입력받은 수를 8로 나눈 몫, 8로 나눈 나머지로 사용했다. 최근 본 OS에서 페이징을 볼 .. 더보기
백준 6568 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 비트마스킹을 해볼까? 하고 잡은 문제이다. 제목이 길어서 뭔가 호기심이 생겼다. 문제는 비트연산을 많이 쓰는 구현이다. 메모리 구조를 한번에 입력받고, PC를 움직여 가면서 메모리 안의 명령어들을 실행하면 된다. 크게 삽질을 했던게 3가지 정도 있다. 첫번째로, 메모리를 한번에 받는다는 것. 왜 처음에 한 줄씩 입력받고 매 번 입력받은걸 처리한다고 생각했는지 모르겠다. 두번째, AC와 PC의 범위가 넘으면 리셋된다는 것. 처음엔 AC 범위 넘는것만 구현하고 아 왜 안되지... 이러고 있었는데 PC도 범위가 넘으면 0으로 초기화를 해 줘야 한다... 마지막. Bit 연산을 잘못 생각했다. 마지막 출력 단에서 AC의 값을 각 비트마다 계산해서 1이면 출력하려고 했는데, 마스킹 한 값이 배열 []연산처럼 그 .. 더보기
백준 1126 같은 탑 DP 문제를 슥 보다가 오우 문제 짧네? 하고 한번 잡아봤다. 근데 플은 괜히 플이 아니더라... 하하... 처음 접근했을때, dp[i]를 i 높이로 탑을 쌓을 수 있는 조건으로 접근했다. dp[i]는 벡터였고, dp[2]는 2 높이를 만들 수 있는 블럭들 상태들을 저장하고 있었다. 루프 돌면서 이전 조합에 지금 블럭을 or 해서 추가하고, dp[i]가 2 이상인 경우 중 최대값을 출력했다. 답은 나왔는데 예상보다 루프가 많아 시간 초과가 떴다. 시간 갈아넣었는데 시간초과가 나와 좀 더 생각해보다가 검색을 좀 해봤다. dp 배열을 진짜 신박하게 잡더라. dp[i][j] = i 번째 블럭까지 썼을때, 두 블럭 높이 차이가 j일 경우 두 탑 중 높은 것의 높이. 로 정의해둔다. 이렇게 되면, i와 j를 늘려.. 더보기
백준 2618 경찰차 좀 어려워 보이는 문제를 잡아봤다. 두 경찰차가 있고, 하나는 1,1에서 나머지 하나는 N,N에서 출발한다. 경찰차가 격자무늬 도시를 돌아다니며 사건들을 해결하는데, 그 과정에서 이동하는 최소값과 경로를 출력하는 문제이다. 처음에 그냥 답이라도 나왔으면 좋겠다 하고 각 사건마다 가장 가까운 경찰차를 이동하면서 문제를 풀었는데, 틀렸다. 당연히 그런게, 만약 두 경찰차가 모두 같은 거리에 떨어져 있으면 이 경우는 어떻게 할지 정의되지 않아 최적해 탐색은 물 건너간다... 머리 쥐어뜯다가 질문 게시판을 탐색해보고 DP 배열 감을 잡았다. dp[i][j] = 경찰차 1이 가장 마지막으로 i번째 사건을 했고, 경찰차 2가 가장 마지막으로 j번째 사건을 했을 때 이동 최소 거리로 정의를 하자. 이렇게 dp를 구성.. 더보기
백준 2098 외판원 순회 백준 문제를 다시 잡아봤다. DP문제에서 진짜 엄청 유명한 문제인 TSP를 풀어보고 싶어서 찾았다. 근데 진짜 TSP 키워드로 구글에서 검색하면 별의 별 곳 응용이 다 나오더라. 가장 많이 보이는게 경로 문제, 최근 드론 배달이 많이 연구 되고 있는데 그쪽 관련된 이미지가 많이 나오는 것 같다. 문제는 심플하다. 유향 가중치 그래프를 인접 행렬로 입력 받아서, 모든 노드를 방문하고 제 자리로 돌아오는 경로를 찾는 것 - 이 문제에서는 비용만 구하면 된다. 처음 접근은 DFS를 사용해서 DP에 저장해가면서 풀어보는 방식이었다. 직전 문제인 도둑질에서도 같은 접근 방법을 사용했었다. 근데 코드 구현 중, 탐색 중간에 되돌아가거나 다음 경로가 없을 때 너무 복잡해져서 엎었다... 그래서 이걸 어떻게 하나..... 더보기
백준 7579 앱 알고리즘 스터디에서 친구가 가져왔던 문제이다. 0-1 Knapsack문제 유형을 보고 잡은 문제라는데, 좀 어려웠다. 그냥 0-1 knapsack 문제로 생각하면, 배낭크기를 메모리로 따져서 col에 M개 열을 만들어 해볼까 했는데 메모리의 최대값이 10000000이라 배열으로 선언을 할 수 없을 것 같다. 그럼 어떻게 할까...? 친구가 풀다가 솔루션을 확인했는데, 그 방식이 너무 신기했다. col을 다른 값을 사용해서 채우는 방법이 있더라. 이 문제 같은 경우에는, col에 cost를 넣어둬 문제를 해결했다. 따라서 dp[i][j] = i번째 앱까지 봤을때, j비용으로 얻을 수 있는 메모리의 크기가 된다. dp 배열의 내용을 한번 보자, [0] [1] [2] [3] [4] [5] [6] [7] [8].. 더보기

티스토리툴바