알고리즘 부수기

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE 없음 100만 이하의 모든 소수 출력하기 "에라토노스의 체"라는 이론을 사용할 것이다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 간단하게 설명하면 우선 100만 이하의 2의 배수를 모두 지운다. 다음으로 3의 배수를 모두 지운다. 진행 중 지워..

문제링크 : https://www.acmicpc.net/problem/14720 우유 가게 수 n n개의 가게 정보 ( 0 : 딸기우유, 1 : 초코우유, 2 : 바나나우유 ) 최대로 마실 수 있는 우유의 개수 역시 단순한 dp 문제이다. 0(딸기우유)번 가게일 경우 이전의 2(바나나우유)번 가게의 값 중 Max +1을 하고 1(초코우유)번 가게는 이전의 0(딸기우유)번 가게의 값 중 Max +1, 2(바나나우유)번 가게는 이전의 1(초코우유)번 가게의 값 중 Max +1을 하면 된다. 여기서 주의해야할 예외는 1. 맨 처음에는 딸기우유를 한 팩 마신다. 이다. 즉, 1과 2가 나오더라도 0이 나오기 전이라면 값을 갱신해서는 안된다. 예외처리를 해줘야 하는 경우는 2..

문제링크 : https://www.acmicpc.net/problem/11727 길이 n이 주어진다. 2 x n 크기의 직사각형을 채우는 방법의 수 (%10,007) 계단을 1칸 2칸씩 오를 때의 경우의 수와 같은 전형적인 dp문제이다. 따라서 (2 x (n-1))의 경우와 (2 x (n-2))의 경우를 더해주면 된다. 여기서 주의해야할 점은 (2 x (n-1))의 경우를 2번 더해줘야 한다는 점이다. (즉, x 2) 이유는 2 x n 크기의 직사각형을 채울 수 있는 방법을 시뮬레이션 해보면 알 수 있다. 위 사진에서 ?가 그려진 직사각형을 2 x n 크기로 보자. 그러면 아래 그림처럼 1칸 적은 직사각형에서 2 x 1을 더하는 경우와 2칸 적은 직사각형에서 2 x ..

문제링크 : 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

문제링크 : 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가지 경우로 나눠서 ..