BFS 기초 문제 풀어보기 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2644번 : 촌수계산 * 입출력 예시 // 입력 9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6 // 출력 3 8과 6일땐 ? => 8에서 6을 못 감 => -1 출력 #include #include #include #include #include #include #include using namespace std; #define M..

https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 이번 주 스터디는 내 차례가 되어 조금 더 깊게 이 문제에 대해 공부해봤고, 이 문제를 풀어봄으로써 C++의 STL에 대해 조금 더 알게되었다. #include #include #include #include #include using namespace std; // sort, unordered_map(해시맵), pair, auto, iterator bool compare(const ..

오류찾기 다음은 잘못된 코드이다. 왜 그런지 알아보자. 오류를 먼저 찾을 수 있는지 확인해 보고 아래 글을 읽기를 추천한다. #include int main() { char arr[21] = "”; /* 모두 널로 초기화 */ printf("최대 20문자 입력 가능\\n"); printf("(Q 혹은 이 입력 시 종료)\\n"); printf("---------------------\\n"); for(int i=0; i

지난 시간에 그래프의 기초 개념을 다루었으니 그래프 응용 시간을 가져보겠다. 이번 시간에 할 건 그래프의 최소비용 신장트리의 구성이다. 그전에 우리는 무방향 그래프만 다룰 것이고, 시작에 앞서 용어를 몇 개 짚고 가자 가중치 그래프 : 정점을 잇는 간선에 값이 부여된 그래프이다. 인접행렬을 보면 0과 0이상의 값, 무한대로 3가지의 값의 표현이 있다. 0 : 자기 자신을 가리키는 간선이 없으니 0 0 이상의 값 : 가중치, weight라고 부른다. 무한대 : this 정점에서 해당 정점까지 한 번에 가지 못한다는 걸 의미한다. 지난 시간에는 정점이 간선으로 연결되어 있다는 사실로, 인접행렬을 0과 1로 표현했지만 이제는 간선에 값이 주어지기에 1이 아닌, 그 값을 인접행렬에 넣는다. 신장트리(Spanni..

그래프란 ? : 정점(Vertex)과 그 정점을 잇는 간선(edge)으로 구성되어 있는 자료구조 무방향 그래프 : 간선의 방향이 없는 그래프 방향 그래프 : 간선의 방향이 있는 그래프 그래프를 표현하는 두 가지 방법 1. 인접행렬 2. 인접리스트 인접행렬 표현법 (무방향과 방향 그래프) 무방향 그래프를 인접행렬로 표현하면 대칭적인 형태를 볼 수 있다. 인접행렬을 작성하는 코드는 다음과 같다. // 그래프의 인접행렬 생성 함수 void createGraph(int arr[][MAX_SIZE], int vertex, int edge) { int start, destination; // 인접행렬 초기화 for (int i = 0; i < vertex; i++) { for (int j = 0; j < verte..

동적 계획법을 지난 시간에 배웠으니, 그에 맞는 문제를 풀어보려 한다. 백준의 실버3 난이도 DP 알고리즘을 쓰는 '2579번 : 계단 오르기' 문제이다. 문제 규칙 이 문제에서는 규칙을 문제 설명에 명시해 두었다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 동작 원리의 핵심은 2번에 있다. 세 개의 계단을 연속되게 밟으면 안 되고, 한 번에 세 칸 이상씩은 이동할 수 없다는 점이다. 백준에 나와있는 입력 예제이다. 첫 번째 int 변수 n에 계단 개수를 받아주고 계단의 값을 담아..

이번 주 백준 문제 유형이 자료구조 수업 때 배우지 않은 DP이기에 이를 공부한 바탕으로 DP를 정리해보려 한다. 두괄식으로 먼저 DP를 정의한 문구들을 보고 가자. DP란 ? → *메모이제이션(Memoization) 기법을 이용하며 '하나의 문제는 단 한 번만' 풀도록 하게 하는 알고리즘 * 계산했던 것을 메모리 공간에 기억해 두고, 같은 식을 써야한다면 앞에서 기억한 것을 재사용하는 기법 분할 정복 기법과 DP의 차이점 분할 정복 : 큰 문제를 작은 부분 문제로 나누고, 그 하위 문제를 독립적으로 해결하고 이를 합쳐서 원래 문제를 해결함 동적 계획법(DP) 분할 정복 중복되는 문제 O X 메모이제이션 O (중복 문제의 결과를 저장하고 재활용함) X 문제 분할 방식 문제의 크기와 형태에 따라 다름 동일..