11725번: 트리의 부모 찾기 (acmicpc.net) 문제 풀이 입력이 길어 input이 아닌 sys모듈의 stdin.readline 사용 모든 노드의 연결구조를 봐야한다고 생각해서 dfs로 풀긴했지만, bfs로 푸는 것도 오답이 아니라고 생각함. 입력받기는 딕셔너리에 저장. 이때 정점 u와 v가 연결되어있다면 딕셔너리의 키값으로 둘 다 저장함. 이다음 깊이우선탐색을 하는데, 방문여부를 파악하는 동시에 답을 저장함. 이를 위해 딕셔너리 이용. 깊이우선이므로 스택(후입선출) 만들어서 루트노드인 1을 저장. 스택이 빌 때까지 while 반복. 스택에서 pop을 하며 그 노드를 node에 저장. 이 노드가 이미 방문된 노드라면 continue, 아니라면 방문했다는 의미로 visit에 저장. 루트노드인 1은..
Koala - 11기/코딩테스트 준비 스터디
풀이 DFS를 활용하여 그림의 영역을 찾는다. 각각의 1로 이루어진 영역은 하나의 그림을 의미함. 따라서 DFS를 사용하여 연결된 1의 영역을 찾아내고, 각 그림의 넓이를 계산한다. FS 함수는 현재 위치 (x, y)에서 상하좌우로 탐색하며 연결된 영역을 찾아간다. 이때 주의해야 할 점은, 대각선으로는 연결되어 있지 않다고 하였으므로 상하좌우만 고려해야 한다. 만약 (x, y) 위치가 유효하고 아직 방문하지 않았으며, 값이 1이라면, 해당 위치를 방문한 것으로 표시하고 그림의 넓이를 1 증가시킨다. 그리고 이어서 인접한 위치들도 DFS를 호출하여 같은 그림에 속하는지 확인한다. 모든 위치를 순회하면서 그림의 개수와 가장 큰 그림의 넓이를 찾는다. 가장 큰 그림의 넓이를 출력한다. 코드 #include #..
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 - deque를 이용하여 BFS로 구현하였다. - 이중 반복문을 통해 탐색을 시작할 위치를 찾고, bfs를 호출한 결과의 제곱을 합한다. - bfs함수가 호출이 되면, 시작 위치를 방문했으므로 0으로 변경하고 q를 생성하여 시작 좌표를 append 하고 반복문을 통해 상하좌우를 확인한다. - 만약 상하좌우의 좌표가 범위를 벗어나지 않고 해당 위치의 병사가 시작 ..
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의 기본 구현문제입니다. 기본적으로는 dfs는 스택, bfs는 큐를 통해 구현하였습니다. 그리고 탐색 문제는 방문 여부를 판단하는 boolean 배열이 필요하므로, isVisit배열을 만들어 문제를 해결합니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 1. 벽 세우기 -> make_wall 함수 : 재귀 호출 이용하여 0만날때 값을 1로 변경 -> count 증가 -> 밖으로 나올 때 다시 0으로 -> 벽 3개다 세우면 bfs호출 2. 바이러스 퍼뜨리기 & 안전영역 크기 재기-> dfs 함수 : 상하좌우 움직일 수 있게끔 d 변수 생성 - queue 만들어 map deepcopy -> 바이러스 퍼진 곳을 queue에 넣기. - 좌표값 확인하며 상..
Problem Solution 1. 테스트 케이스의 개수를 입력 받는다. 2. t번 반복하면서 아래 작업을 수행한다. - 각 테스트 케이스마다 두 개의 숫자 n과 m을 입력 받습니다. - m번만큼 무시하고 숫자 쌍을 입력 받습니다. - 각 테스트 케이스마다 n-1 값을 출력합니다.(이때, n은 입력된 값에서 1을 뺀 값) Answer #include using namespace std; int main(void) { int t; cin >> t; while(t--){ int n, m; cin >> n >> m; for (int i = 0; i > a >> b; } cout
https://www.acmicpc.net/problem/16637 정답 코드 import sys from collections import deque si = sys.stdin.readline N = int(si()) arr = list(map(str, si().rstrip())) answer = -sys.maxsize visited = [0 for i in range(N)] max_depth = ((N // 2) + 1) // 2 def calculate(first, second, arr): operator = arr[first + 1] first = int(arr[first]) second = int(arr[second]) if operator == '+': return str(first + sec..
문제 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 게임 이론 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을..
문제 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net Algorithm 모든 국가를 여행하기 위해 타야하는 비행기의 최소 갯수를 묻는 문제이다. 비행기의 최소갯수를 구하려면 각 지역을 1번씩만 방문하는게 당연히 최소가 될것이므로 이미 방문한 노드면 방문하지 않는 dfs를 사용하면 좋을것 같았다. 재귀를 이용하여 dfs를 구현하였고, 재귀가 호출될때마다 노드를 옮긴것이고, 즉 비행기를 탔다는 소리이므로 ans..
문제 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는 큐를 사용한다.(시간복잡도가 낮은 덱을 사용) 2차원 배열로 노드 연결여부를 구성. 최초 모든 연결을 False로 초기화 입력값에 따라 (시작노드,끝노드), (끝노드,시작노드)를 True로 만들어줌.(연결되었다) visited1,visited2는 dfs,bfs의 방문기록 작성 깊이우선탐색, 너비우선탐색에서 조건문의 기준은 “..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제풀이 네트워크 연결 상태를 확인 후, 1번 컴퓨터가 바이러스에 걸렸을 때 전파될 수 있는 컴퓨터의 수를 구하는 탐색 문제이다. 깊이 우선 탐색 문제 중 하나로, 네트워크 연결 상태를 입력받은 후 인접 리스트의 형태로 그래프 정보를 저장한 후, 1번 컴퓨터를 매개변수로 하여 깊이 우선 탐색을 진행하였다. 다른 컴퓨터를 방문할 때마다 바이러스에 걸린 컴퓨터의 수를 1씩 증가시킨다. 2. C++ 코..
4949번: 균형잡힌 세상 (acmicpc.net) 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 문제 풀이 단지 (,)와 [,]가 짝을 이루어 있는지만 확인하는 문제이다. 이는 스택을 이용하여 쉽게 풀 수 있다. 온점을 이용하여 입력을 알린다. EOF문제인걸로알고있는데 정확히 코드의 형식을 지켜야한다~ 이런형식이 있다~는 아직 모르겠어서 while문에 if종료조건 달아줬다. (,[는 리스트에 append해주고 ),]가 온다면 바로 전에 (,[가 있는지 확인한다. 있다면 잘하고있는것이므..
