비트마스킹을 위한 비트연산 필수이론 가볍게 정리

1. 비트(bit) 정보를 구분하는 최소 단위로 이진 숫자(binary)를 뜻한다 0,1의 값을 가지며 True/False나 on/off같은 2가지 상태를 나타낼 수 있다 10진수를 2진수로 바꾸면 해당 10진수에 대응하는 하나의 비트열을 얻는다 2. 비트연산 - 비트연산은 비트열의 같은 위치끼리만 연산함 2-1) &(and) 비트 단위로 and연산을 수행 비트가 둘다 1이면 1이고, 하나라도 0이면 0인 연산 & 연산은 위 표에서 특징을 자세히 살펴보면.. 1) 0과 and연산은 무조건 결과가 0이다 0&0 = 0 0&1 = 0 2) 1과 and연산은 나머지 비트를 그대로 가져온다 1&1 = 1 1&0 = 0 2가지 성질을 잘 이용하면.. 3) 어떤 비트열에서, 특정 부분을 0으로 만들고 싶다면.. 나..

• format_list_bulleted 비트마스킹
• · 2022. 10. 23.
• textsms

다이나믹 프로그래밍의 기본이 되는 동전 거스름돈 문제 해법 배우기

1. 문제 사용할 수 있는 동전이 1원,4원,6원이 있다. 거스름돈 8원을 내주기 위해 사용할 수 있는 최소 동전의 개수는? 그리디 방법으로 접근하면, 가장 큰것부터 내주면 최소라고 생각할 수 있으니까, 6원, 1원, 1원 그러나 실제 최적해는 4원, 4원으로 2개이다 그리디 방법이 항상 최적해를 보장해주지 않아서, 다른 방법으로 문제를 해결할 필요가 있다 - 완전 검색(백트래킹 이용가능) - 다이나믹 프로그래밍 2. 재귀 알고리즘 3가지 동전 각각 선택하면 작은 부분문제가 생긴다 1원짜리 동전을 선택하면 >> 7원에 대한 최적해 + 1원 1개 >> 7원에 대한 최적해는 1원,4원,6원으로 다시 나눌 수 있음 4원짜리 동전을 선택하면 >> 4원에 대한 최적해 + 4원 1개 6원짜리 동전을 선택하면 >> ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 22.
• textsms

다이나믹 프로그래밍 - 최장 증가 수열(LIS)을 찾는 알고리즘 배우기

1. 문제 어떤 수열이 왼쪽에서 오른쪽으로 순서대로 나열된다. 3,2,6,4,5,1.... 만약 이러한 나열된 순서를 유지하면서, 크기가 점진적으로 커지면서, 가장 긴 부분수열은 어떻게 찾을 수 있을까 이러한 부분수열은 연속적으로 고를 필요는 없다. 예를 들어 위 수열에서 3,4,5는 크기가 점점 커지는 부분수열이다. 2. 완전 검색 단순하게 완전 탐색을 수행해서 찾아낼 수도 있다 주어진 수열의 모든 부분집합을 구한다. 부분집합의 원소들이 증가하는 수열인지 검사한다. 증가하는 수열일때, 부분수열의 길이의 최댓값을 갱신한다. 당연히, 부분집합의 크기가 긴 것부터 조사하면, 처음으로 찾게되는 증가수열이 가장 긴 증가수열일 것이다. #완전탐색으로 최장증가 부분수열 찾기 s = [3,2,6,4,5,1] n = ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 20.
• textsms

배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기

1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 19.
• textsms

회의실 배정 문제 응용하기 -모든 수업을 가능하게 하는 회의실의 수는-

1. 문제 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si = 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다 근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다 어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다 먼저 가..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 18.
• textsms

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median

1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결론부터 말하자면, (크기와는 무관하게) 항의 순서대로 수열이 주어질때 최대힙에 들어간 원소의 수와 최소힙에 들어간 원소의 수가 서로 같을 때는 최대힙에 수를 넣어주고 최대힙의 원소의 수가 최소힙의 원소의 수보다 1개 더 많을때는 최소힙에 수를 넣어준다 즉 항상 최대힙 > 최소힙 > 최대힙 > 최소힙 >.. 으로 번갈아가면서 수를 넣어준다. 힙은 완벽하게 정렬해주지는 않지만, 루트에는 최소힙이면 힙에 들어간 원소들 중 최솟값이, 최대힙이면 힙에 들어간 원소들 중 최댓값이 온다는건 확실하다 최대힙에 원소를 넣으면 최대힙..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2022. 10. 18.
• textsms