목록c++ (12)

수학과의 좌충우돌 프로그래밍

[Algorithm] 위상정렬

위상정렬이란? 위상 정렬은 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘입니다. 그림을 보며 이해해봅시다. 다음과 같은 그래프에서 앞선 작업 2,3이 끝나야 뒤 작업 4가 이루어질 수 있으며 이 때 둘 중 무엇을 먼저 끝내던 규칙에 위배 되지 않기 때문에 경로는 여러 개가 나올 수 있습니다. 단 위상정렬이 성립하기 위해서는 DAG여야 합니다. DAG란? Directed Acyclic Graph의 줄임말로 사이클이 존재하지 않는 방향 그래프입니다. 만일 위 그림에서 5이 1에 연결되었다면 시작점이 존재하지 않기 때문에 위상정렬이 성립할 수 없습니다. 위상 정렬 원리 위상 정렬이 어떤 원리로 동작하는지 살펴봅시다. 위상 정렬을 스택이나 큐를 사용하여 구현할 수 있지만 큐를 사..

알고리즘/이론 2020. 8. 27. 00:17
[C++] stl container set, multiset

이번 포스팅에서는 C++ stl container인 set과 mutiset에 대해서 알아보도록 하겠습니다. set set 은 데이터를 저장할 수 있는 container입니다. 가장 기본적인 container와 다른 점은 자동으로 정렬이 된다는 점입니다. 새로운 값이 삽입, 삭제 될 때마다 이 정렬 상태를 유지하고 있어야 하므로 set 은 기본적으로 binary search tree로 구현이 되어 있습니다. set 선언 set 을 사용하기 위해서는 헤더 파일을 포함해야합니다. #include 그 후에는 보통 container들과 마찬가지로 다음과 같이 선언할 수 있습니다. set 이름; int 자료형을 저장할 s라는 이름의 set을 만들기 위해서는 다음과 같이 선언해줍니다. set s; 선언 시, 어떠한 ..

알고리즘/C++ 2020. 4. 14. 17:22
[C++] BAEKJOON 1012 유기농 배추

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net dfs 를 이용해서 구현하였습니다. K 번 만큼 받은 좌표를 통해 board 를 완성한 후, 연결되는 구간이 몇 개인지 세주는 문제였..

알고리즘/C++ 2019. 10. 1. 23:57
[Algorithm] KMP, Knuth-Morris-Pratt 알고리즘

한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다. 단순한 문자열 검색 특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다. 두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n 0 && p[i] != p[j]) j..

알고리즘/이론 2019. 8. 21. 01:38
[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011)

문제보러가기 8901번: 화학 제품 문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다. www.acmicpc.net 입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다. bc 혼합물의 수를 0 부터 ..

알고리즘/C++ 2019. 8. 2. 21:10