반응형 전공 관련/알고리즘12 백준 2504 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값.. 2022. 9. 18. 시간복잡도 정리 1. 점근표기법(Asymptotic Notation) 1) 빅 오 표기법(O(n)) 빅 오 표기법의 정의는 다음과 같다. 모든 N≥N₀에 대해 f(N)≤cg(N)이 성립하는 양의 상수 c와 N₀가 존재하면, f(N)=O(g(N))이다. 이때 g(N)이 f(N)의 상한이 된다. 예를 들어 f(N)= 4N²+N+1 이라는 식이 있을 때 2보다 큰 N에 대해서 g(N)=N², c=5라면 항상 f(N)≤cg(N)이 성립한다. 주의할 점은 g(N)을 찾을 때 가장 차수가 낮은 함수를 선택하는 것이다. 차수가 높은 함수를 선택하게 될 경우 시간복잡도를 과장해서 추정하게 되기 때문이다. 2) 빅 오메가 표기법(Ω(n)) 빅 오메가 표기법의 정의는 다음과 같다. 모든 N≥N₀에 대해 f(N)≥cg(N)이 성립하는 양의.. 2021. 9. 8. 백준 2109 처음에는 우선순위 큐를 사용해서 비용이 크고 기간이 짧은 강연을 먼저 고르면 될 줄 알았다. 그런데 4 5 1 10 2 20 2 10 3 이러한 예시가 들어올 경우 5 + 2 + 10 이 아니라 10 + 20 + 10 을 선택해야 했다. 왜냐하면 기간 내에 강연을 가는 것도 가능하기 때문이다. 그래서 아예 새로운 방법을 사용해야 했다. 1. 최대 기간 maxDate 잡기 2. 비용이 큰 순서대로 입력값 정렬하기 3. maxDate에서 하루씩 줄여가며 가능한 강연 찾기 위 예시에서는 maxDate = 3 이 될 것이다. 비용이 큰 순서대로 입력값을 정렬하면 [[20, 2], [10, 2], [10, 3], [5, 1]] 이 될 것이다. 그러면 3에서 부터 2, 1 와 같이 1씩 줄여가면서 해당 날짜에 가능.. 2021. 5. 2. 백준 9663 이 문제는 정말 유명한 N-Queen 문제이다. 퀸은 양옆, 위아래, 대각선 방향 어디든 갈 수 있다. 따라서 한 행에 최대 하나의 퀸이 존재할 수 있다. 이때 N*N 크기의 체스판 위에서 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다. 만약 N = 8 이라면 위의 그림과 같이 배치할 수 있을 것이다. N-Queen 문제는 dfs, 백트래킹을 필요로 한다. 먼저 dfs를 위해 체스판을 표현할 배열이 필요하다. 퀸이 서로 공격할 수 없게 배치하려면 무조건 한 행에는 최대 한 개의 퀸만 존재할 수 있다. 그래서 a_row라는 배열을 만들었는데, 이 배열은 특정 행의 어느 열에 퀸이 위치하는지를 저장한다. 예를 들어 위 그림처럼 1행에서 6열에 퀸이 위치한다면 a_row[1] = 6.. 2021. 5. 2. 백준 2493 백준에서는 분류가 스택으로 되어있었는데 도저히 스택으로는 답이 보이지 않아서 다른 방식으로 풀었다. 1. data, res 라는 2개의 배열을 만든다. 2. data 배열에는 input값(탑들의 높이)을 저장한다. 3. res에는 해당 탑의 레이저를 송신받는 탑의 번호를 저장한다. res에 저장되는 탑의 번호는 0부터 시작한다고 가정하였다. 4. 현재 탑의 높이를 앞의 탑의 높이와 비교한다. 만약 앞의 탑의 높이가 더 낮다면 앞의 탑의 레이저를 송신받는 탑의 높이와 비교한다. 예를 들어, 6 10 5 6 7 11 8 이렇게 input이 들어온다면 6번째 탑의 높이는 8이므로 5번째 탑이 레이저 송신을 받을 것이다. 따라서 data[5] = 8, data[4] = 11, res[5] = 4 가 될 것이다... 2021. 4. 26. 백준 18115 이 문제는 deque을 사용하여 푸는 문제였다. 문제 풀이의 핵심은 주어진 input에 대해 역순으로 확인하며 deque에 카드번호를 집어넣는 것이다. 예를 들어 input이 5 2 2 1 3 2 1 이렇게 주어졌다면 1 → 2 → 3 → 1 → 2 → 2 순서로 값을 읽고, 각 숫자에 해당하는 과정을 해주면 된다. 카드 숫자는 1부터 N까지 수행을 할 때마다 1씩 증가한다. 1의 경우: 제일 앞에 카드가 들어가므로 deque.appendleft()를 사용해주었다. 2의 경우: 1. 앞에서 두 번째에 카드가 들어가야 하기 때문에 deque.popleft()를 이용하여 제일 앞의 카드를 빼네준다. 2. 카드를 deque.appendleft()를 이용해 넣는다. 3. 빼낸 카드를 deque.appendlef.. 2021. 4. 26. 이전 1 2 다음 반응형
