다문다문 개발자

Problem 🔒문제홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.주식 하나를 산다.원하는 만큼 가지고 있는 주식을 판다.아무것도 안한다.홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이..

Problem 🔒문제https://www.acmicpc.net/problem/1541 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.입력첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.출력첫째 줄에 정답을 출력한다.더보기예제 입력 155-50+4..

Problem 🔒문제https://www.acmicpc.net/problem/1931 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시..

문제 유형도착 지점에서 여러 출발 지점까지의 최단경로를 구하는 경우특정 노드(출발 지점이 고정되어 있지 않음)에서 도착 지점까지의 최소 비용을 시간초과 안나게 구해야 하는 경우 역방향 그래프 활용 이유그래프의 가중치가 양수일 경우, 간선을 역으로 뒤집어도 최단 경로가 일치한다.도착 지점을 기준으로 다익스트라 를 1번만 수행하면, 모든 출발 지점에서 도착 지점까지의 최단 경로를 한꺼번에 구할 수 있다.예시문제 : 여러 도시에서 한 중앙 도시로 최소 비용 이동을 구하는 경우해결 : 간선을 역방향으로 뒤집고 중앙 도시에서 모든 도시로 가는 다익스트라를 수행하면, 모든 모시에서 중앙 도시로 가는 최단 경로를 1번에 구할 수 있다.[백준] 1238번 : 파티 - 자바(Java)[백준] 17835번 : 면접보는 승..

Problem 🔒문제https://www.acmicpc.net/problem/17835 마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다..

Problem 🔒문제https://www.acmicpc.net/problem/16946 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.각각의 벽에 대해서 다음을 구해보려고 한다.벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 세어본다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.출력맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을..

Problem 🔒문제지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.사람의 수 N이 주어진..

♟️ 최소 신장 트리(Minimum Spanning Tree)?최소 신장 트리는 주어진 그래프의 모든 정점을 포함하는 부분 그래프를 의미한다.부분 그래프는 주어진 그래프에서 일부 정점과 간선만을 선택해 구성한 새로운 그래프를 의미한다.신장 트리는 주어진 그래프의 정점이 V개일 때 V-1개의 간선을 가지고 있다.최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 말한다.최소 신장 트리를 구하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다.크루스칼(kruskal) vs 프림(prim)  크루스칼은 현재 선택할 수 있는 정점 중 가중치가 가장 적은 간선을 선택하여 모든 정점이 연결될 때 까지 연결  프림은 임의의 한 정점과 연결된 정점들에 대해, 가장 가중치가 작은 간선을 연결하면서 트리 ..

Problem 🔒문제https://www.acmicpc.net/problem/1922 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비..

♣️ 유니온 파인드(Union-Find = Disjoint-set)?크루스칼 알고리즘에서 두 정점이 같은 그룹인지 확인하고, 다르면 같은 그룹으로 합칠 때 이 알고리즘을 활용한다.일반 구현으로는 $O(V+E)$의 시간이 걸리지만, 유니온 파인드를 사용하면 상수시간에 가깝게 해결할 수 있다.Union 연산 : 두 그룹을 합치는 연산Find 연산 : 원소가 속해있는 그룹을 알아내는 연산 ♣️ Find(int x) 구현방법트리 구조를 각 원소에 대해 부모 정점의 번호를 담을 배열을 만들고 값을 적절히 사용한다.각 원소를 정점으로 생각하고 그룹은 트리로 표현한다. 그리고 모든 원소에 대해 부모 정점이 없다는 뜻으로 -1을 채워둔다.재귀를 활용해, 자신의 부모 노드로 타고 올라간다.현재 노드의 값이 음수(-1)이..