비트 연산5 [Baekjoon] 2580번: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당 문제 해결 과정 착안 빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해.. 2023. 12. 11. [Baekjoon] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 해결 과정 착안 $N^2$ 개의 동전의 초기 상태로부터 뒷면(T)인 동전의 갯수가 최소가 되도록 행 또는 열을 뒤집는 경우를 찾기 위해서는 가능한 모든 경우를 확인해보아야 한다. 이때, 행이나 열을 뒤집는 동작을 수행할 때 선택된 행과 열 중에서 어느 것을 먼저 뒤집더라도 결과가 동일하므로, 편의상 항상 행을 먼저 다 뒤집은 다음에 열을 뒤집는 경우만 살펴볼 수 있다. 행 또는 열을 뒤집.. 2023. 12. 9. [Programmers] 다음 큰 숫자 https://school.programmers.co.kr/learn/courses/30/lessons/12911 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 비트 연산을 활용하여 아래의 과정을 통해 규칙에 따라 주어지는 수 $N$의 다음 숫자를 구하고자 하였다. $N$을 이진법으로 표현하였을 때, 가장 오른쪽에서부터 시작하여 왼쪽 방향으로 '01' 비트가 처음 등장하는 부분을 찾는다(아래 코드의 while문). 해당 '01' 비트를 10으로 바꾼다(아래 코드의 while문 다음의 코드 두 줄에 해당). 해당 '01' 비트보다 오른.. 2023. 8. 15. [Programmers] 이진 변환 반복하기 https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구한 것과 같이, 주어진 문자열에서 0을 제거하면서 횟수를 계산하고 0을 제외한 나머지 문자열의 길이를 이진법으로 변환하는 과정을 반복하면서 변환 횟수를 계산한다. 구현 십진법의 숫자를 이진법으로 변환하는 과정은 비트 연산을 활용하여 구현하였다. [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using na.. 2023. 7. 30. [Baekjoon] 14891번: 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 해결 과정 착안 문제에서 요구하는 출력 형식에서 힌트(?)를 얻었는데, 톱니바퀴의 각 8 개 톱니의 N극, S극 상태를 비트 형태로 저장하고 비트 연산(bitwise operation)을 활용하여 문제를 해결하고자 하였다. 비트 연산을 사용하고자 한 곳은 아래와 같다. 톱니바퀴 정보에 대한 입력 처리 톱니바퀴의 회전 이웃한 톱니바퀴가 서로 맞물려 있는지를 판정 문제에서 출력으로 요구하는.. 2023. 7. 3. 이전 1 다음
