Machineboy空

https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=csharp

원리배열 A가 정렬되어 있다고 할 때, A の真ん中の要素が k 未満であれば、A の前半分の要素もすべて k 未満であることがわかります。つまり、A の前半分について探索する必要が無くなります。A의 중앙값보다 비교할 요소가 작다면, 나머지 오른쪽 절반의 요소들 보다 작다.逆に、A の真ん中の要素が k より大きければ、A の後ろ半分の要素もすべて k より大きいので、A の後ろ半分について探索する必要が無くなります。A의 중앙값보다 비교할 요소가 크다면, 나머지 왼쪽 절반의 요소들 보다 크다.つまり、「対象とする探索範囲の中央の値」と「探索したい値」を比較することで、探索範囲を半分にすることができます。즉, 탐색 범위의 중앙 값과 탐색하고 싶은 값을 비교하며 탐색 범위를 절반으로 줄일 수 있다!Tipソート済みであること정렬되어 있어야 한다.二分探索..

분할정복(Divide and Conquer)Divide : 큰 문제를 작은 문제로 분할한다.기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.일반적으로 재귀로 구현한다.  백트래킹(backtracking)답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.정확한 시간 복잡도를 구하기 어려움 분할 정복백트래킹주로 재귀적인 방식으로 해결하위 문제를 해결하고 결과를 결합하여 문제를 해결문제 해결을 위해 모든 가능한 선택을 시도한 후,..

1. 회문(Palindrome)ex) "소주만병만주소", "수박이박수", "Madam, I'm Adam", "1234321" 회문을 판단하는 방법? 2. 올바른 괄호 문자열(VPS = Valid Parenthesis String)ex) (()), (())()보통은 스택(Stack)을 사용해서 해결')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지운다. 이때 스택(top)이 비어있거나 '('이 없으면 올바른 괄호 문자열이 아님모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고 비어있지 않으면 올바르지 않은 괄호 문자열임

for this particular purpose라는 뜻의 라틴어 특정 상황에서만 정답이 되고 일반화될 수 없는 해답을 말한다.일반화할 수 없고 재사용이 거의 불가능하다!예시 문제https://machineboy0.tistory.com/223 1813: 논리학 교수 - Ad Hochttps://www.acmicpc.net/problem/1813machineboy0.tistory.com

백준 문제 리스트17466231226091929코딩테스트에서 나올 수 있는 마지막 수학 이론이라고 한다.유클리드 호제법 많이 들어는 봤는데 직접 빼면서 구하는 방법이 참 신기했다.최대공약수를 정석으로 구하지 않고 호제법으로 구하면 시간복잡도가 현저히 낮아짐.

비트연산 활용idx번째 비트 끄기S &= -(1idx번째 비트 XOR 연산S ^= (1 최하위 켜져있는 비트 찾기idx = (S & -S)크기가 n인 집합의 모든 비트를 켜기(1 idx번째 비트를 켜기S |= (1 idx번째 비트가 켜져있는지 확인하기if(S & (1  idx 번째 비트 끄기S &= ~ (1 int S = 18;int idx = 1;S &= ~(1  idx 번째 비트 XOR연산S ^= (1  토글 기능이랑 비슷, 스위치 켜고 끄기처럼 원하는 idx 비트 껐다 켰다 하는 법 최하위  켜져있는 비트 찾기idx = (S & -S) 크기가 n인 집합의  모든 비트 켜기(1  idx번째 비트를 켜기S |= (1 idx번째 비트가 켜져있는지 확인하기if(S & (1 https://exercism.o..