전자공학 및 알고리즘

문제 링크입니다 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS +DP를 이용하면 풀 수 있는 문제였습니다. 무한번 움직일 수 있는 경우, 모든 선택지마다 값을 새로 찾는 경우 -> 시간 초과가 생긴다! 따라서 해당 칸에서 움직일 수 있는 최대 횟수, 이미 왔던 곳에 다시 왔다면 무한이라고 처리해야하는 문제입니다! 문제 접근 방법 1. char배열로 값을 입력 받은뒤 int형 배열에다가 옮긴다. (H는 0으로 옮겼습니다) 2. dfs탐색..

문제 링크입니다 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net BFS와 DFS를 모두 사용하는 문제였습니다. 방문할 수 있는 지점이 다수일 경우, 작은 수부터 출력하는 것을 주의해야 했습니다. 문제 접근 방법 1. 백터를 이용해 정점에서 갈 수 있는 다른 정점들을 저장합니다. 2. 시작 지점부터 DFS를 탐색하면서, 방문 노드를 출력합니다. 3. 시작 지점부터 BFS를 탐색하면서, 방문 노드를 출력합니다...

문제 링크입니다 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이분 그래프가 어떤 것인지는 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 이분의 깃허브를 참고..

문제 링크입니다 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제입니다. DFS를 이용하는 것이 핵심이였습니다. 위 도형중에서 'ㅗ' 모양의 보라색 도형을 제외한다면 나머지 모두는 상하좌우 4번을 연속해서 이동한다면 모두 구할 수 있습니다. 문제 접근 방법 1. 모든 칸마다 DFS를 통해서 상하좌우 이동한다. 2. 4번 이동한다면, 지금까지의 최댓값과 비교한다. 3. 조건에 맞다면 'ㅗ' 모양으로 나올 수 있는 ..

문제 링크입니다 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.www.acmicpc.netBFS와 DFS를 동시에 사용하는 문제였습니다. 위와 같은 조건으로 다리를 연결해 건널 수 있는 최소 연결 갯수를 구하는 문제입니다. 간단한 문제 접근 방법은 1. 섬의 구역에 번호 붙이고 좌표 저장하기 2. A섬에서 B섬까지 갈 수 있는 다리를 구하기 3. 다리를 연결해주면서 최소수를 구하기 였습니다. 문제 접근 1. 현재 지도의 상태 입력받기 2. 지도에서 각각..

문제 링크입니다 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net DFS에 익숙하지는 않아 https://yabmoons.tistory.com/117 님의 접근 방식을 참고했습니다. DFS, BFS를 모두 사용한 문제입니다 1번 기능을 구현하는 함수, 3번과 4번을 구현하는 함수와 2번 기능을 구현하는 함수로 나누어서 풀었습니다. 접근방법 1. DFS를 통해 7명의 학생을 뽑습니다. (1,2,3,4,5,6,7)이나 (7,6,5,4,3,2,1)은 똑같..

문제 링크입니다 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(BFS) 문제였습니다. 문제 조건입니다. 한번 지나간 알파벳은 지나가지 않고 최대로 갈 수 있는 횟수를 구하는 문제입니다. 예를 들어 CAAB ADCB 의 경우에는 C -> A -> D 총 3번이 됩니다. 접근 방법 1. 26칸을 가진 배열을 선언해 이동중에 어떤 알파벳이 입력되었는지 저장한다. 2. 상, 하, 좌, 우를 확인하여 갈 수 있는 경로를 확인한다..