생성자 c++을 사용하여 알고리즘 문제를 풀때에도 class로 원하는 형태의 객체를 정의할 일이 종종 있다. 이경우 보통 아래와 같이 생성자를 통해 클래스의 멤버변수를 초기화 해준다. class Edge { public: int from; int to; int distance; Edge(int from, int to, int distance) { this->from = from; this->to = to; this->distance = distance; } bool operator distance < edge.distance; //오름 차순 정렬 } }; 멤버 이니셜라이저 다른 사람의 코드를 참조하다 처음 보는 방식을 배우게 되었다. 바로 이니셜라이저 혹은 멤버 이니셜라이저라고 불리는 방법이다. 이니셜라..

문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1.완전 탐색 처음엔 [BOJ 10971] 외판원 순회2 문제와 동일하게 모든 도시를 각각 출발지로 하여 N번 순회를 수행했지만 시간 초과가 발생했다. #include #include using namespace std; #define INF 987654321 int N, edge[17][17], ans = INF, start; void init() { ..

벨만-포드 개념 벨만 포드 알고리즘은 가중치가 존재하는 그래프에서 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다. 보통 위와 같은 유형의 문제를 풀기 위해 다익스트라 알고리즘을 먼저 학습한다. 결론부터 말하자면 다익스트라 알고리즘의 경우 음수 간선이 존재하는 경우 문제를 해결하지 못 할 수 있다. 다익스트라 음수 간선 위에서 다익스트라의 경우 음수 간선이 존재하면 문제를 해결하지 못한다고 하지 않았고 못 할 수 도 있다고 했다. 아래의 그래프를 통해 자세히 이해해보자. 단순한 음의 간선 : s -> a -> b -> g 경로에 -4(a -> b) 음의 간선이 있어도 문제가 발생하지 않음 순환하지 않는 싸이클 : s -> c > -> d 경로 이후 d->c로 가는 경우 -3 음의 간선이 있지만 ..

문제 좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다. 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다. 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다. 예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다. 정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성..

문제 문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다. 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다. 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다. s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다. 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다. 문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요. 입력 ..

문제 준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다. 준호는 처음에 병사 n명을 가지고 있습니다. 매 라운드마다 enemy[i]마리의 적이 등장합니다. 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다. 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다. 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다. 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다. 무적권은 최대 k번 사..

문제 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다. b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다. n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다. a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다..

문제 한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다. 예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다. 직사각형 ..

문제 구름나라는 N개의 도시와 N - 1개의 도로로 이루어진 나라이다. 각 도시는 1번부터 N번까지 번호가 붙어있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있으며, 같은 두 도시 쌍을 잇는 도로는 존재하지 않는다. 최근 구름나라의 도시들에는 불법 쓰레기 투기로 인한 환경적 문제가 발생하고 있다. 때문에 현재 i 번 도시에는 Ai만큼의 쓰레기가 쌓여 있는 상태이다. 구름나라의 청소부인 구름이는 구름나라를 돌아다니면서 쓰레기들을 치우려고 한다. 구름이는 최대 K만큼의 쓰레기를 담을 수 있는 커다란 쓰레기 봉투를 가지고 있다. 구름이는 현재 1번 도시에 있고, 다음 두 가지 행동들을 자유롭게 반복하여 청소를 하고자 한다. 구름이가 현재 머물고 있는 도시를 a번 도시라고 하자. a번 도시에 인접한..