YANGORITHM

문제https://www.acmicpc.net/problem/14502  풀이그래프의 크기가 작으므로 벽의 위치를 완전 탐색으로 지정할 수 있다백트래킹을 이용해 벽의 위치 3개를 지정하고 BFS 탐색으로 바이러스가 퍼진 후의 빈 칸의 수를 구한다 모든 빈 칸에서 3개의 빈칸을 구하는 시간 복잡도는 다음과 같다- n * m 중에서 1칸을 고른다- (n * m-1) 칸 중에서 1칸을 고른다- (n * m - 2) 칸 주엥서 1칸을 고른다따라서 64 * 63 * 62다 바이러스가 BFS를 사용하는 시간복잡도는 O(n * m)이다따라서 총 연산횟수는 64 * 63 * 62 * 64 = 15,998,976이므로 주어진 시간 내에 풀 수 있다  코드pypy312345678910111213141516171819202..

문제https://www.acmicpc.net/problem/2206  풀이BFS를 응용해서 문제를 해결한다어떤 칸에 도달했을 때, 벽을 부수거나 부수지 않거나 두 가지의 상태가 있다이것을 다음처럼 표현한다visited[y][x][벽을 부숨, 벽을 부수지 않음]visited[y][x][0]=0 # 벽을 부수지 않은 상태, 해당 위치를 방문하지 않은 상태visited[y][x][0]=1 # 벽을 부수지 않은 상태, 해당 위치를 방문한 상태visited[y][x][1]=0 # 벽을 부순 상태, 해당 위치를 방문하지 않은 상태visited[y][x][1]=1 # 벽을 부순 상태, 해당 위치를 방문한 상태 또한 최단 거리를 저장하기 위해 visited[y][x][?] 에는 이전 칸에 값 + 1을 해준다visit..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.acmicpc.net  풀이 bfs 탐색을 (1,1)에서 시작해서 (N,M)에 도착했을 때 지나가는 level의 수가 최소 횟수가 된다.result = (1,1)에서 (N,M)까지 이동할 때 지나야하는 최소 칸 수 라고 할 때,bfs 탐색을 진행하면서 현재 level에 해당되는 좌표들을 모두 방문한 후에 result 값을 증가시켜주면 된다. 현재 level에 해당하는 좌표를 모두 방문하려면, bfs 탐색에서 현재 큐에 저장되어 있는 데이터 수 만큼..

문제https://www.acmicpc.net/problem/14888  풀이백트래킹을 이용해 문제를 해결한다 백트래킹의 핵심 코드는 다음과 같다operator[i] -= 1backtracking(index + 1, sum)operator[i] += 1sum = temp해당 연산자는 사용했으므로 operator[i] -= 1을 해준다operator[i] == 0 이라면 연산자를 모두 사용했다는 뜻이다 이후 연산자를 1개 사용한 채로 backtracking(index + 1, sum)을 실행한다이는 다음 인덱스와 지금까지 계산한 결과값을 넘겨준다 다음으로 operator[i] += 1을 다시 해준다백트래킹 이전으로 연산자를 다시 선택하지 않은 상태로 만든다 마지막으로 sum 값을 다시 원래 값인 temp로..

문제https://www.acmicpc.net/problem/15649  풀이N과 M(3) 문제와는 달리 같은 숫자를 여러 번 사용할 수 없도록 조건식을 추가해야 한다  코드python123456789101112131415161718def backtracking(depth):    if depth == m:        print(*answer)        return    for i in range(1, n + 1):        if i in answer:            continue        answer.append(i)        backtracking(depth + 1)        answer.pop()  answer = [] n, m = map(int, input().split..

문제https://www.acmicpc.net/problem/15651  풀이다음 순서로 문제를 해결한다 1. 만들 수 있는 모든 수열을 구해야 하므로, 완전 탐색을 이용한다2. 수열의 길이는 m이고 중복되지 않게 오름차순으로 출력한다 재귀함수를 이용해 백트래킹 알고리즘으로 문제를 해결한다  코드python12345678910111213141516def backtracking(depth):    if depth == m:        print(*answer)        return    for i in range(1, n + 1):        answer.append(i)        backtracking(depth + 1)        answer.pop()  answer = [] n, m = ..

문제https://www.acmicpc.net/problem/1019  풀이숫자 n을 10으로 나눠가면서 1의자리에서 0~9까지의 숫자가 나오는 규칙을 찾아야 한다 숫자 n을 283으로 가정해서 예를 들었을 때현재 1의 자리는 3이므로0 ~ 2는 28 + 1(n / 10 + 1)번 나타난다4 ~ 9는 28(n / 10)번 나타난다3의 경우 28 + 1번 나타난다다음으로 283에서 10의 자리에 위치했던 수들의 개수를 세기 위해 10으로 나눈다그러면 28이고 현재 1의 자리는 8이므로0 ~ 7는 (2+1) x 10 번 나타난다 (원래 수에서 10의 자리였으므로 10을 곱해줘야한다)9는 2 x 10번 나타난다8의 경우 280, 281, 282, 283 총 4개의 숫자를 고려해줘야 한다. 이 경우는 따로 갯수..

문제https://www.acmicpc.net/problem/14500  풀이완전탐색으로 문제를 해결할 수 있다5가지 도형을 회전해서 얻을 수 있는 모든 도형을 종이 위에 올리면서 최대값을 구한다최대 시간은 500 * 500 * 19 * 4 = 19000000 이므로완전탐색으로 해결 가능하다 코드python12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152figures = [    [[0, 0], [0, 1], [1, 0], [1, 1]],    [[0, 0], [0, 1], [0, 2], [0, 3]],    [[0, 0], [1, 0], [2, 0], [3, 0]],    [[0,..

문제https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.www.acmicpc.net  풀이8*8 크기의 체스판을 두 개를 준비한다. W로 시작하는 체스판과 B로 시작하는 체스판을 준비한다.이 두 체스판을 M*N 크기의 보드에 번갈아 가면서 비교해 가면 된다. 1. M*N 보드의 왼쪽 끝(0,0)을 기준으로 8*8 크기 만큼 두 개의 체스판과 비교를 한다.2. 왼쪽 끝을 (0,1), (0,2), ..., (1,0), (1,1), ... 순으로 가능한 범위 내에서 바꿔준 후 ..

문제https://www.acmicpc.net/problem/1436  풀이완전탐색을 이용해 문제를 해결한다 규칙을 파악하면 다음과 같다666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, 6663, 6664규칙을 수학적인 규칙으로 접근하려면 오래걸린다따라서 1부터 숫자를 증가시켜서 666이 포함됐는지 확인한다 N의 최대값이 10,000이고, 이때 666 숫자는 266799이다 1 ~ 2666799까지 탐색과 666찾기가 최대 O(n^2) 시간 복잡도로 해결이 가능하다  코드python12345678910111213141516current = 0answer = 1 n = int(input()) while True:    if "666" in str(answer)..