Jaeryong

1080번: 행렬 풀이어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집어 똑같이 만드는 것이기 때문에, n-2, m-2 까지만 탐색을 하면서,matrix1[i][j] == matrix2[i][j]의 여부를 확인하고 일치하지 않는다면 뒤집어 주면된다.코드import sysinput = sys.stdin.readlinen,m = map(int, input().split())matrix1 = [list(input().rstrip()) for _ in range(n)]matrix2 = [list(input().rstrip()) for _ in range(n)]def flip(x,y): for i in range(x, x+3): for j in range(y, y+3): if matrix1[i..

1946번: 신입 사원 풀이A 지원자 보다 서류 점수, 면접 점수 모두가 높은 B 지원자가 있다면, A 지원자는 신입사원 채용에서 선발될 수 없다.때문에 서류 점수를 기준으로 정렬하고 면접 점수를 하나씩 비교해 가면서 검사하면 되겠다고 생각했다.코드import sysinput = sys.stdin.readlinet = int(input())for _ in range(t): n = int(input()) grades = [list(map(int, input().split())) for _ in range(n)] grades.sort() cnt = 1 standard = grades[0][1] for i in range(1,n): if grades[i][1]  문제를 풀고 다른 사람들은 ..

1261번: 알고스팟 사용 알고리즘: 0-1 BFS코드from collections import dequem,n = map(int,input().split())grid = [list(input().strip()) for _ in range(n)]visited = [[False]*m for _ in range(n)]dx = [0,0,1,-1]dy = [1,-1,0,0]def bfs(): q=deque() q.append((0,0,0)) visited[0][0] = True while q: x,y,smash = q.popleft() if x == n-1 and y == m-1: return smash for k in range(4): nx = x+dx[k]..

16953번: A->B 사용 알고리즘: 그리디그리디 알고리즘(Greedy Algorithm)은 '탐욕(Greedy)'이라는 이름에 알맞게 지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘을 의미한다. 모든 경우 최적해를 보장하지는 못하지만, 드물게 최적해를 결과로 내는 경우도 있다. 합리적인 시간 내로 최적에 가까운 해답을 찾을 수 있다는 점에서 유용한 알고리즘이다. 그리디 알고리즘이 잘 작동하는 문제들은 이전의 선택이 이후의 선택에 영향을 주지 않는 문제들이 많다.물론 꼭 그렇지 않더라도 괜찮은 정답을 찾을 수 있는 알고리즘이다. 다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데,DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 ..

1149번: RGB거리 사용 알고리즘: DP 동적계획법(Dynamic Programming) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다.  때문에 동적 계획법을 적용하기 위해서는, 두 가지 속성을 만족시켜야 한다.부분 반복 문제 (Overlapping Subproblem)최적 부분 구조 (Optimal Substructure)DP는 주로 Memoization기법을 활용한 Bottom-Up 방식으로 구현한다. 코드import sysn = int(input())# r g b 순서costs = [list(map(int, input().split())) ..

1584번: 게임 사용 알고리즘: 0-1 BFS 0-1 BFS는 가중치가 0, 1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘이다. 최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간 복잡도가 O(ElogE) 또는 O(ElogV)인 반면에, 0-1 BFS는 O(V+E)의 시간 복잡도로 문제를 해결할 수 있다. 일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 그렇기 때문에 결과 값이 방문 횟수의 최소가 아닌 가중치의 최소인 경우를 찾기 위해서는 가중치가 낮은 경로부터 탐색해야 한다.코드from collections import dequeimport sysinput = sys...