https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 인접리스트, DFS * 주의 1. 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다. 2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다.

1. 함수 매개변수와 마찬가지로 템플릿 매개변수에 기본값을 지정할 수 있다. template class Pinko { ... } - optional 에 정의돼 있으며, 어떤 타입의 값이 있거나 없을 수 있는 것을 표현한다. 2. 템플릿 매개변수로 템플릿을 받으려면 템플릿 템플릿 매개변수(template template parameter)라는 특수 매개변수를 사용해야 한다. - 템플릿 템플릿 매개변수를 지정하는 방식은 일반 함수의 매개변수에 함수 포인터를 지정하는 방식과 비슷하다. - 정의한 컨테이너(템플릿 선언부: templateclass vector)를 클래스 이름(vector)을 매개변수 이름 (Contatiner)으로 바꾼다. template class vector{}; tmeplate class ..

제네릭 알고리즘 표준 라이브러리에서 제공하는 알고리즘은 함수 템플릿으로 구현돼 있어서 다양한 타입의 컨테이네에 적용할 수 있다. 여기서 제네릭 알고리즘을 곧바로 컨테이너에 적용할 수 없다는 점에 주의한다. 대부분 반복자(이터레이터iterator)라 부르는 중간 매체를 거친다. ※ 이터레이터 begin( ), end( ) 첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다. cbegin( ), cend( ) 첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다. rbegin( ), rend( ) 마지막 원소부터 첫 번째 항목의 바로 다음 원소까지 순차적으로(역방향으로) 탐색하는 n..

프림(Prim) 알고리즘1. 그래프에서 시작점을 정한다 - (어떤 노드이어도 상관없음)2. 선택한 정점과 인접하는 정점들 중 최소 비용인 간선에 연결된 정점을 선택한다.3. 모든 정점이 선택될 때까지 1,2과정을 반복한다.※ 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리를 구성하는데 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 정렬 후 가장 최소 비용으로 간선을 선택하기 때문에 사이클이 발생하는지 판단하면서 진행해야 한다.

1976번: 여행 가자 (acmicpc.net) 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다. ..

20040번: 사이클 게임 (acmicpc.net) 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 사이클 찾기: 여기서 빨간색 줄을 마지막으로 연결한다고 가정했을때, 왼쪽은 3번 키값의 value는3, 5번키값의 value는 3으로 같고, 오른쪽은 5번 키값의 value는3, 1번키값의 value는 1로 다르다. 이렇게 사이클은 새로운 edge를 추가할때 출발점의 부모와 도착점의 부모가 같으면 사이클이 발생했다고 판단한다. 3. 구현:

종류 연산자 프로토타입 이항 산술 연산자 operator+ operator- operator* operator/ operator% T operator■ ( const T&, const T& ) ; 단항 산술 및 비트 연산자 operator+ operator- operator~ T operator■ ( ) const ; 선행, 후행 (증가,감소) operator++ operator-- T& operator■ ( ); T& operator■ ( int ); 대입 연산자 operator = T& operator■ ( const T& ); 축약 산술 대입 연산자 operator+= operator-= operator*= operator/= operator%= T& operator■ ( const T& ); T&..

C++에서는 흔히 스트림의 출발지와 목적지로 콘솔, 파일, 스트링을 사용합니다. ※ 파일 끝을 나타내는 EOF(end of file)은 유닉스와 리눅스에서는 Ctrl+D를 사용하고 윈도우에서는 Ctrl+Z를 사용합니다. 1. 출력 스트림에서 제공하는 메서드 대표적인 cout은 빼고 정리했습니다. cin 입력 스트림. '입력 콘솔'에 들어온 데이터를 읽는다. cout 버퍼를 사용하는 출력 스트림. 데이터를 '출력 콘솔'에 쓴다. cerr 버퍼를 사용하지 않는 출력 스트림. 데이트를 '에러 콘솔'에 슨다. clog 버퍼를 사용하는 cerr ※ 버퍼를 사용하는 것과 사용하지 않는 것의 차이와 장점은? 버퍼를 사용하는 스트림은 받은 데이터를 버퍼에 저장했다가 블록 단위로 목적지로 보내고, 버퍼를 사용하지 않는 ..

문제링크: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 안녕하세요. 핑크코냥입니다. 1780번 종이의 개수 문제는 분할정복의 기본적인 틀에서 개수만(?) 조금 늘린 문제입니다. 문제에서 요구하는 것을 간단하게 정리해보면 아래와 같습니다. 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. 2. (1) 이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각 잘린 종이에 대해서 (1) 의 과정을 반복한..

《출처. 시작하자! C++17 프로그래밍 (박헌재 지음)》 시작하기 전 동기와 비동기에 대해서 먼저 알아보자! Asynchronous(비동기) Synchronous(동기) 발음도 어려워 보이는 동기, 비동기 일단 말은 할 수 있어야 하니.. 번역기에 돌려 읽어주는데로 한 번 적어보겠습니다. Synchronous-> siNGkrənəs(씨-인!크로너스) Asynchronous->āˈsiNGkrənəs(에이 씨-인!크로너스) 이런식으로 발음해주고 있습니다. 알아 둡시다.. 면접에서 물어보면 알아듣긴 해야하니깐 (T_T)/ 이제 이 둘의 차이점과 지닌 뜻을 알아보자! 더보기 더보기 더보기 ● Asynchronous(비동기) : 작업을 위임하고 기다리는 방식 쉽게 이야기 하면, 꼭 한 줄 한 줄 순서대로 실행되..