N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1~N-1까지의 값을 모두 가지면 그 수열을 유쾌한 점퍼라고 부른다. 예를 들어 다음과 같은 수열에서 1 4 2 3 앞 뒤에 있는 숫자 차의 절대 값이 각각 3, 2, 1이므로 이 수열은 유쾌한 점퍼가 된다. 어떤 수열이 유쾌한 점퍼인지 판단할 수 있는 프로그램을 작성하라. 입력 첫 번째 줄에 자연수 N이 주어진다. 그 다음 줄에 N개의 정수가 주어진다. 정수의 크기는 int형 범위 안에 있다. 출력 YES/NO 1트 (강의 풀이) 어떻게 해야할지 모르겠었음ㅠㅠ 풀이보니까 바로 이해됨 #include #include #include using namespace std; int main(void){ freopen("input.txt", "..
전체 글
N개의 숫자가 나열된 수열이 주어집니다. 이 수열 중 연속적으로 증가하는 부분 수열을 최대 길이를 구하여 출력하는 프로그램을 작성하세요. 만약 N=9이고, 5 7 3 3 12 12 13 10 11이면, "3 3 12 12 13" 부분이 최대 길이 증가수열이므로 그 길이인 5을 출력합니다. 값이 같을 때는 증가하는 걸로 생각합니다. 입력 첫 줄에 자연수의 갯수가 주어진다. 두 번째 줄에 N개의 숫자열이 주어진다. 각 숫자는 100,000 이하의 자연수이다. 9 5 7 3 3 12 12 13 10 11 출력 최대 부분 증가수열의 길이를 출력하세요. 1트 (성공) cnt를 1로 초기화하는 것에 주의해야 한다. #include #include using namespace std; int main(void){ f..
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 다음과 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 다음과 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 입력 첫 째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다..
0부터 9까지의 숫자가 표시된 카드를 가지고 두 사람 A와 B가 게임을 한다. A와 B에게는 각각 0에서 9까지의 숫자가 하니씩 표시된 10장의 카드뭉치가 주어진다. 두 사람은 카드를 임의의 순서로 섞은 후 숫자가 보이지 않게 일렬로 늘어놓고 게임을 시작한다. 단, 게임 도중 카드의 순서를 바꿀 수는 없다. A와 B 각각이 늘어놓은 카드를 뒤집어서 표시된 숫자를 확인하는 것을 한 라운드라고 한다. 게임은 첫 번째 놓인 카드부터 시작하여 순서대로 10번의 라운드로 진행한다. 각 라운드에서는 공개된 숫자가 더 큰 사람이 승자가 된다. 승자에게는 승점 3점이 주어지고, 패자에게는 승점이 주어지지 않는다. 만약 공개된 두 숫자가 같아서 비기게 되면, A와 B 모두에게 승점 1점이 주어진다. 10번의 라운드가 모..
// C 스타일 초기화 int num = 20; int &ref = num; // C++ 스타일 초기화 int num(20); int &ref(num); 위 문장들은 모두 동일하다. class SoSimple{ private: int num1; int num2; public: SoSimple(int n1, int n2) : num1(n1), num2(n2){} void ShowSimpleData(){ cout
🌟 최대 유량 문제(=네트워크 플로우) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량을 동시에 보낼 수 있는지 계산하는 문제 ✏️ 용어 정리 용량 : c(u,v) 정점 u에서 v로 전송할 수 있는 최대 용량 유량 : f(u,v) 정점 u에서 v로 실제 흐르고 있는 유량 잔여 용량 : r(u,v) = c(u,v) - f(u,v) 간선의 용량과 실제로 흐르는 유량의 차이 소스 s 모든 유량이 시작되는 정점 싱크 t 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 ✏️ 기본 속성 용량 제한 속성 f(u,v)
🟩 모든 정점쌍에 대해서 둘 사이의 최단거리를 구할 수 있다. cf. 다익스트라 : 한 시작점에서 다른 정점까지의 최단 거리 단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작 a 👉 b로 이동할 때, 경유점은 c 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택 🟩 구현 1. 위의 그래프를 우선 배열로 구현해야 한다. 초기값은 아주 큰 값으로 설정해야 한다. 그리고 자기 자신까지의 비용은 0으로 설정한다. 2. 시작점을 i, 끝점을 j, 경유점을 k라 할 때, 구하는 식은 다음과 같다. adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]) 항상 작은 값만을 갖게 되므로 직접적으로 ..
🟩 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 🌟 다익스트라 vs 벨만-포드 1번 노드에서 3번 노드로 가는 최단 거리를 구한다고 할 때, 경로1. 1번 👉 3번 (비용 : 10) 👉 다익스트라 알고리즘 경로2. 1번 👉 2번 👉 3번 (비용 : 5) 👉 벨만-포드 알고리즘 ✏️ 다익스트라 알고리즘 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다. 음수 간선이 없다면 최적의 해를 구할 수 있다. 시간 복잡도가 빠르다 (O ElogV) ✏️ 벨만-포드 알고리즘 (정점-1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. cf. 다익스트라와의 차..
🟩음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만 한 꼭짓점을 "소스" 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용 🟩 그리디이자 동적계획법 그리디 : 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 다이나믹 프로그래밍 : 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 👉 가능한 적은 비용으로 가장 빠르게 해답을 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 🟩 예제 A노드에서 출발하여 F노드로 가는 최단경로를 구하는 문제 S = 방문한 노드들의 집합 d[N] = A -> N까지 계산된 최단 거..
🟩 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택 🟩 동작 1. 시작 단계는 시작 노드만이 최소 신장 트리 집합에 속한다. 2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 최소 신장 트리 집합에 넣는다 (사이클을 막기 위해 연결된 정점이 이미 트리에 속한다면 그 다음 순서를 넣는다) 3. 2번 과정을 MST 집합의 원소 개수가 그래프의 정점의 개수가 될 때까지 반복한다. 시작 정점 A A와 인접한 노드 B, C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니, C를 집합에 넣고 비용에 AC 가중치를 더한다. AC와 인접한 노드들..
🟩 최소 신장 트리 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 👉 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드 연결 가능 🌟 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🌟 최소 신장 트리 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 신장 트리 왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선 (23+13)으로 이루어진 신장트리 즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리 🟩 크루스칼 알고리즘 동작과정 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인 👉 사이클 발생 여부에 따라, 최소 신장..
🟩 객체 배열 객체로 이루어진 배열 따라서, 배열 생성시 객체가 함께 생성된다. Person arr[3]; Person * per = new Person[3]; 🟩 객체 포인터 배열 객체를 저장할 수 있는 포인터 변수로 이뤄진 배열 따라서 별도의 객체 생성 과정을 거쳐야 한다. Person * arr[3]; arr[0] = new Person(name, age); arr[1] = new Person(name, age); arr[2] = new Person(name, age); 객체 관련 배열을 선언할 때는 객체 배열을 선언할지, 객체 포인터 배열을 선언할지를 먼저 결정해야 한다. 🟩 this 포인터 그 값이 결정되어 있지 않은 포인터이다. 왜냐하면 this 포인터는 this가 사용된 객체 자신의 주소값을..