본문 바로가기

전체 글

백준 14391 종이 조각 비트마스킹 문제 분류로 잡은 문제이다. 골드 3이라 쉽겠지... 하고 문제 생각을 했는데 뭔가 계속 안풀렸다... 허허허허 질문으로 감좀 잡아봐야겠다 했는데, 제출이 3천명이나 되는데 질문이 3개밖에 없다... 이건 무슨 일인지. 머리 쥐어뜯다가 검색을 해봤다. 역시 좀 신박한 접근이었다. 각 셀의 상태를 0 : 가로로 찢기, 1 : 세로로 찢기 로 표현해서 m*n 개의 상태를 순회하면서 값을 계산한다. 비트마스킹 변수 안의 각 셀 위치는 2D가 아니고 1D이므로 row*m + col 해서 해당 셀이 어떻게 찢어지는지 찾아, 가로탐색할때 가로 값을 측정하고, 세로 탐색할때 세로 값을 측정한다. 모든 경우의 수 일때, 각 row, col을 순회하며 쭉 이어지면 계속해서 숫자를 이어가고, 끊어지면 지금까지 .. 더보기
백준 9328 열쇠 비트마스킹 문제를 푸려고 보는 중, 내가 분명히 풀었던건데 비트마스킹을 쓴 기억이 없어 들고와봤다. 내가 풀었을때는, BFS 탐색을 조금 예외상황을 넣으며 풀었다. 처음 접근할때는, 맵을 곧이곧대로 입력받고 시작 점을 하나 잡아서 구현했었다. 이 경우 벽이 아닌곳을 통해 다른곳으로 이동하는 경우 처리가 너무 빡셌다. 그래서 그냥 맵 주변을 전부 접근가능한 . 로 표시하는 방법을 선택했다. 이 경우, 자연스럽게 BFS탐색으로 해당 케이스가 커버된다. 맵 입력을 받은 뒤, 열쇠 리스트를 입력으로 받아 해당 열쇠로 열 수 있는 문을 전부 갈 수 있는 '.'로 대체해준다. 열쇠 입수 순간에 맵에 표시를 한다는 생각은 차마 못했는데, 다른 솔루션에서 봤다. 입수 키 리스트를 들고, 문을 볼때마다 키 리스트와 대조.. 더보기
백준 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를 구성.. 더보기

티스토리툴바