본문 바로가기

백준

백준 2470 두 용액 이진 검색 유형의 문제를 풀어보자. 첫 문제는 가볍게 골드5로 잡았다. 이것과 유사한 문제로 세 가지 용액을 섞는 문제가 있었다. 그 때와 유사하게 생각을 해 봤다. 근데 이 문제는 그냥 두개의 용액만 가지고 계산을 하기만 하면 된다. 간단하다. 1부터 n 까지 순회하면서 해당 인덱스 + 1 ~ 끝까지 값들을 이진 탐색으로 훑는다. 현재 값(i, 1~n) 과 탐색하는 값(j, i+1 ~ n) 의 합이 0보다 크면 뒤의 절반, 0보다 작으면 앞의 절반으로 계속 계산해나간다. low와 high가 지나칠때까지 검색을 해서, 0과 가장 인접한 합 상태를 갱신한다. 이외에 출력할 때, 순서를 맞춰 출력하는 것 외에 특이사항은 없다. #include #include #include int main() { int n.. 더보기
백준 1112 진법 변환 구현 문제이다. 근데 그냥 빡 하고 부딛히는 구현이 아닌, 수학적인 방법론을 잘 찾아서 구현을 해야 하는 문제였다. 진법 변환 자체는 크게 다를게 없다. 진법의 밑 수로 계속해서 나머지 연산을 해주고 그 나머지들을 역순으로 출력하면 된다. 문제는 음수 진법의 경우. 무조건 나머지는 0이 되어야 한다. 따라서 나머지 연산을 재정의 해야한다. a % abs(b) = a % abs(b) (결과가 양수일 경우), a % abs(b) + abs(b)(결과가 음수일 경우, 나누는 수의 절대값을 더해 보수로 만들어준다) 이렇게 재정의된 나머지 연산을 사용해, 나누기 연산도 재정의해준다. a / b = (a - a % b) / b -> 구한 나머지를 뺀 수를 나눠준다. 이렇게 구현을 해 두면, 음수 진법은 잘 구할 수.. 더보기
백준 12904 A와 B 조금 간단한 구현 문제이다. 두 스트링을 받아, 첫 스트링에서 두 가지 연산을 통해 두번째 스트링이 만들어 질 수 있는지 확인하는 문제이다. 여기서, 두 연산이 모두 뒤에 각각 서로 다른 문자를 붙인다는 것에 주목하자. 만들어진(혹은 만들고 있는 과정의) 스트링의 끝을 확인하면, 이 전에 일어났던 연산이 무엇인지 바로 알 수 있다. 그러면, 우리는 원래 스트링에서 반대로 연산을 해 나가 찾고자 하는 스트링이 만들어지는지 확인을 하면 된다. 구현은 진짜 몇줄 안되는 간단한 코드였다. 두 스트링 입력을 받고, T의 뒤 자리를 확인해서 A이면 단순히 해당 문자를 삭제 했고, B이면 삭제 후 스트링을 뒤집어 줬다. T의 길이가 한 루프마나 하나씩 줄어들기에, T의 길이가 0이 될때까지 루프를 돌았다. 문제 조건.. 더보기
백준 2636 치즈 빡 구현 문제를 잡았다. 2D BFS 문제에서 풀듯이 접근해보자 싶었고, 그 접근이 맞았다. 맵 입력을 받고, 테두리를 돌면서 BFS로 탐색을 한다. 상하좌우 탐색을 하면서 빈 공간을 만나면 그 위치도 큐에 넣는다. 만약 치즈를 만나면 그 부분은 공기와 접촉한 부분이므로 표시를 해둔다. 탐색을 하면서 꼭 visited[][] 배열을 채워주자. 테두리 탐색할때나, 큐 안에서 탐색할 때 visited[][] 로 이미 방문한 곳 처리를 하지 않으면 무한루프가 돌거나 연산 속도가 너무 느려질 가능성이 높다. 한번 모든 테두리에서 BFS 탐색으로 접촉면을 표시해준 다음, 전체 위치를 돌면서 녹는 부분을 제거해주고, 치즈 자리수를 세줬다. 치즈 자리수가 0이 되면 모든 치즈가 없어진 것이므로 탐색 종료! 가장 마지.. 더보기
백준 15686 치킨 배달 구현 문제를 풀어보자고 해서 잡은 문제이다. 2D 지도를 입력받고, 치킨 집 중 M개를 선택해 각 집에서 가장 가까운 치킨집 거리들의 합 최소값을 구하면 되는 문제이다. 구현 문제기도 하고, 맵 크기도 50 * 50 = 2500개 셀이라 크지 않아서 전체 탐색으로 구현했다. 처음 맵 입력을 받을 때, 집 위치와 치킨집 위치를 각 벡터에 저장한다. 탐색하는 공간은 전체 치킨집 중에서 어떤 특정한 치킨집들을 선택하는 경우를 비트마스킹으로 탐색했다. 전체 탐색 공간의 수는 2^치킨집의 수 이다. 하지만 이 경우 중에서 선택한 치킨집의 수가(1의 수가) M개인 경우만 사용한다. 각 경우에서는 집을 순회하면서 그 집에서 가장 가까운 치킨집의 거리를 더해나간다. 가장 가까운 치킨집 거리 역시 각 치킨집을 모두 돌면.. 더보기
백준 14939 불 끄기 비트마스킹 분류로 되어있는 문제이다. 처음 접근할때, 모든 스위치 상황을 비트마스킹으로 만들까 했는데, 10*10 맵을 비트마스킹으로 표시하면 이걸 담을 자료형이 마땅치 않아 접었다. 물론 여러개의 변수를 사용해서 만들 수는 있지만, 그렇게까지 해야할까... 싶었다. 문제가 속한 다른 분류에 그리디가 있어서 한번 생각을 꼬아봤다. 맨 윗줄만 탐색하고 나머지는 그때 그때 상황에따라 계산해보자... 첫 줄에 불을 켜냐 끄냐 경우의 수는 2^10이다. 따라서 그 경우의 수 만큼 탐색을 한다. 첫 줄의 상황에 맞게 스위치를 눌러놓고, 다음 줄 부터 마지막 줄 까지는 윗 줄 같은 열이 켜져있을 때 스위치를 누르는 선택을 한다. 이 때, toggle() 함수를 따로 만들어, temp[][]배열에 변경사항을 실행해준.. 더보기
백준 14391 종이 조각 비트마스킹 문제 분류로 잡은 문제이다. 골드 3이라 쉽겠지... 하고 문제 생각을 했는데 뭔가 계속 안풀렸다... 허허허허 질문으로 감좀 잡아봐야겠다 했는데, 제출이 3천명이나 되는데 질문이 3개밖에 없다... 이건 무슨 일인지. 머리 쥐어뜯다가 검색을 해봤다. 역시 좀 신박한 접근이었다. 각 셀의 상태를 0 : 가로로 찢기, 1 : 세로로 찢기 로 표현해서 m*n 개의 상태를 순회하면서 값을 계산한다. 비트마스킹 변수 안의 각 셀 위치는 2D가 아니고 1D이므로 row*m + col 해서 해당 셀이 어떻게 찢어지는지 찾아, 가로탐색할때 가로 값을 측정하고, 세로 탐색할때 세로 값을 측정한다. 모든 경우의 수 일때, 각 row, col을 순회하며 쭉 이어지면 계속해서 숫자를 이어가고, 끊어지면 지금까지 .. 더보기
백준 9328 열쇠 비트마스킹 문제를 푸려고 보는 중, 내가 분명히 풀었던건데 비트마스킹을 쓴 기억이 없어 들고와봤다. 내가 풀었을때는, BFS 탐색을 조금 예외상황을 넣으며 풀었다. 처음 접근할때는, 맵을 곧이곧대로 입력받고 시작 점을 하나 잡아서 구현했었다. 이 경우 벽이 아닌곳을 통해 다른곳으로 이동하는 경우 처리가 너무 빡셌다. 그래서 그냥 맵 주변을 전부 접근가능한 . 로 표시하는 방법을 선택했다. 이 경우, 자연스럽게 BFS탐색으로 해당 케이스가 커버된다. 맵 입력을 받은 뒤, 열쇠 리스트를 입력으로 받아 해당 열쇠로 열 수 있는 문을 전부 갈 수 있는 '.'로 대체해준다. 열쇠 입수 순간에 맵에 표시를 한다는 생각은 차마 못했는데, 다른 솔루션에서 봤다. 입수 키 리스트를 들고, 문을 볼때마다 키 리스트와 대조.. 더보기

티스토리툴바