알고리즘 부수기

문제링크 : https://www.acmicpc.net/problem/1967 노드의 개수 n (n-1)개의 간선 정보 (부모, 자식, 가중치) 트리의 지름(트리의 두 정점 간의 거리 중 가장 최대값) 우선, 트리의 가중치가 음수 혹은 0인 경우가 존재하지 않는다면 두 정점간의 거리의 최대값은 리프 - 리프 노드 사이에 존재한다. 이 생각을 시작으로 문제를 접근했다. 루트 노드의 번호는 언제나 1이다. 이 문제는 부분으로 나눌 수 있다. 6번 노드가 루트인 서브 트리의 최대값은 (10+6=16)이고 5번 노드가 루트인 서브 트리의 최대값은 (15+4=19)이다. 그리고 각각 위로 갈 수 있는 최대 경로인 10과 15를 넘겨준다. 다음으로 3번 노드가 루트인 서브트리의 최대값은 5번 노드로부터 받은 (15..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo TestCase ( 0) { arr1[index1] = num1 % 10; index1++; num1 /= (ll)10; } while (num2 > 0) { arr2[index2] = num2 % 10; index2++; num2 /= (ll)10; } int count1 = 0; // 앞자리수부터 차례대로 더하는 변수 int count2 = 0; int cur_num = 0; // 계산중인 자리수 저장하는 변수 // 일의자리 제외 for (int j = index1 - 1; j > 0; j--) { cu..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWczm7QaACgDFAWn 각 버스의 노선 정보가 주어지고 입력되는 정류장 번호에 따라 해당 정류장이 포함된 노선의 개수를 출력하는 간단한 문제이다. 노선의 개수 N (1T; for (int test_case = 1; test_case > N; int A[5000] = { 0 }; int B[5000] = { 0 }; for (int i = 0; i

지금 하고 있는 활동에서 하는게 많아지고 알고리즘 병행하다보니 토이 프로젝트에 조금 소원해진 것 같다. (절대 커밋 안하고 날아가서 멘붕와서 안한거 아님) 오늘 오랜만에 여유가 잠깐 생겨서 커밋 !! IntroActivity 구성 ( 아이콘 및 앱 이름 ) IntroActivity 일정 시간동안 보여준 뒤 핸들러 이용해서 MainActivity로 Intent ! 이렇게 써놓고 보니까 한거 별로 없어 보이는데.. ( 한거 없는게 사실이긴 하지만 ) 그래도 나름 Activity 하나 끝낸 거에 만족 ! 앱 이름이나 아이콘은 나중에 생각해야겠다. 데이터베이스 구성 SQLite 및 권한 설정

문제링크 : https://codeforces.com/contest/1099/problem/D 결론부터 말하자면 틀린 문제이다. 당연하다고 생각하고 여러 가지를 다시 생각해보지 않았기 때문에 제대로 풀지 못했다. - 노드의 개수 (n) - 2번부터 노드의 parent 노드 번호 - 1번부터 노드의 S_v (해당 노드부터 루트까지 경로상에 있는 모든 노드의 value 합) [ 단, 루트의 height을 1이라고 할 때 height이 짝수인 칸은 -1로 주어짐 ] - 해당 트리에서 모든 노드의 value들의 합 중 최소값 (조건에 맞는 트리가 될 수 없을 경우 -1) 문제의 상황은 height이 짝수인 노드들의 루트까지의 sum을 -1로 바꿔버린 상황이다. 즉, height이 홀수인 칸은 맞는 sum들이 들..

문제링크 : https://codeforces.com/contest/1099/problem/C - '?'와 '*'이 포함된 문자열 - 만들고 싶은 문자열 길이 - ?와 *의 기능을 이용해서 원하는 길이로 만들어진 문자열 - 불가능할 경우 Impossible 내가 알고리즘 문제를 풀 때 가장 어려워하는 문자열 가지고 놀기 문제이다. 먼저, '?'와 '*'의 기능을 살펴보자. '?'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있다. '*'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있고 추가로 원하는 개수만큼 복사할 수 있다. 주어진 문자열에서 기호의 기능을 사용해 만들 수 있는 많은 문자열 중 아무거나 하나만 출력해도 된다. 이 조건이 문제를 굉장히 쉬워지게 만들었다. 3가지 경우로 나눠서 ..

문제링크 : https://codeforces.com/contest/1099/problem/B 원하는 개수의 사각형을 만들기 위해 자를 재고 그려야하는 선의 개수의 최소값을 찾는 문제이다. 우선 이해하기 쉽게 문제를 설명해보면, 위 그림에서 빨강색 선은 자를 이용해서 그려야 하는 부분, 검정색은 자 없이도 그릴 수 있는 부분이다. 왜 검정색은 자 없이 그릴 수 있는 부분인가? 이미 같은 x 와 (x+1) 혹은 같은 y와 (y+1)을 이은 선이 존재하기 때문이다. 즉, a'은 a로 인해 자 없이 그릴 수 있고, b'은 b로 인해 자 없이 그릴 수 있게 된다. 마찬가지로 사각형 2개를 만들기 위해서는 아래 그림과 같이 구성되어야 한다. 사각형 2개를 만들기 위해서는 3개의 빨강 선이 필요하게 된다. 이제, ..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT&categoryId=AWS2h6AKBCoDFAVT&categoryType=CODE 이 문제는 산의 높이를 순서대로 저장한 배열에서 극대값을 찾는 문제이다. 산의 높이는 10^9까지 가지만 산의 개수가 50,000개 이하이므로 long long을 사용하지 않았다.(산의 높이를 더하는 문제였으면 long long을 사용해야 한다.) 기본적인 아이디어부터 살펴보자. 극대값이 있고 그 주변을 감쌀 수 있는 범위의 개수를 찾는 문제이다. 순서대로 증가한 값이 극대값 앞에 2개 있고 순서대로 감소한 값이 극대값 뒤에 2개가 있다면..