코딩성장스토리

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS로 풀면 그게 곧 최소 거리이므로 목적지 도달할 떄 탈출하면 된다. #include #include #include #include using namespace std; typedef pair pii; int arr[301][301]; bool check[301][301]; int dx[] = { 1,2,-1,-2,1,2,-1,-2 }; int dy[] = { 2,1,2,1,-2,-1,-2,-..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 그래프 탐색 문제이고 DFS, BFS 둘다 이용해서 풀었다. 1.DFS 를 이용한 풀이 #include #include #include using namespace std; int nmSheet[101][101]; bool check[101][101]; int m, n; int cnt=0; void dfs(int a, int b) { if (check[a][b] ==..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 BFS로 풀었다. 범위가 10만이고 모든 범위를 다돌아도 시간복잡도는 O(N)이 나오므로 모든 범위에 있는 위치값을 최소 몇번인지 정해도 문제 없다. 그래서 시작 위치에서 갈 수 있는 세가지 위치 현재위치 -1,현재위치+1,현재위치*2(순간이동) 을 큐에 넣으며 탐색을 하면 된다. 코드를 보자. #include #include using namespace st..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제는 처음에 순열을 이용해서 일일이 위치값 변경하면서 더했는데 이럴경우 시간복잡도가 (n*n!)가 나와 시간초과가 나온다 그 다음으로 재귀함수를 구현해서 모든 부분집합을 구햇다. 시간복잡도는 (2^n-1)이 나오고 시간초과는 나오지 않았다. 함수에는 부분집합의 합과 배열 몇 번째인지 를 인자로 받고 몇번쨰 배열 인자를 더하는 경우와 안더하는 경우를 나누어서..