목록알고리즘/C++ (56)

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

[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 11404 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 전형적인 플로이드 와샬 알고리즘을 사용하여 해결하는 문제였습니다. 플로이드 와샬 알고리즘이란? [Algorithm] 플로이드 와샬(F..

알고리즘/C++ 2019. 11. 10. 22:17
[C++] BAEKJOON 11559 Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net dfs 를 사용하여 문제를 해결하였습니다. 사실 dfs 를 이용한 접근보다 구현 쪽에 치중되어 있는 문제입니다. dfs 를 사용하여 같은 상하좌우 붙어있는 같은 색상을 찾아 해당 좌표를 v vector 에 넣어주었습니다. v vector 의 크기가 4 이상이면 삭제가 가능한 블록이므로 v_total vector 에 넣어주었습니다. 바로 삭제하지 않고 한 번에 모아서 삭제하는 이유는 동시에 깨지는 블록들의 경우에는 별도의 갯수로 세지 않기 때문입니다. v_total vector 가 비..

알고리즘/C++ 2019. 11. 4. 01:10
[C++] BAEKJOON 2573 빙산

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net dfs 를 이용하여 문제를 해결하였습니다. 매 년 마다 dfs 를 순회하여 빙산을 없애줍니다. 빙산을 한 번에 없애면 같은 년도에 먼저 없어..

알고리즘/C++ 2019. 11. 3. 21:38
[C++] BAEKJOON 1389 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net bfs 를 이용하여 문제를 해결하였습니다. 인접리스트를 이용하여 각 유저간의 연결 관계를 표시합니다. for (int i=0;i> n1 >> n2..

알고리즘/C++ 2019. 11. 3. 18:43
[C++] BAEKJOON 6593 상범 빌딩

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net BFS 를 이용하여 문제를 해결하였습니다. 건물이 층, 폭, 너비 3차원이기 때문에 3차원 배열과 각 좌표를 담을 수 있는 pair3 ..

알고리즘/C++ 2019. 11. 1. 01:08