👨💻📱✍️🎢314 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. BOJ 5980 - Corn Maze 문제 백준 온라인 저지 - 5980번 풀이 과정 시작지점에서 목표지점에 도달하기 위한 최소 이동 횟수를 구하는 BFS 문제입니다. 여기서 주의할 점은 특정 지점간의 양방향 포탈이 존재한다는 것입니다. 각각의 포탈은 대문자 알파벳으로 제공되기 때문에 해시 테이블 을 이용해서 각 포탈의 정보를 관리합니다. 또한 중복 방문을 방지하기 위해서 visit 을 체크할 때 포탈의 위치는 중복 방문을 허용해야 한다는 점에 주의합니다. 이렇게 하지 않으면 포탈을 한번밖에 사용하지 못하는 상황이 발생하여 필요할 때 사용할 수 없기 때문입니다. 이로인해 다음과 같은 예시에서 문제가 발생할 수 있습니다. ###### #.WB## #.#### =B@W## ######코드 import sys from collections imp.. 2021. 6. 7. BOJ 1240 - 노드사이의 거리 문제 백준 온라인 저지 - 1240번 풀이 과정 트리 는 특정 정점에서 다른 정점까지 단 하나의 경로가 존재합니다. 따라서 BFS 를 이용해 각 정점까지의 거리를 구할 수 있습니다. 이때 인접 리스트를 이용해서 그래프를 구현한다면 O(V+E) 의 시간 복잡도로 문제를 해결할 수 있습니다. 코드 import sys from collections import deque def make_graph(edges): graph = {n + 1: [] for n in range(N)} for frm, to, cost in edges: graph[frm].append([to, cost]) graph[to].append([frm, cost]) return graph def bfs(start, goal): q = dequ.. 2021. 6. 7. BOJ 11265 - 끝나지 않는 파티 문제 백준 온라인 저지 - 11265번 풀이 과정 그래프가 주어졌을 때, 최소 시간으로 각 지점간의 이동 비용을 구한 뒤 제한 시간내에 도달 가능성을 판단하는 문제입니다. 플로이드 와샬 알고리즘 을 사용해서 모든 정점간의 최소 비용을 구한 뒤 시작 지점과 도착 지점을 활용해서 답을 구할 수 있습니다. 코드 import sys def floyd(graph): for k in range(N): for i in range(N): for j in range(N): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) def solution(current_party, next_party, remaining_time): is_possible = graph[curre.. 2021. 6. 4. 이전 1 ··· 19 20 21 22 23 24 25 ··· 53 다음
