본문 바로가기

Algorithm202

BOJ 15684 - 사다리 조작 문제 백준 온라인 저지 - 15684번 풀이 과정 DFS 와 백트래킹 을 활용한 최적화가 필요한 탐색 문제입니다. 이때 사다리의 위치를 검사하는 과정에서 인덱스 범위에 대한 고려를 안해주기 위해 board 양쪽에 padding 을 추가했습니다. 이렇게 안하면 양쪽 사다리 위치 인덱스가 board 를 벗어나는지에 대한 조건문에 추가해줘서 코드가 복잡해집니다. 사다리를 2차원 배열로 표현했으므로 각 시작점에서 타고 내려올때는 왼쪽, 오른쪽에서 만나는 경우를 고려해줘야 합니다. 주의할 점은 수평 방향으로 이동했을 경우에는 바로 한칸 밑으로 전진시켜줘야합니다. (안그러면 무한 루프에 빠집니다.) DFS 를 수행하는 과정에서 만약 만족하는 조합을 찾았을 경우에는 이후 탐색을 수행하지 않고 바로 True 를 반환하.. 2021. 6. 7.
BOJ 1781 - 컵라면 문제 백준 온라인 저지 - 1781번 풀이 과정 마감일을 고려하여 가장 많은 컵라면을 얻을 수 있는 방법을 찾는 그리디 문제입니다. 데드라인의 마지막 날부터 순회를 하면서 해당하는 날 이상의 날짜에 대해서 가장 많은 컵라면을 얻을 수 있는 것을 선택하면 됩니다. 이를 위해 우선 순위 큐 를 두 개 사용해서 하나는 데드라인의 내림차순으로, 다른 하나는 컵라면의 내림차순으로 정렬하여 사용합니다. 코드 import sys import heapq N = int(input()) questions = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] def init_queue(): pq = [] for deadline, cups in question.. 2021. 6. 7.
BOJ 6118 - 숨바꼭질 문제 백준 온라인 저지 - 6118번 풀이 과정 시작 정점에서 다른 모든 정점까지의 거리 중 가장 긴 경로를 찾는 문제입니다. 다익스트라 알고리즘 을 활용하여 한 정점으로부터 다른 모든 정점까지의 최단 거리를 구한 다음, 가장 거리가 먼 정점을 찾아주면 됩니다. 이때 구현의 편의를 위해서 dist 배열을 거리값과 정점 번호순으로 정렬하여 답을 구했습니다. 코드 import sys import heapq INF = sys.maxsize N, M = list(map(int, sys.stdin.readline().split())) adj = [[] for _ in range(N+1)] for _ in range(M): frm, to = list(map(int, sys.stdin.readline().split(.. 2021. 6. 7.
BOJ 2331 - 반복수열 문제 백준 온라인 저지 - 2331번 풀이 과정 규칙에 따라 생성되는 숫자들을 모두 탐색하며 최종적으로 반복되는 수열을 제외한 나머지 숫자들의 개수를 구하는 문제입니다. 이를 위해 DFS 탐색을 수행하며 각 숫자들을 처음 방문, 두번째 방문, 세번째 방문 이렇게 세 종류로 구분해줍니다. 첫번째 방문의 경우는 문제가 없지만 두번째 방문했을때는 해당 숫자가 중복되어 나타난다는 의미이므로 방문횟수를 증기시킨 후 다음 탐색을 수행합니다. 이때 가장 처음 세번째 방문되는 숫자가 나타나는 경우 이후의 숫자들은 또다시 겹치게 되므로 탐색을 계속 수행할 필요없이 바로 종료해주면 됩니다. 코드 import sys sys.setrecursionlimit(10**6) A, P = list(map(int, sys.stdin... 2021. 6. 7.
BOJ 4889 - 안정적인 문자열 문제 백준 온라인 저지 - 4889번 풀이 과정 여는 괄호와 닫는 괄호를 적절히 변환하여 짝이 맞도록 하는 방법을 찾는 문제입니다. 괄호 짝 맞추기 문제와 유사한 컨셉으로 문제를 해결할 수 있습니다. 우선 여는 괄호({)의 경우 해당 괄호가 안정적인지는 이 괄호만 봐서는 알 수 없습니다. (이후에 나오는 괄호에 영향을 받음) 대신에 닫는 괄호(})의 경우 이전에 여는 괄호가 존재해야만 안정적인 문자열을 만들 수 있습니다. 만약 닫는 괄호가 나왔는데 여는 괄호가 존재하지 않을 경우 유일한 방법은 해당 괄효를 여는 괄호로 바꾸는 것 뿐입니다. 이룰 위해 스택 을 활용해서 괄호 종류에 따라 push, pop 을 수행하고 최종적으로 남는 여는 괄호의 개수 / 2 가 필요한 닫는 괄호의 개수입니다. 코드 impo.. 2021. 6. 7.
BOJ 4811 - 알약 문제 백준 온라인 저지 - 4811번 풀이 과정 알약을 하나 전체를 먹거나 반개를 먹어서 만들 수 있는 모든 문자열의 개수를 찾는 문제입니다. 완전탐색으로 접근하면 경우의 수가 너무 많기 때문에 중복된 연산을 많이 수행하게 됩니다. 대신 동적 계획법 을 활용해서 모든 경우의 수를 구하면 중복된 연산을 많이 줄일 수 있습니다. dp[i][w][h] = 알약 한개가 W개, 반개가 h개 있을 때 i 날부터 시작해서 만들 수 있는 모든 문자열의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[i][w][h] = dp[i + 1][w][h + 1] + dp[i + 1][w + 1][h] 단 전자의 경우 `h < w` 여야 하며 후자의 경우는 `w < N(전체 알약 수)` 이어야 합니다. 코드 .. 2021. 6. 7.

티스토리툴바