본문 바로가기

개발/CodingTest55

[백준] 1541번 - 잃어버린 괄호 - 그리드 알고리즘 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 풀이 1. 나는 '-' 기준으로 쪼개기 2. 쪼개진 것끼리 덧셈 3. 첫번째 숫자 제외하고 뒤에 숫자.. 2024. 1. 22.
[백준] 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분이 필요하게 된다.. 2024. 1. 22.
[백준] 1931번 - 회의실 배정 - 그리디 알고리즘 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거.. 2024. 1. 22.
[이코테] 커리큘럼 - 이해까지 도와주는 풀이 문제 철수는 온라인으로 컴퓨터공학강의를 듣고 있다. 이때 각 온라인강의는 선수강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당강의를 들을 수 있다. 예를들어 '알고리즘’ 강의의 선수 강의로 '자료구조'가 존재한다면, ‘자료구조를 들은 이후에 ‘알고리즘' 강의를 들을 수 있다. 철수는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번강의의 선수 강의로 1번과 2번강의가 있고, 1번과 2번강의는 선수강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자. 1번 강의: 30시간 2번 강의: 20시간 3번 강의: 40시간 이 경우 1.. 2024. 1. 21.
[이코테] 도시 분할 계획 - 이해까지 도와주는 풀이 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느날 원숭이 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을 이장은 계.. 2024. 1. 21.
[이코테] 팀 결성 - 이해까지 도와주는 풀이 문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는 지 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 1. 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 2024. 1. 21.
[자료구조] 진입차수란? 진입차수(Indegree)란? 그래프 이론(Graph Theory)은 네트워크 구조를 모델링하고 분석하는 데 사용되는 수학적 도구입니다. 그 중에서도 "진입차수(Indegree)"는 방향 그래프(Directed Graph)에서 매우 중요한 개념 중 하나입니다. 이 개념은 어떤 정점으로 들어오는 간선의 수를 나타내며, 그래프 내의 연결 관계를 이해하는 데 도움이 됩니다. 그래프에 대한 개념을 다시 잡고 싶으시면 아래의 링크로 이동하시면됩니다. https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84%EB%9E%80 [자료구조] 그래프란? 오늘은 수학과 컴퓨터 과학에서 매우 중요한 개념.. 2024. 1. 21.
[자료구조] 그래프란? 오늘은 수학과 컴퓨터 과학에서 매우 중요한 개념인 '그래프(Graph)'에 대해 자세히 알아보겠습니다. 그래프는 객체들 간의 관계를 나타내는 추상적인 모델로, 네트워크를 구성하는 핵심적인 요소입니다. 이 구조는 데이터 구조와 알고리즘, 복잡한 시스템의 분석에 광범위하게 사용됩니다. 그래프의 기본 개념, 구성 요소, 그리고 다양한 유형과 이들의 활용 방법에 대해 구체적으로 살펴보겠습니다. 1. 노드(정점, Vertex) 그래프의 기본 단위인 노드는 네트워크 내의 개별적인 객체를 나타냅니다. 이는 도시, 컴퓨터, 사람 등 다양한 형태일 수 있습니다. 2. 간선(Edge) 노드들을 연결하는 선으로, 두 객체 사이의 관계를 나타냅니다. 간선은 친구 관계, 도로 연결, 데이터 전송 등을 표현할 수 있습니다. 3... 2024. 1. 21.
다양한 알고리즘 - 위상정렬 안녕하세요. 오늘은 위상 정렬에 대해서 알아보려고 합니다. 위상 정렬은 정렬 알고리즘의 일종입니다. 위상 정렬은 일반적으로 작업들 간의 의존 관계를 표현하고, 이를 바탕으로 작업들을 순서대로 실행해야 할 때 사용합니다. 이론적으로 설명하자면, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것입니다.' 0. 집입차수 계산 먼저 우리는 집입차수에 대해서 알고 넘어가야합니다. 진입차수란 특정한 노드로 '들어오는' 간선의 개수를 의미합니다. 이는, 해당 노드의 선행 작업의 개수를 의미합니다. 자세한 진입차수의 대한 개념은 다음 링크로 들어가시면 체크해보실 수 있습니다. https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC.. 2024. 1. 21.
신장 트리 - 크루스칼 알고리즘 신장 트리(Spanning Tree)는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 이 글은 신장 트리의 정의와 특성, 그리고 그것의 응용 분야와 관련 알고리즘에 대해 설명합니다. 신장 트리의 정의와 특징 1. 모든 노드 포함 신장 트리는 원본 그래프의 모든 노드를 포함하는 부분 그래프입니다. 이는 어떤 노드도 제외되지 않는다는 것을 의미합니다. 2. 사이클이 없는 구조 신장 트리는 사이클을 포함하지 않습니다. 이것은 트리 구조이기 때문에, 어떠한 경로를 따라가도 동일한 노드를 두 번 방문하지 않는다는 것을 의미합니다. 3. 신장 트리 알고리즘 1) 크루스칼(Kruskal) 알고리즘 이 알고리즘은 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않.. 2024. 1. 19.

티스토리툴바