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/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net - 백트래킹 문제 시간 복잡도 dfs 시간복잡도 : O(V+E) 정렬 시간복잡도 : O(NlogN) 따라서 big O = O(NlogN) 소스코드 #include #include using namespace std; int l,c; char ans[16]; char arr[16]; void combi(int start,int cnt){ if(cnt == l){ int check = false; int ..

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/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 다이내믹 프로그래밍 문제 알고리즘 현재 칸이 가장 왼쪽 위치인 경우 -> dp [1][0]=max(dp [0][0],dp[0][1])+ map[0] 현재 칸이 중간 위치인 경우 -> dp[1][1] = max(dp[0][0],dp[0][1],dp[0][2])+map[1] 현재 칸이 가장 오른쪽 위치 -> dp[1][2] = max(dp[0][1],dp[0][2])+map[2] 시간 복잡도 총 n번(n>num..

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net - 백트래킹을 이용한 dp문제. 알고리즘 1. dp배열에 마지막 칸을 1로, 나머지는 0으로 초기화한다. 2. 백트래킹을 활용한 dfs를 사용..