백준 9934번 : 완전 이진 트리 재귀 호출을 사용해서 left와 right값을 업데이트 해 center값을 정하는 과정으로 생각. //9934 완전 이진 트리 #include #include using namespace std; void findCenter(int * arr, int left, int right) { int center = (left + right) / 2; if (left == right) { cout k; int size_k = pow(2, k) - 1; int* arr = new int[size_k]; for (int i = 0; i > arr[i]; } // 1 6 4 3 5 2 7 findCenter(arr, 0, size_k - 1);..
정답률 높은 문제라 쉽게 생각했는데 생각보다 복잡한 문제였다 ;-; 처음에는 0이 나온 인덱스의 앞의 것만 0으로 바꿔주면 된다고 생각했는데, 0이 나온 갯수만큼 최근의 나온 숫자(0과 인접하지 않더라도)를 모두 없애줘야 했고 #include using namespace std; // 3 0 4 0 // 0 // 1 3 5 4 0 0 7 0 0 6 // 7 int current = -1; void pop(int *arr, int cur) { if (current == -1) { } else { arr[current] = 0; } } void sol(int *arr) { int length = _msize(arr) / sizeof(arr[0]); for (int i = 0; i < length; i++) ..
문제 해결은 간단하다. 인덱스를 신경쓰지 말고 Pi배열을 정렬해 새 배열에다 밑의 주석과 같이 값을 정해주면 된다. C++문제 해결 코드이다. #include #include using namespace std; /* * i는 인덱스, Pi는 해당 인덱스의 value이다 * ! 사실상 '누구' 즉 인덱스는 상관이 없다 * 정렬해서 * 새 배열 만들어서 * 맨 처음 인덱스는 그대로 * 두번째는 처음 + 두번째 * 세번쟤는 처음 + 두번째 + 세번째 */ int main() { int N; cin >> N; //사람 수를 담을 배열 int list[1000] = { NULL }; for (int i = 0; i > list[i]; } // list[1000] = { 3, 1, ..
처음엔 테이프를 이어붙이는 동작을 어떻게 프로그램에서 표현할 수 있을까를 고민했다. '0.5'를 표현해야 한다는 고정관념에 사로잡혀 한참을 고민했다. 그러다 배열의 한 메모리를 '구멍' 자체로 생각하니 0.5 같은 건 생각할 필요가 없어졌고, 배열과 파이프를 동일시하여 생각하기로 하였다. 구현 알고리즘과 의사코드는 다음과 같다. 1. 파이프 배열을 생성해 구멍이 생긴 부분의 값을 true로 바꾸어준다. 2. for문을 배열의 처음부터 순차적으로 돌며 맨 처음 true인 부분을 만나면 먼저 false처리 해주고, 그 부분에서 테이프의 길이만큼의 범위에서 true 인 부분이 있는지 이중 for문을 통해 관찰한다. 3. 만약 이중 for문에서 물이 새는 부분이 또 있으면 그 부분을 false 처리하여 중복 동..
역시 '최소한' 즉 최적의 답을 찾는 그리디 알고리즘 문제, 반례를 찾지 못하는 틀린 코드만 계속 만들어 내었던 문제인 것 같다. 먼저 생각한 알고리즘은 다음과 같다. // 레벨 점수를 list에 '반대로' 담아 레벨이 높은 순대로 정렬한다. while(비교할 하위 레벨이 NULL이 아닌 경우 if(list[i] > list[i+1]) 넘어가 else count+=(list[i + 1] - list[i] + 1) list[i+1] = list[i] - 1; i++; 이런 의사 코드로 만들어진 코드는 다음과 같다. int main() { int count = 0; int list[100] = { NULL }; int N; cin >> N; //4 for (int i = 0; i < N;i++) { cin ..
문제 해결 알고리즘 1. list에 입력한 바이너리 문자열을 넣는다. 2. 0과 1중 무엇을 뒤집을 지 결정하는 잣대로 연속된 1과 0의 개수를 세도록 한다. 3. 어떻게 연속된 1과 0의 개수를 세느냐 - for문에서 list[i]와 list[i+1]의 변화가 있으면 count, 없으면 넘어가도록 - 0과 1을 구분하기 위해 cnt0, cnt1 변수를 따로 저장하고, list[i+1]이 0이면 cnt0++, 1이면 cnt1++를 실행한다. 4. cnt1와 cnt0중에 적은 것을 출력한다. #include #include using namespace std; int main() { int cnt1, cnt0; char s[1000000]; cin >> s; if (s[0] == '1') { cnt1 = ..
문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..
