어흥

문제 링크: https://www.acmicpc.net/problem/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 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 - MOD 연산, 0으로 나누기를 유의해야 한다 2. 구현 - Num의 크기만큼 Arr[] 배열에 초기값을 입력 받는다 - Num을 통해 Height를 계산한 이후, Tree[] 배열을 동적할당한다 - Init() 함수를 통해 Tree[] 배열을 갱신한다 - 값이 ..

문제 링크: https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다(세그먼트 트리 ↔ 구간 합이라고 생각했던에서 벗어나게 해준 문제다) 2. 구현 - 모든 수들을 Arr[] 배열에 담는다 - 부모로 자식중에서 Max값을 지닐 maxTree[]와 Min값을 지닐 minTree[]를 생성한다. 이때, MinTree[]는 전부 MAX로 초기화하여 추후에 0만 나..

문제 링크: https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고있어야 한다 2. 구현 - Height을 통해 세그먼트 트리를 나타낼 Tree[] 배열의 크기를 설정한다 - 초기의 수를 Arr[] 배열에 입력받은 후, Init() 함수를 통해 Tree를 초기화한다 - Query수만큼 Sum()과 Update() 함수를 호출하며, X가 Y보다 클 수도 있으므로 Big, Sma..

문제 링크: www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 - 우선순위가 높은 사탕을 뽑을 방법은? 2. 구현 - Tree[]를 이용하여 세그먼트 트리를 구성한다. 이때, Tree의 크기는 사탕의 우선순위가 1~1000000이므로 N=1000000일때 완전이진트리의 높이를 구하고, 비트연산으로 배열의 메모리를 동적으로 할당한다 - Update() 함수를 통해 idx가 포함된 ..

문제 링크: www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 2. 구현 - Arr[] 배열을 통해 입력받는 수들을 저장한다(Index: 0~Num-1) - ceil(log2(Num))을 통해 Height을 구한다. Tree[] 배열을 만들 경우, Num보다 크거나 같은 2의 제곱수 중 가장 작은 제곱수*2만큼의 공간이 필요하기 때문이다. - ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 1. 주의할 점 - 회전시킨 문자열은 어떻게 구상할 것인가 2. 구현 - 기존 파라미터로 받은 문자열 SS의 길이를 Len에 저장한다 - SS를 2개 이어서 새로운 SS를 만든다 - For문을 통해 0~Len-1에서 시작해서 Len만큼의 길이를 검사한다 → 회전에 대한 처리를 할 필요가 없다 - Stack을 이용하여 괄호의 짝이 모두 맞아서 Stack이 빈 경우, Answer++를 수행한다 #include #include #include using namespace std; int solution(string ss) { int answer ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 1. 주의할 점 - Check[][][] 배열이 갱신될 때마다 MOD로 나눈 나머지를 저장한다 - (Y,X)에 Dir의 방향에서부터 온 적이 여러번 있다면, 최종 경우에만 BFS를 수행하도록 한다 (안하면 메모리 초과 가능성↑) 2. 구현 - 2 방향으로만 이동가능하므로 항상 특정 지점까지의 거리는 최단거리로 구해진다 → Info 구조체를 큐에 삽입하여 B..

문제 링크: programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 1. 주의할 점 - 모든 정점이 서로 연결되어 있지 않다 - 3번의 다익스트라 알고리..