본문 바로가기

알고리즘

 (305)
[백준] 2243번 : 사탕상자 2243번: 사탕상자 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 🤔 문제분석 세그먼트 트리와 팬윅트리를 활용하여 문제를 해결하였습니다. 팬윅 트리 팬윅 트리로 문제를 해결 할때에는 이분탐색과 팬윅트리를 사용하여 문제를 해결하였습니다. 사탕의 순위를 누적합으로 계산시키고, 이분탐색으로 사탕을 찾아 나아 갑니다. 쿼리함수의 인자는 사탕의 가치가 되고 사탕의 가치를 입력하면 현재 그 사탕의 가치의 순위가 리턴 됩니다. 업데이트 함수는 사탕의 정보를 업데이트 합니다. 쿼리함수로 리턴받..
[백준] 1517번 : 버블소트 1517번: 버블 소트 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 🤔 문제분석 처음 문제에 접근할때 배열을 순회하면서, 배열의 인덱스의 오른쪽 부분의 배열들이 현재의 배열의 값보다 큰 개수를 세어 카운팅을 하여 문제를 풀었습니다. 해당 문제를 해결하기위해서는 병합정렬을 알아야합니다. 병합정렬은 분할정복 알고리즘으로 가장 작은 단위(풀기쉬운문제)로 분할하고, 원하는 조건으로 정복(병합) 합니다. 병합하는 과정에서 버블소트 swap 횟수를 알 수 있습니다. 병합하고자 하는배열에 오른쪽..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 [백준] 6549번 : 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 🤔 문제분석 이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂 해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다. 분할정복, 세그먼트 트리 최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 ..
[백준] 7578번 : 공장 7578번: 공장 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 📄 문제개요 라인 A와 라인 B가 있을때 라인 A와 B에는 N개의 기계가 각각 있다고 하고, 직선으로 각각의 기계를 1:1 매칭 하였을때, 겹치는 선분의 개수를 구하는 문제이다. 1:1 매칭은 같은 유니크한 숫자를 매칭시킨다. 🤔 문제분석 라인 A의 기계들을 리터레이션 하는데, 하나씩 연결해보면서, 겹치는 선분이 있는지 확인한다. B의 위치를 알기위해서는 딕셔너리 자료구조를 활용하여 위치를 파악한다. 📝 의사코드 A의 배열의 값을 순회한다...
[백준] 11505번 : 구간 곱 구하기 11505번: 구간 곱 구하기 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 📄 문제개요 수열이 주어지고, 업데이트, 쿼리가 주어졌을때 쿼리를 했을때에 업데이트된 구간 곱을 출력하는 문제이다. 🤔 문제분석 세그먼트 트리를 사용하는 구간곱 문제이고, 기존 구간 합과는 0을 곱해버리면 트리가 다음 업데이트일때 어떠한 수를 곱해도 0이 되기때문에 diff를 사용하지 않는다. update함수는 leaf 노드까지 방문했다가, leaf노드를 해당 값으로 초기..
[백준] 10999번 : 구간 합 구하기2 10999번: 구간 합 구하기 2 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 📄 문제개요 구간합을 구하는 문제로, 쿼리와 업데이트가 주어졌을때, 턴마다 결과를 출력하는 문제이다. 🤔 문제분석 구간 업데이트 기존의 구간합 로직으로 구현한다면 시간복잡도는 KlogN이 될것이다. 만약 구간이 엄청 크다면 원하는 시간복잡도안에 문제를 해결 할 수 없습니다. 느리게 갱신되는 세그먼트 트리 (Segment Tree Lazy Propagation) 📝 ..
[백준] 5676번 : 음주코딩 5676번: 음주 코딩 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 📄 문제개요 구간곱을 구하는 문제로 쿼리의 개수가 10^5개로 N의 개수가 매우 크다면, 일반적인 쿼리로 문제를 해결 할 수 없습니다. “팬윅트리” 혹은 **“세그먼트 트리”**를 이용하여 문제를 해결 할 수 있습니다. 수열이 주어졌을때, 해당 곱이 “양수”인지 “음수”인지 “0”인지 판별해야합니다. 🤔 문제분석 세그먼트 트리로 문제 풀기. 세그먼트 트리로 문제를 풀경우 메모리는 최소 2^(log(N)+1), 최대 4N의 배열이 필요합..
[백준] 18500번 : 미네랄 2 18500번: 미네랄 2 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 📄 문제개요 창영이와 상근이는 양쪽에서 화살을 날려 미네랄를 부순다. 미네랄을 부수면 땅과 연결되지 않는 클러스터는 모양을 유지한 상태로 땅이나, 다른 미네랄 혹은 클러스터에 떨어진다. 주어진 창을 던지는 횟수와 높이가 주어졌을때, 최후의 미네랄의 모양을 출력하라. 🤔 문제분석 R, C, N 이 100 이하 이기때문에 정확한 문제 분석과 알고리즘 작성이 문제의 Key Point 라고 생각한다. 주어진 창의 횟수가 높이가 주어졌을때 미네랄을 부수는..

티스토리툴바