본문 바로가기

알고리즘

 (29)
Codeforces Round #694(Div. 2) 리뷰 1. 최종 결과 Rank : 4976/22818 Performance : 1283 A : WA on Test 4 B : AC C : AC D : Unsolved E : Unsolved F : Unsolved 2. 문제풀이 A Strange Partition tags : greedy, math, number theory 문제 : x와 배열의 길이 n이 주어질 때, beauty of array는 $\sum_{i=1}^k \lceil \frac{b_i}{x} \rceil$으로 결정된다. 해당 리스트에 인접한 두 원소를 더해서 배열의 길이를 줄여줄 수 있다. 모든 경우에서의 beauty of array의 최댓값과 최솟값을 구해라. 풀이 : $\lceil \frac{a+b}{x} \rceil \le \lceil ..
시간 복잡도 1. 문제 : 백준 - 주사위 윷놀이 www.acmicpc.net/problem/17825 2. 틀린 이유 : 주어진 이동횟수 또한 바뀔 것이라 생각해서 10! * 4^10의 시간복잡도를 계산하고도 완전 탐색으로 풀려고 했다. 실제로는 4^10만 계산해서 완전탐색으로 풀 수 있는 문제이지만 풀이를 구상하기 전에 시간복잡도를 먼저 계산하고 맞는 풀이인지 검토하려는 노력이 필요하다. 3. key idea : 4^10(1,048,576), 10!(3,628,800) -> 대충 계산할 수 있는 능력 다 백만 안쪽으로 계산된다. 4. 알아두면 좋을 것 : (1) 실제로 10! * 4^10으로 해당 문제가 나왔다면 어떻게 계산해야될까? -> dp를 이용하면 될듯한데,,,조금 더 생각해보기 (2020.12.30. 추..
시뮬레이션에서 문제 조건을 잘못 읽은 문제 1. 문제 : 백준 - 이상한 게임 2 www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 2. 틀린 이유 : 빨간색 격자에서의 조건을 잘못 봤다. 밑의 말부터 위의 말 순서대로 적어 놓은 것을 캐치하지 못하고 다른 조건으로 2시간 동안 붙잡고 풀었음. 3. key idea : 문제를 꼼꼼히 읽는 것 말고는 답이 없는 듯. 더군다나 규칙이 복잡한 문제는 코딩에 들어가기 전 조건들 모두 적고 이후에 잘못됐을 때 비교할 수 있는 표를 만들 것
시뮬레이션 재귀 때 map 원래 상태로 복귀 1. 문제 : 백준 - 2048(Easy) www.acmicpc.net/problem/12100 2. 틀린 이유 : 재귀에서 이전 상태를 저장하는 tmp array를 전역 변수로 선언. DFS가 진행됨에 따라서 tmp 상태도 함께 바뀌게 되어 이전 값을 올바르게 저장할 수 없다. 3. key idea : tmp array를 DFS 함수 안에서 선언한다. 함수가 끝날 때 자동으로 없어지기 때문에 서로 영향을 받지 않음. 4. 알아두면 좋을 것 : (1) array를 지역 변수로 선언했을 때 다른 함수에서 인자로 받는 방법 int (* tmp)[21] 이렇게 선언해주면 된다. array 하나가 pointer를 의미하므로 2차원의 경우에는 [21]을 뒤에 붙여주면 된다. 3차원의 경우에는 int (* tmp)..
c++ 문자열 입력 받는 방법 문자열 입력 받는 문제를 풀 때 어떻게 입력 받아야할지 몰라 고생을 했다. 우선 헤더를 통해 string 타입을 선언할 수 있고(using namespace std를 선언해주어야 한다.) cin을 통해서 문자열을 입력 받을 수 있다. #include #include using namespace std; int main(){ //입력이 apple banana로 주어질 때 string fruit1; string fruit2; cin >> fruit1 >> fruit2; cout
펜윅 트리(Fenwick tree, Binary Indexed Tree) 변경되는 데이터 속에서 구간 합을 구하거나 최대/최소, 구간 곱 등을 구할 때 세그먼트 트리(링크)를 사용하였다. 하지만 세그먼트 트리는 N개의 배열이 있을 때 4*N개의 공간을 할당해야했기 때문에 많은 메모리를 필요로 하였다. 세그먼트 트리와 비슷한 역할을 하면서 N개의 공간을 사용하는 자료 구조가 있다면..? 그렇다. 그것이 바로 펜윅 트리이다. 펜윅 트리 펜윅 트리 또는 Binary Indexed Tree(BIT)라고 부른다. Binary Indexed Tree라는 이름에서 알 수 있듯이 인덱스로 이진수를 사용한다. 이것이 무슨 말이냐 하면, (그림 출처) n = 16인 위와 같은 배열이 있다고 가정하면, 각각의 수가 2진수로 나타냈을 때 어디에 마지막 1이 있는지를 알아야 한다. 1 = 0001(..
세그먼트 트리(Segment tree) {1, 3, 100, 5, -2, 10, 4, 20, 1, 5} 다음 배열의 구간 합을 m개의 각 요청마다 구한다고 생각해보자 그냥 구하게 된다면 O(mn)의 시간복잡도를 가지게 될 것이다. 이를 줄이고 싶다면, 누적합(prefix sum) 기법을 사용하면 된다. 미리 index = 0부터 더한 값들을 배열에 저장한다. pre_sum = {1, 4, 104, 109, 107, 117, 121, 141, 142, 147} 그리고 만약 i번째에서 j번째의 구간 합을 구하라는 쿼리가 들어온다면 prefix[j - 1] - prefix[i - 1]의 값을 바로 구하면 되기 때문에 O(1)의 시간복잡도 내에 각각의 쿼리를 처리할 수 있다. 이렇게 되면 처음에 누적합을 구할 때만 배열 전체를 순회하면 되기 때문에 ..
백준 12865번 평범한 배낭 C/C++ 풀이 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 가장 고전적인 DP 문제 예전에는 DP를 점화식으로만 이해했었는데, 2차원 배열로 이해하고 나니 더 깊은 이해를 할 수 있게 되는 것 같다. https://gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다...

티스토리툴바