구현 썸네일형 리스트형 백준 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개인 경우만 사용한다. 각 경우에서는 집을 순회하면서 그 집에서 가장 가까운 치킨집의 거리를 더해나간다. 가장 가까운 치킨집 거리 역시 각 치킨집을 모두 돌면.. 더보기 백준 6568 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 비트마스킹을 해볼까? 하고 잡은 문제이다. 제목이 길어서 뭔가 호기심이 생겼다. 문제는 비트연산을 많이 쓰는 구현이다. 메모리 구조를 한번에 입력받고, PC를 움직여 가면서 메모리 안의 명령어들을 실행하면 된다. 크게 삽질을 했던게 3가지 정도 있다. 첫번째로, 메모리를 한번에 받는다는 것. 왜 처음에 한 줄씩 입력받고 매 번 입력받은걸 처리한다고 생각했는지 모르겠다. 두번째, AC와 PC의 범위가 넘으면 리셋된다는 것. 처음엔 AC 범위 넘는것만 구현하고 아 왜 안되지... 이러고 있었는데 PC도 범위가 넘으면 0으로 초기화를 해 줘야 한다... 마지막. Bit 연산을 잘못 생각했다. 마지막 출력 단에서 AC의 값을 각 비트마다 계산해서 1이면 출력하려고 했는데, 마스킹 한 값이 배열 []연산처럼 그 .. 더보기 이전 1 다음
