Bull

학교에서 배운 힙소트 정리 코드 아카이브 용.이론을 안다는 전제하에 코드만 읽는다.def heapify(arr,n,i): key = i l = key*2+1 r = key*2+2 # 왼쪽 자식 노드 검사 if l arr[key]: largest = l else: largest = key # 오른쪽 자식 노드 검사 if r arr[largest]: largest = r # 바뀐 게 있다면 자식 노드와 값을 바꾸고 해당 자식 노드를 검사 if largest != key: temp = arr[largest] arr[largest] = arr[key] arr[key] = temp heapify(arr,n,largest)# 절반부터 하는 이유는 절반보다 위..

문제1019: 책 페이지N이 36이라면 1~36페이지까지 즉 1,2,3,...35,36에 나오는 모든 숫자를 다 세는 것이다.설명각 자리 수 마다 검사하여 모든 경우의 수를 구한다. 1234라는 N이 주어졌을 때 1,2,3,4 모두 검사하는 것이다.1의 자리 수를 검사할 때 1의 자리를 0~9까지 모두 바꿔보는 것이다. 그리고 일의 자리를 제외한 나머지 부분을 보는 것이다.주석을 보고 숫자 디버깅으로 이해하는 게 편할 것이니 포괄적인 설명은 포기한다. (포괄적으로 말하기가 어려워서)1204일 때 0104~1204 (0004는 불가, 다른 숫자 과정에서 겹침.)1214일 때 0014~12141224일 때 0024~12241234일 때 0034~1134 | 1230,1231,1232,1233,12341244..

오른쪽 1 제거// C++#include #include int main() { unsigned int num = 0xFFFFFFFF; while (num > 0) { std::cout (num) (num) num -= num & -num 혹은 num = num & (num - 1) 을 해주면 된다. # 결과1111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111001111111111111111111111111111100011111111111111111111111111110000111111111111111111111111111000001111111111111111..

Baekjoon 2143문제숫자 T가 주어지고 배열 A와 B가 주어진다. 여기서 부 배열이라는 개념이 있는데 A[i], A[i+1], ..., A[j] 와 같이 연속된 배열을 부배열이라고 한다. A[13]까지라고 한다면 A[7], A[8], A[9], ... A[13] 도 가능하고 A[2], A[3]도 부 배열이라고 할 수 있다. 문제는 A의 부 배열과 B의 부 배열이 합해서 T가 되는 경우의 수를 구하는 것이다.예를 들어 본문의 내용과 같이 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] = ..

Baekjoon 1806문제제목처럼 부분합을 구하는 문제이다.1,2,3,4 배열이 있을 때, 1 2 3 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 3 1 2 4 2 3 4 1 2 3 4와 같이 모든 조합이 가능 한 원소의 합이다.이 집합의 원소들의 합이 S 이상이 되는 것 중 원소가 연속되어 있고 짧은 것을 찾는 것이다.입력첫 번째 줄에 수열의 길이 N과 부분합 S가 주어진다. (10 ≤ N , 0 )두 번째 줄에 길이 N인 수열이 주어집니다. 수열의 각 원소는 10,000 이하의 자연수이다.출력합이 S 이상이 되는 가장 짧은 부분 수열의 길이를 출력합니다. 만약 그러한 부분 수열이 없다면 0을 출력한다.아이디어이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용한..

https://www.acmicpc.net/problem/13913문제0 1 2 3 ... 100000 으로 이루어진 일자형 길에 x+1, x-1 2*x로 움직일 수 있다고 했을 때 목적까지 가는 최단 경로를 구하는 문제이다.아이디어단순 BFS문제이다. 하지만 visit으로 최단 경로보다 이후에 간 인덱스는 방문처리하여 다시 방문하지 않도록 한다. 여기까지는 스스로 짰지만 이후에도 메모리 초과가 걸렸다.왜냐하면 최단 경로를 vector를 사용하여 리스트처럼 저장을했는데이는 상당히 많은 배열을 큐에 저장하기 때문이다.단순하게 생각해보면 벡터의 크기가 1에서 100000까지인데 방문한 인덱스를 제외하면 최대 1에서 33333까지 3개씩 저장해 나갈 것이다.(1,2,2,2,3,3,3,4,4,4....) 그러면..

https://www.acmicpc.net/problem/9019문제원문에 나오는 D, S, L, R 연산을 구현하여 A, B입력 시 A→B가 될 때 까지 어떤 연산을 해야하는 지 출력해야 하는 문제이다.아이디어BFS를 통해 D, S, L, R, DD, DS, DL, DR, SD, SS, SL, SR, ...처럼 레벨 단위로 숫자를 확인한다. 여기까진 OK. 하지만 문자열의 제한이 없기 때문에 DSLDLSDRRSRSDSL... 같이 긴 숫자는 Queue에 메모리초과가 발생한다.숫자는 0~10000미만이다. 이것을 활용하여 10000까지 visit을 확인하여 이미 확인한 숫자는 확인하지 않는다. 또한 자료형에 대해서도 short로 바꿔줄 수 있다. int를 쓰면 틀리는 지는 확인해보지 않았지만 일단 sho..