[Python] 백준 1541 잃어버린 괄호 문제풀이

문제세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.입력첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.출력첫째 줄에 정답을 출력한다. 문제풀이 이번 문제는 문자열 파싱을 하는 문제유형이라고 생각한다.일단, 괄호를 입력하는 것 보다, 가장 작은 결..

• format_list_bulleted CodingTest/BOJ
• · 2025. 2. 26.
• textsms

[Python] 백준 11399 ATM 문제풀이

문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. ..

• format_list_bulleted CodingTest/BOJ
• · 2025. 2. 25.
• textsms

[Python] 가장 먼 노드 문제풀이 및 정답코드

문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 nvertex..

• format_list_bulleted CodingTest/programmers
• · 2025. 2. 22.
• textsms

[Python] 서로소 집합을 활용하여 그래프 사이클 확인하기 (Graph Cycle)

직전에 알아봤던 서로소 집합 알고리즘은 다양한 알고리즘에서 활용될 수 있다.특히, 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다. 참고로 방향 그래프에서의 사이클 여부는 DFS로 판별할 수 있다. 서로소 집합의 연산은 find와 union으로 두가지가 있으며, 여기서 union은 그래프의 간선정보로 이해할 수 있다고 했다.따라서, 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다. 알고리즘의 순서는 아래와 같다. 서로소 집합을 활용한 사이클 판별 알고리즘각 간선을 활인하며 두 노드의 루트 노드를 확인한다.루트 노드가 서로 다르다면, 두 노드에 대해서 union연산을 수행한다.루트 노드가 서로 같다면..

• format_list_bulleted CodingTest/algorithm
• · 2025. 2. 21.
• textsms

[Python] 1717 집합의 표현 문제풀이 - disjoint set, union by rank

문제초기에 n+1개의 집합 {0}, {1}, {2}, ... , {n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 입력첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.출력1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 ..

• format_list_bulleted CodingTest/BOJ
• · 2025. 2. 11.
• textsms

[Python] 서로소 집합(disjoint set) 알고리즘 알아보기

서로소 집합 개념 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.아래의 그림으로 예시를 알아보자(가)에서는 집합이 총 2개가 있으며, {1, 2}와 {3, 4}의 원소를 갖고 있다. 두 집합에서 원소가 겹치는 경우가 없기 때문에, 서로소 관계라고 할 수 있다. 반면, (나)의 경우, {1, 2, 4}, {3, 4}의 두 집합이 있으며, 4라는 원소가 두 집합에 공존하고 있기 때문에 서로소 집합 관계가 아니라고 할 수 있다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.이 때, 서로소 집합 자료구조는 union과 find의 2개의 연산으로 조작할 수 있다. 연산 명작동 방식union두 집합을 하나의 집합으로 합치는 연산find특정한 원소가 속한 ..

• format_list_bulleted CodingTest/algorithm
• · 2025. 2. 10.
• textsms