개발자 퉁이리

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 다익스트라 ⊙ 문제 접근 과정 가장 짧은 경로를 구하는 문제다. 다익스트라 알고리즘으로 풀면 된다. heapq 라이브러리를 사용해 우선순위 큐를 구현하자! 입력받은 출발점을 기준으로 각 정점간의 최소비용을 구해준 후, 도착지점의 최소 비용을 출력해주면 된다. ⊙ 문제 풀이 import sys..

https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 char 값으로 받은 데이터를 0과 1로 변환하여 int arr에 넣고 bfs 함수를 만들어줬다. 그리고 한 바퀴가 다 끝나서 queue를 탈출시 count up을 해주고 마지막에 저장된 count 값을 출력한 후, 배열과 방문 기록을 초기화..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 플로이드-와샬 ⊙ 문제 접근 과정 입력받을 때, 해당 경로에 대해 1이라는 값을 표시해준다. 플로이드 와샬로 검사하여 만약 거쳐갈 수 있다면 또다시 1 표시 1 표시가 둘 다 안 되어 있다면 count up! N까지 다 돌고 count 출력 해준 뒤, count를 다시 0으로 초기화 다음 번호, 마지..

https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 같은 거리의 집을 다 탐색하고도 탐색할 집이 남아있다면 거리를 1 늘리고 다시 탐색한다. set을 이용하여 방문을 했는지 안 했는지 판별했다. ⊙ 문제 풀이 #include #include #include using namespace std; ty..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 BFS 문제라 BFS로 풀었는데 식으로도 충분히 풀 수 있다. 현재 층에 대해 위층과 아래층 값을 더하거나 뺀 값이 최고층보다 작거나 같거나, 0보다 크고 방문한 적 없는 층이라면 진행한다. 그리고 그 층을 다시 현재층에 대입하여 반복한다. 그러다가 목적층인 G와 현재층 S 값이 같다면 종..

⊙ 문제 다음과 같은 지뢰 찾기 게임 프로그램을 작성하시오. 실행 결과는 '5 10 0.3'을 명령행 인수로 사용한 예이다. 프로그램은 3개의 명령행 인수(m, n, p)를 받아들이고, m * n 크기의 배열을 생성해 지뢰를 숨긴다. 숨긴 지뢰가 있는 원소는 *로 표시하고 없는 원소는 -로 표시한다. 원소에 지뢰가 있을 확률은 세 번째 명령행 인수인 p이다. 지뢰 숨김 여부를 나타내는 2차원 배열을 출력하고, 지뢰를 숨기지 않은 원소를 -대신에 이웃한 지뢰 개수로 채운 2차원 배열도 함께 출력한다. 이웃한 지뢰는 상하좌우 및 대각선 원소에 숨긴 지뢰를 의미한다. 지뢰 숨긴 지역을 30%로 설정하려면, 난수 발생 정적 함수 Math.random() 값이 0.3보다 적은 원소에 지뢰를 숨긴다. ⊙ 문제 접근..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS를 사용하여 1과 연결된 모든 컴퓨터에 대해서 count를 올려주었다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 101 int n,m; int cnt=0; int arr[MAX][MAX]; bool..

https://www.acmicpc.net/problem/1260 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 DFS와 BFS 알고리즘을 사용하여 푸는 문제이다. DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다. DFS의 구현은 스택 또는 재귀 함수로 구현한다. BFS의 구현은 큐를 이용해서 구현한다. ⊙ 문제 풀이 #include #include using namespace std; int n,m,v; int arr[1001][1001]; bool visit[1001]; void reset_visit() { for (auto i=1;i y; arr[x][y]=1; arr[y][x]=1; } reset_v..