![]()
https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이 처음에는 맥도날드와 스타벅스가 없는 정점들을 순차적으로 출발점으로 두고 반복문을 사용하여 맥도날드와 스타벅스의 최단거리의 합을 각각 구했다. 하지만 이 풀이는 시간 초과라는 결과를 가져와 다른 방식으로 접근해야겠다고 생각했다. 먼저 맥도날드에 대해 모든 맥도날드 위치를 출발점으로 두고 최소힙을 사용하여 각 정점들에 대해 거리를 구했다..
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 브루트 포스 탐색을 이용하여 사전순 순열을 출력하는 과정에서, 추가로 가지치기를 통해 주어진 길이와, 오름차순일 경우에만 출력하는 문제이다. 재귀함수를 이용하여 탐색한 이후, 이전 단계로 돌아와 다시 탐색을 하는 식으로 코드를 구성하였다. 그리고 가지치기 조건은 길이가 주어진 길이일 경우, 그리고 인덱스 탐색을 통해 오름차순에 해당할 경우에 출력을 해주었다. import sys n,m=map(i..
문제 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 구현 + 브루트포스 알고리즘 문제이다. 문제 조건을 꼼꼼히 읽지 않아서 많이 틀렸는데 오답률이 낮은 이유가 있다.. 북동, 동, 남동, 남 방향으로 확인하면 되는데 범위를 넘어가는 경우나 6개이상 놓여 있으면 안되는 조건을 꼭 숙지해야한다 코드 #include using namespace std; int board[20][20]; // 범위 안에 있는지 확인하는 함수 bool insid..
![]()
문제 풀이 주어지는 노선이 양방향이므로 다익스트라 알고리즘을 3번 이용하여 풀었습니다. 입력받는 위치는 총 4가지 입니다. 1과 N, 필수로 들러야 하는 start와 end. 다익스트라 알고리즘을 1, N, start 에서 이용하여 각 경로로 가는 최단거리를 구합니다. 여기서 1 -> start + N -> end 와 1 -> end + N ->start 를 비교하여 더 작은 값을 얻습니다. (start -> end는 동일, 양방향) 이 값에 start -> end 의 최단거리를 더하여 답을 얻습니다. 예외 처리) start가 1과 같은 경우, end와 N이 같은 경우엔 해당 연산을 삭제합니다. 코드 import java.io.*; import java.util.*; class Main { static ..
https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 문제분석 n개의 패턴을 입력받아 n개의 패턴 중 똑같은 것만을 출력하고 나머지 다른 부분은 '?'를 채워 출력하는 문제이다. 소스코드 n = int(input()) name = [] for i in range(n): name.append(input()) tmp = list(name[0]) for i in range(n): for a in range(len(tmp)): if tmp[a] == ..
문제 링크 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 파이썬의 deque 모듈을 이용해 BFS를 구현하였다. BFS를 하기 전 memo 변수에 W팀의 탐색을 진행하는지, B팀의 탐색을 진행하는지 기록하였다. (line 16) 탐색 조건으로 memo 변수에 저장된 팀에 속한 병사인지 체크한다. (line 24) num 변수는 모여있는 병사들의 수를 센다. (line 15) 탐색 조건을 만족하면 num 수를 1씩..
문제링크 예제 입력 1 5 RRRBB GGBBB BBBRR BBRRR RRRRR 예제 출력 1 4 3 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다. 적록색약 : G,R을 구별 못 함 Solution Base: 깊이 우선 탐색을 사용하여 R,G,B 일 때를 모두 탐색 def bfs(x,y,color): global isvisited isvisited[x][y] = True dx = [0,1,0,-1] #위 아래 왼쪽 오른쪽 방향 설정 dy = [1,0,-1,0] for i in range(4): mx = dx[i] + x my = dy[i] + y if 0
문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs에 대한 기초를 점검하는 문제이다. 그래프를 인접행렬과 인접리스트로 나타낼수 있는데, 인접행렬보다 인접리스트가 메모리 측면에서 더 좋기때문에 벡터를 이용하여 구현하였다. 입력받을때 양방향 그래프이므로 양쪽모두에 간선을 넣어주고, 각 노드 벡터마다 정렬을 해준뒤 구현하면 된다. 코드 #include #include #include #in..
![]()
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 코드 #include using namespace std; #include #define PI 3.141592653589793 #define ll long long int a[505][505], d[505][505]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 1; i a[i][j]; } } d[1][1] = a[1][1]; for(int i = 2; i
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] 나이트가 이동하는 방향만 잘 고려한다면 결국 최단 거리를 찾는 문제와 동일하기 때문에 전형적인 BFS 문제입니다. 다른 기본적인 BFS 최단거리 문제에서 사용하는 상하좌우로 이동 대신 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 목적지까지의 Depth를 찾으면 되는 간단한 문제였습니다. 더보기 #include #include #include using namespace std; i..
문제 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 가장 처음에 생각난 풀이는 n^3 * logn의 풀이인데 (임의의 세수 합을 구해서 이분탐색으로 찾기) n 이 최대 1000이기 때문에 시간초과가 난다. 정답을 구하기 위해서는 n^2 또는 n^2logn의 풀이를 생각해야 했고 a + b + c = k 라고 할 때 a + b의 값을 갖는 배열을 만들기로 했다. a + b 배열을 만든 뒤 k..
* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 2251 BOJ 2251번 물통BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.처음에는 방문\_여부\[물통 A의 velog.io BOJ 2251번 물통 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net Intro BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, ..
