본문 바로가기
반응형

PS 문제 풀이/Algospot16

[Algospot] 알고스팟 GRADUATION 졸업학기 출처: https://algospot.com/judge/problem/read/GRADUATION Approach ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com 과목의 수 = 4 들어야 할 과목의 수 = 4 학기 수 = 4 한 학기에 최대 들을 수 있는 과목의 수 = 4 - 첫번째 학기) 0, 3 과목 이수 - 두번째 학기) 1 과목 이수 - 세번째 학기) 2 과목 이수 graduate(int semester, int taken) = 현재 학기가 semeter 이고,.. 2021. 3. 1.
[Algospot] 알고스팟 INSERTION 삽입 정렬 뒤집기 출처: https://algospot.com/judge/problem/read/INSERTION Input 2 5 0 1 1 2 3 4 0 1 2 3 Output 5 1 4 3 2 4 3 2 1 뒤에서 부터 문제를 풀어 나갑니다. ① [1 3 4 5 2]에서 2를 왼쪽으로 3칸 옮겨서 [1 2 3 4 5]가 만들어 졌으므로 2를 다시 오른쪽으로 3칸 움직이면 됩니다. 즉, 2보다 큰 숫자가 3개 존재하고 있었습니다. A[N-1] = 2 ① [1 3 4 5]는 [1 4 5 3]에서 3을 왼쪽으로 2칸으로 옮긴 것이므로 3을 다시 오른쪽으로 움직이면 A[N-2] = 3 ② [1 4 5]는 [1 5 4]에서 4를 왼쪽으로 1칸 옮긴 것이므로 4를 오른쪽으로 한칸 이동합니다 A[N-3] = 4 ③ [1 5]는 .. 2021. 3. 1.
[Algospot] 알고스팟 NERD2 너드인가, 너드가 아닌가? 2 출처: https://algospot.com/judge/problem/read/NERD2 Input 2 4 72 50 57 67 74 55 64 60 5 1 5 2 4 3 3 4 2 5 1 Output 8 15 x, y좌표를 좌표명면상의 점으로 표현 → (x, y)를 직사각형의 우측 상단 좌표로 생각. 새로운 신청자(좌표)가 추가될 때마다 기존 영역에 지배 여부(isDominated)로 너드 여부 확인 ※ 한 점 a가 다른 점 b보다 오른쪽 위에 있을 때, a가 b를 ‘지배한다’고 표현 - 기존의 좌표(a, b) 중에서 새로운 좌표(x, y)와 비교해서 x < a && y < b를 판단 즉, 사각형 영역에서 새로운 좌표보다 우측 상단에 위치한 꼭지점이 있는지 확인하는 것입니다. ① 새로운 좌표가 너드인 .. 2021. 3. 1.
[Algospot] 알고스팟 FORTRESS 요새 출처: https://www.algospot.com/judge/problem/read/FORTRESS Input 2 3 5 5 15 5 5 10 5 5 5 8 21 15 20 15 15 10 13 12 5 12 12 3 19 19 2 30 24 5 32 10 7 32 9 4 Output 2 5 성벽들이 서로 닿거나 겹치지 않는다는 조건에서 계층적 구조를 알 수 있습니다. (두 원은 서로 떨어져 있거나 하나의 원이 다른 하나의 원안에 있습니다.) ▶ 성벽들간의 간의 포함 관계를 트리로 표현 가능 ① 트리 생성 0번 성벽은 다른 모든 성벽을 포함하는 외벽이므로, 트리의 루트로 정의 0번 성벽 바로 밑에 들어갈 성벽들을 찾고, 각각의 성벽을 루트로 하는 서브트리를 재귀적으로 생성 원(성벽)들을 모두 비교하면서.. 2021. 3. 1.
[Algospot] 알고스팟 TRAVERSAL 트리 순회 순서 변경 출처: https://algospot.com/judge/problem/read/TRAVERSAL Input 2 7 27 16 9 12 54 36 72 9 12 16 27 36 54 72 6 409 479 10 838 150 441 409 10 479 150 838 441 Output 12 9 16 36 72 54 27 10 150 441 838 479 409 ① 트리의 Root Node는 전위순회(PreOrder)의 첫번째 원소입니다. ▶ preorder = [27 16 9 12 54 36 72] ② 중위 순회(inorder)에서 루트 노드를 찾습니다. ▶ 9 12 16 27 36 54 72 루트를 기준으로 왼쪽 서브 트리 / 오른쪽 서브 트리 구분 가능. 후위순회: 왼쪽 서브 트리 → 오른쪽 서브 트리.. 2021. 3. 1.
[Algospot] 알고스팟 ITES 외계 신호 분석 출처: https://www.algospot.com/judge/problem/read/ITES Input 3 8791 20 5265 5000 3578452 5000000 Output 1 4 1049 구간의 길이를 1..N까지 모든 경우에 대한 구간합이 K인지 확인하는 경우 TLE 발생 Greedy하게 접근하여 최적화할 필요가 있습니다. 접근 ex) [1 4 2 1 4 3 1 6]에서 구간합 K = 7을 찾습니다. * 구간합의 시작점인 [head]를 중심으로 접근 1 + 4 + 2 = 7로, 적절한 구간입니다. 여기서 tail을 우측이동 이동해봤자 구간합은 증가하여 구간합 > 7이 됩니다. 즉, head를 우측으로 이동하여 구간의 범위를 줄여야 합니다. 여기서 눈여겨볼 점은 tail의 탐색 위치입니다. t.. 2021. 3. 1.
[Algospot] 알고스팟 CHRISTMAS 크리스마스 인형 출처: https://algospot.com/judge/problem/read/CHRISTMAS Input 1 6 4 1 2 3 4 5 6 Output 3 1 [1] 한 번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가? K = 4, (1 2 3 4 5 6) 배열에서 [2, 4]구간 선택 3 + 4 + 5 = 12로 4명의 아이에게 3개씩 나누어 주면됩니다. 즉, 특정 구간의 합이 K로 나누어떨어지면 됩니다. ← 나머지 연산(modulo) ① [H, T] 구간의 합 = (psum[T] - psum[H - 1]) ② 해당 구간의 합이 K명의 아이들에게 나눠줄 수 있는 경우 (psum[T] - psum[H - 1]) mod K = 0 ③ (나머지 연산 적용 후) psum[T] mod K = psum[H.. 2021. 3. 1.
[Algospot] 알고스팟 PICNIC 소풍 출처: https://algospot.com/judge/problem/read/PICNIC Input 3 2 1 0 1 4 6 0 1 1 2 2 3 3 0 0 2 1 3 6 10 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 Output 1 3 4 [두번째 Test Case] N = 4 → [0, 1, 2, 3] ▶ 친구가 가능한 쌍: (0, 1) (1, 2) (2, 3) (3, 0) (0, 2) (1, 3) 주의해야할 경우는 [(0 1) (2 3)] = [(1 0) (2 3)] = [(0 1) (3 2)] = [(1 0) (3 2)]로 모두 같습니다. ex) (0, 1)을 선택한 경우, 남은 숫자 중 가장 낮은 숫자 2 선택하고 선택되지 않은 숫자 3을 선택 [코드 해석] 『 .. 2021. 3. 1.
[Algospot] 알고스팟 JUMPGAME 외발 뛰기 출처: https://algospot.com/judge/problem/read/JUMPGAME Input 2 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 2 3 3 1 2 3 4 1 1 5 2 9 4 7 0 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 3 3 3 1 2 3 4 1 1 5 2 9 4 7 0 Output YES NO ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. .. 2021. 3. 1.
[Algospot] 알고스팟 BRACKETS2 짝이 맞지 않는 괄호 출처: https://algospot.com/judge/problem/read/BRACKETS2 Input 3 ()() ({[}]) ({}[(){}]) Output YES NO YES 스택 이용 - 열린 괄호인 경우 Stack에 push - 닫힌 괄호인 경우 Stack의 마지막 원소가 무엇인지 확인합니다. - 비워져 있는 경우 유효성 X - 괄호 종류가 맞지 않은 경우 유효성 X - 모든 Input Data가 끝난 후, Stack이 비워져 있지 않은 경우 유효성 X 열린괄호가 잔재한 경우 ex) '(()' #include #include #include using namespace std; bool solution(const string& str) { const string opened = "({["; .. 2021. 3. 1.
반응형

티스토리툴바