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/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/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/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)..

문제https://www.acmicpc.net/problem/2630  풀이분할 정복으로 문제를 해결한다 (0~n, 0~n) 구역이 모두 같은 색이면 해당 색깔의 종이 수를 1 더하고 함수를 종료한다모두 같은 색이 아니라면 다음 4구역으로 나눈 후 각 구역에서 모두 같은 색인지 확인한다(0~n/2, 0~n/2)(n/2~n, 0~n/2)(0~n/2, 0/2~n)(n/2~n, n/2~n)  코드python1234567891011121314151617181920212223242526272829def solve(y, x, n):    global white, blue    reference_color = color_paper[y][x]     for i in range(y, y + n):        for j..

문제https://www.acmicpc.net/problem/2477  풀이육각형의 빈 공간을 채워서 큰 직사각형의 넓이를 구한 후, 빈 공간의 직사각형의 넓이를 구해서 빼준다 입력에서 방향이 1번만 나오는 가로와 세로 길이가 가장 긴 길이다이를 이용해서 빈 공간을 채웠을 때 가장 큰 직사각형의 넓이를 구한다 빈 공간의 직사각형 넓이는 다음을 이용해 구한다가장 긴 가로 길이 인덱스에서 +3을 하면 빈 공간의 세로 길이 인덱스가 나온다가장 긴 세로 길이 인덱스에서 +3을 하면 빈 공간의 가로 길이가 나온다이를 이용해서 빈 공간에 직사각형의 넓이를 구할 수 있다  코드python12345678910111213141516171819202122232425directions = []lengths = []max_a..

문제https://www.acmicpc.net/problem/1489  풀이그리디 문제다 a[i]의 값보다 작은 수가 b에 존재한다면, 그 중에서 가장 큰 값을 이겨야 한다그래야 무승부를 최대한 적게 가져가면서 승리를 최대한 많이 가져가고, 점수를 최대한 많이 가져갈 수 있다 구현은 먼저 승리하는 경우의 점수를 더하고, 마지막에 무승부하는 경우에 점수를 더한다  코드python123456789101112131415161718192021222324252627282930313233343536result = 0csort_a = [0] * 1002csort_b = [0] * 1002 n = int(input())a = [int(x) for x in input().split()]b = [int(x) for x i..

문제https://www.acmicpc.net/problem/1071  풀이그리디 문제다사전 순으로 가장 앞선 것을 출력하기 위해 배열이 오름차순으로 정렬되어야 한다이를 위해 계수정렬을 통해 배열을 정렬한다 다음 규칙을 적용한다a[i] 값에 대하여1. a[i] + 1 값이 배열에 존재하면1-1. a[i] + 2 이상의 값 k가 배열 안에 존재하면, a[i] 값을 전부 출력하고 k를 출력한다1-2. a[i] + 2 이상의 값이 배열 안에 존재하지 않으면, a[i] + 1 값을 한번 출력한다 2. a[i] + 1 값의 배열에 존재하지 않는다면 a[i] 값을 전부 출력한다  코드python12345678910111213141516171819202122232425262728293031323334353637383..