https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 코테에 기출되었던 문제. - bfs 문제 알고리즘 1. 현재 파란 구슬의 좌표와, 빨간 구슬의 좌표를 queue에 넣는다. 2. queue에서 하나 꺼내서, 이동할수 있는 경로로 이동한다. 이때, 다음 방문할 좌표가 벽이거나, 구멍을 만나거나, 맵의 사이즈에 맞지않는 다면, 이동을 중지한다. ans를 1더해준다. 이동후 좌표가 이미 방문한 곳..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net - 순열문제 or dfs 문제 알고리즘 1. 숫자는 고정 시켜두고 순열 알고리즘을 통해 기호들을 배열함 소스코드 #include using namespace std; char ca[5] = {' ','+','-','X','/'}; char arr[12]; int nums[12]; int n; int maximum = -100000001; in..

https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net - 순열 문제 알고리즘 1. 뒤에서부터 n[i] > n[i+1]인 i를 찾아서 index에 저장 2. 뒤에서부터 index까지 arr[index] > arr[j]인 j를 찾아서, arr[index]와 arr[j]를 바꾸어준다. 3. index+1부터 수열 끝까지 뒤집어준다. 시간 복잡도 O(N) 소스코드 #include using namespace std; int arr[10001]; int n; int check = false; void reverse..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - dfs 문제 알고리즘 1. 2차원 배열을 이용해서 N개의 노드와 엣지를 표현해준다. 2. dfs를 1부터 돌려주는데, count가 N이 된다면/ 더이상 방문할 노드가 없다면, 해당 dfs 종료. 시간 복잡도 dfs의 시간복잡도인 O(V+E). 모든 노드가 다 이어져있는 경우 최대이므로 해당 상황을 가정한다면, O(2N) 소스코드 #include us..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net dfs로 풀수 있던 간단한 문제. 알고리즘 1. dfs로 ㅗ모양을 제외한 도형을 움직이면서 도형안에 들어가는 최댓값을 구한다. 2. ㅗ모양 탐지를 위해서 도형을 돌려본다. 3. 1,2번에 대해 맵 전체를 돌면서 최댓값을 찾는다. 시간 복잡도 dfs의 시간복잡도가 O(V+E)인데, 맵을 N X M 이므로 총 O(NXM(V+E)). 소스코드 #include using namespace std; int..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net - BFS 문제 다음번에 탐색할 위치와, 얼음을 녹일 위치를 저장하는 문제. 알고리즘 큐를 총 4개 준비한다. 현재 백조의 bfs를 탐색하는 swanQ 1일뒤 백조가 bfs를 탐색할 swanNQ 현재 얼음을 녹이는 bfs를 탐색할 iceQ 1일뒤 얼음을 녹이는 bfs를 탐색할 iceNQ 1. 백조가 진행하는 첫번째 bfs를 구성한다. 처음 실행이라면, 백조의 위치에서 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net - 다이나믹 알고리즘(DP). 알고리즘 v[a][b] = a에서 b까지의 문자열의 팰린드롬 여부(a부터 b까지 문자열이 팰린드롬이라면 true, 아니라면 false) 팰린드롬이 될 조건 - a == b 라면 항상 팰린드롬. - arr[a] == arr[b]인 경우에 팰린드롬. - v[a+1][b-1] = true && arr[a]==arr[b]인 경우에 팰린드롬. 예외 조건 b-a == 1 , arr[b]==arr[a]라면 팰린드롬이다..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net - 브루트 포스 문제. 알고리즘 1. 목표로 하는 채널을 기준으로 두고 1씩 내려가거나 1씩 올린다. 2. 1씩 올리거나 내린 수들이 망가진 키를 포함하지 않는지 검사한다. 3. 망가진 키를 포함한다면 다시 1번으로, 망가진 키를 포함하지않는다면, 100에서 무식하게 올리는 거랑 비교해서 작은 횟수를 출력한다. 예외 조건 1. 100에서 무식하게 올리거나 내린것이 더 적은 이동..