본문 바로가기

전체 글

백준 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이 되면 모든 치즈가 없어진 것이므로 탐색 종료! 가장 마지.. 더보기
[문을 편하게 열고 싶다] UID changable tag에 카드 복사하기(완) UID changable 카드가 왔다. 요즘엔 알리에서 산게 되게 빨리 오는것 같다. 옛날에는 주문해두고 잊어먹고 있으면 온댔는데 2주 안쪽으로 온 것 같다. 카드긴 한데 워치 스트랩이랑 폰에 붙이고 쓸거라 태그 스티커를 샀다. 휘뚜루 마뚜루 UID 변경하는 아두이노 코드를 돌려서 복사해봤다. 데모 코드가 라이브러리에 있어서 출입카드의 UID를 복사해보았다.(사진은 임의의 UID로 변경해본 이미지이다) 그러고 집 도어락에 대 보았다... 안된다...ㅠ 어흑 저번 포스팅에서 봤던 앱에서 덤프 & 복사가 되는것 같아 보여서 시도해보았다. 하지만 작동이 안되었다. UID 작성 가능한 태그가 버전이 몇개 있는데, 지원되는게 아니라고 뜨며 작성이 되지 않았다... 그럴줄알고 알리에서 RFID 카드 재작성이 되는 .. 더보기
백준 15683 감시 빡 구현 문제이다. 회전 얘기를 못 듣고 1번은 왼쪽만 볼 수 있고, 2번은 좌우만 볼 수 있고... 로 생각해서 다 구현하고 나니 잘못생각했더라... 문제에서 최소 크기 라는 단어가 있을때 뭔가 이상하네... 했는데 잘 생각했어야 했다... 회전의 경우를 생각해보면, 1번 3번 4번 카메라는 4개의 경우의 수가 있고, 2번 카메라는 2개, 5번 카메라는 1개의 경우의 수가 있다. 그 경우를 DFS로 탐색했다. 카메라가 k개 있다 하면, 탐색은 k 깊이로 이루어지고, 각 카메라가 몇번 카메라인지에 따라 해당 함수 호출에서 갈라지는 개수가 달라지도록 구성했다. 그것 외에는 구냥 구현이다. 진짜 딱 구현 문제라서 뭐라고 설명하기가 그렇다. 카메라가 보는 곳은 각 방향별로 인덱스를 줄이거나 늘려가면서 맵 범위.. 더보기
백준 15686 치킨 배달 구현 문제를 풀어보자고 해서 잡은 문제이다. 2D 지도를 입력받고, 치킨 집 중 M개를 선택해 각 집에서 가장 가까운 치킨집 거리들의 합 최소값을 구하면 되는 문제이다. 구현 문제기도 하고, 맵 크기도 50 * 50 = 2500개 셀이라 크지 않아서 전체 탐색으로 구현했다. 처음 맵 입력을 받을 때, 집 위치와 치킨집 위치를 각 벡터에 저장한다. 탐색하는 공간은 전체 치킨집 중에서 어떤 특정한 치킨집들을 선택하는 경우를 비트마스킹으로 탐색했다. 전체 탐색 공간의 수는 2^치킨집의 수 이다. 하지만 이 경우 중에서 선택한 치킨집의 수가(1의 수가) M개인 경우만 사용한다. 각 경우에서는 집을 순회하면서 그 집에서 가장 가까운 치킨집의 거리를 더해나간다. 가장 가까운 치킨집 거리 역시 각 치킨집을 모두 돌면.. 더보기
백준 14939 불 끄기 비트마스킹 분류로 되어있는 문제이다. 처음 접근할때, 모든 스위치 상황을 비트마스킹으로 만들까 했는데, 10*10 맵을 비트마스킹으로 표시하면 이걸 담을 자료형이 마땅치 않아 접었다. 물론 여러개의 변수를 사용해서 만들 수는 있지만, 그렇게까지 해야할까... 싶었다. 문제가 속한 다른 분류에 그리디가 있어서 한번 생각을 꼬아봤다. 맨 윗줄만 탐색하고 나머지는 그때 그때 상황에따라 계산해보자... 첫 줄에 불을 켜냐 끄냐 경우의 수는 2^10이다. 따라서 그 경우의 수 만큼 탐색을 한다. 첫 줄의 상황에 맞게 스위치를 눌러놓고, 다음 줄 부터 마지막 줄 까지는 윗 줄 같은 열이 켜져있을 때 스위치를 누르는 선택을 한다. 이 때, toggle() 함수를 따로 만들어, temp[][]배열에 변경사항을 실행해준.. 더보기

티스토리툴바