본문 바로가기

알고리즘 문제/Programmerse42

[programmers][월간 코드 챌린지 시즌1] 스타 수열 문제 : programmers.co.kr/learn/courses/30/lessons/70130 조건들 중 정답에 가장 큰 영향을 끼치는건 스타 수열의 교집합 숫자이다. a 배열을 탐색하면서 같은 수를 가지는 배열 인덱스를 저장한다. 즉, numbers 2차원 배열을 만드는데 numbers[number] 는 a 배열에서 number 값을 가지는 인덱스들을 저장한다. [5,2,3,3,5,3]을 예로들면 numbers[2] = {1}, numbers[3] = {2,3,5}, numbers[5] = {0,4}가 저장된다. 이제 numbers 배열을 탐색하면서 number의 짝이 최대 몇개나오는지 구하고 이들 중 최대값이 정답이 된다. [0,3,3,0,7,2,0,2,2,0]을 예로들어보자. numbers 배열을.. 2020. 11. 8.
[programmers][월간 코드 챌린지 시즌1] 이진 변환 반복하기 문제 : programmers.co.kr/learn/courses/30/lessons/70129 s에는 '1'이 최소 하나 포함되어 있다고 하는데 그럼 s가 "0"이 될 가능성이 없다는 뜻이다. 이진법으로 변환하면 나올 수 있는 한자리를 가진 문자열은 "0", "1"인데 "0"은 나올 수 없다고 제한사항에 있기 때문에 s 길이가 1인 경우 문자열은 반드시 "1"이 된다. 따라서 반복문 종료조건을 s 길이가 1보다 큰 경우로 잡았다. => 해당 반복문 반복횟수를 cnt라 한다. s 문자열을 탐색하면서 '0'의 개수를 센다. 이를 0의 총 개수를 저장하는 변수(let, zeroCnt) 1에 더해서 갱신해준다. x의 모든 0을 제거한 뒤 x의 길이를 c 라고 한다면 결국, x(= 문자열 s)의 총 길이에서 0.. 2020. 11. 7.
[programmers][월간 코드 챌린지 시즌1] 내적 문제 : programmers.co.kr/learn/courses/30/lessons/70128 배열 a, b 길이를 N이라 할 때, N만큼 반복하면서 a[i] * b[i]의 합을 구해서 반환한다. 시간복잡도는 O(N). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%EB%82%B4%EC%A0%81.cpp 2020. 11. 7.
[programmers][월간 코드 챌린지 시즌1] 트리 트리오 중간값 문제 : programmers.co.kr/learn/courses/30/lessons/68937 트리의 지름을 구하는 문제의 심화과정. 임의의 노드(let, v1)에서 dfs를 한 번 돌려서 가장 먼 노드(let, v2)를 구한다. (첫번째 BFS) v2 노드에서 가장 먼 노드들을 구한다. (두번째 BFS) 이 때 구한 가장 먼 노드들과 v2 노드의 거리가 트리의 지름이 된다. 만약 가장 먼 노드들이 복수 개(let, d1, d2)라면 f(v2, d1, d2)를 선택하면 이들의 중앙값은 트리의 지름이 되므로 정답은 트리의 지름이 된다. v2 노드에서 가장 먼 노드(let, v3)가 한 개라면 한 번 더 BFS를 돌려야한다. 왜냐하면 v2를 지름의 끝으로 트리의 지름을 만드는 노드들을 구했을 때는 v3 노.. 2020. 10. 18.
[programmers][월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기 문제 : programmers.co.kr/learn/courses/30/lessons/68936 크기가 2인 answer 배열을 하나 만들고 각각 0, 1일 때 크기를 저장한다. arr[sx~ex][sy~ey] 를 탐색하면서 모든 수가 같은지 확인하고 같다면 answer 배열을 갱신하고 같지 않다면 배열을 4분할로 나눠서 다시 판단한다. 이 때 n은 확인하고 있는 배열의 크기로 ex - sx값이라 한다. 1. arr[sx ~ ex - n/2][sy ~ ey - n/2] 2. arr[sx + n/2 ~ ex][sy ~ ey - n/2] 3. arr[sx ~ ex - n/2][sy + n/2 ~ ey] 4. arr[sx + n/2 ~ ex][sy + n/2 ~ ey] 이를 매열 크기가 1일때까지 반복하고 배.. 2020. 10. 17.
[programmers][월간 코드 챌린지 시즌1] 3진법 뒤집기 문제 : programmers.co.kr/learn/courses/30/lessons/68935 string third; while(n > 0) { third += n % 3; n /= 3; } int mul = 1; int answer = 0; // 뒤에서부터 탐색 for(int i=third.size()-1; i>=0; i--){ answer += mul * third[i]; mul = 3 * mul; } n이 0이 될때까지 n에 3나머지 연산한 결과를 문자열 앞에서부터 추가하고 n에 3을 나눈다. n이 0이 되었을 때의 문자열이 n을 3진법화한 결과이고 이를 앞뒤 반전하라고 했으므로 뒤에서부터 3의 i(i는 자리수-1)승을 곱한 수의 총합이 정답이 된다. 시간복잡도는 O(log3N) 소스코드 : g.. 2020. 10. 17.

티스토리툴바