하나씩 알아가기

이 문제는 직관적으로 이해하기가 정멀 어렵습니다. 예시를 보면서 식을 세워 문제를 풀어야 합니다. M=5, N=7, x=3, y=2 라고 하면 카잉달력의 총 날짜는 M*N = 35개(0~34)입니다. 시작점인 0에서 x를 더한 날짜가 최초날짜이고 최초날짜로부터 M번씩 간격을 두고 총 N번 날짜를 확인하면 됩니다. 이 N번 중 y 값이 일치하는 날짜가 몇 번째 인지를 찾는 것이 핵심입니다. 3+0부터 시작해서 3%7 = 3, (3+5)%7 = 1, (3+10)%7 = 6, (3+15)%7 = 4, (3+20)%7 = 2 이것을 for 문으로 잘 구현해야 합니다. 다시 말하면, x를 이용해 모든 해를 고려하지 않고, i X M + x의 형태만 조사하면 됩니다. #include using namespace s..

입력된 채널을 몇 번만에 입력할 수 있는 지 묻는 문제입니다. 그런데 제한이 있는데 바로 고장난 채널이 있을 경우 +나 -를 입력해서 대체합니다. 출력은 해당 채널로 리모컨을 돌리기 위해 누른 횟수의 최소값이 됩니다. 또한, 100번에서 시작됩니다. 그래서 99번으로 이동할 때 최소 횟수는 2번이 아니라 1번이다. 예를 들어 5457번으로 이동하고 싶는데 6, 7, 8번 버튼이 고장났습니다. 5, 4, 5, 5, +, +를 입력하면 이동하므로 6번입니다. N이 500000까지이므로 음수까지 고려하면 최대 1000000번까지 리모컨을 누를 수 있게 됩니다. 백만번까지 되는 경우를 모두 확인해 보면 답을 찾을 수 있습니다. 기본적으로 +나 -만 사용해서 버튼을 누르는 것이 최대 값이고 이것부터 생각해 봅니다..

이 문제는 DFS/BFS를 이용한 시뮬레이션 문제입니다. 좌표의 범위 내에서 육지의 지역을 순회하고 이동을 할 수 없으면 카운트를 올려주는 식으로 계산합니다. 말로 하면 간단한데 좌표에서 이동할 수 있는 경우(next position)를 모두 고려해야하므로 좌표의 정보를 구해줘야 합니다. 좌표 시뮬레이션 문제는 늘 그렇듯이 dx와 dy를 더해서 다음 좌표로 이동하기 때문에 dx = [-1,-1,-1,0,0,1,1,1] dy = [-1,0,1,-1,1,-1,0,1] 를 준비합니다. 그리고 이 문제의 경우 다음 지도에서 섬의 개수가 5가 아닌 3인 것을 볼 때 상하좌우 뿐만 아니라 대각선까지 고려해 주어야한다는 것은 알 수 있습니다. 처음에는 DFS를 이용해서 여덟번의 재귀를 하는 식으로 구현했는데... I..

연결 요소(Connected Component)의 개수를 구하는 문제입니다. 인접행렬을 이용해서 풀 수 있습니다. 인접 행렬의 요소를 모두 확인할 것인데(n * n) 시작 노드부터 dfs 함수에 넣고 확인하는데 한 회차를 다 돌면 return하고 연결 요소 카운트를 올립니다. 1부터 n까지를 반복하는데 방문하지 않은 곳만 dfs에 넣습니다. n, m = map(int, input().split()) adj = [[0 for _ in range(n+1)] for _ in range(n+1)] visited = [False] * (n+1) result = 0 for _ in range(m): x, y = map(int, input().split()) adj[x][y] = 1 adj[y][x] = 1 def ..

틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다. 노드, 간선, 시작점을 첫째 줄에 입력 받고 둘째 줄 부터는 간선의 개수만큼 두 정점의 번호를 입력 받습니다. 두 개의 리스트를 생성합니다. 연결 정보를 나타낸 2차원 리스트 방문 여부를 기록한 1차원 리스트 이 정점을 연결 정보를 인접 행렬(adjacent matrix)로 다음과 같이 나타낼 수 있습니다. 0 1 2 3 4 1 1 1 1 2 1 1 3 1 1 4 1 1 연결이 되어 있다면 1을 넣어주었습니다. 가장 핵심이 되는 부분은 방문하지 않은 노드면서 연결이 되어있는 노드를 방문해 나가는 것인데 dfs의 경우 재귀함수를 호출하고 bfs일 때는 큐에다가 넣어줍니다 from collections import deque n, m, v = map(i..

DFS(Depth-First-Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 동작 과정 ① 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. ② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 ③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ※ 동작 원리는 스택이지만 구현은 재귀 함수를 이용해서 하는 것이 더 간결합니다. def dfs(graph, v, visited): #현재 노드를 방문처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in grap..

인접한 두 사탕을 교환하여 그 때마다 사탕 길이를 계산하고 가장 긴 사탕 길이를 출력하면 해결할 수 있는 문제입니다. 양옆에 인접한 사탕을 스왑하고 가로 길이 확인 -> 갱신 세로 길이 확인 -> 갱신 스왑한 사탕을 되돌려 놓음 위아래로 인접한 사탕을 스왑하고 가로 길이 확인 -> 갱신 세로 길이 확인 -> 갱신 빨간 글씨로 쓴 부분은 반복되기 때문에 함수로 빼 주었습니다. 길이를 계산해 주는 함수에서 중요한 것은 내부 루프입니다. index가 범위를 벗어나지 않도록 0 ~ n-1(n-1미포함)까지 설정 해주고 인접한 두 사탕이 같은 사탕이면 count를 증가시켜 주고 다른 사탕이면 길이를 갱신하고 다음번 비교를 위해 count를 1로 초기화 시킵니다 파이썬의 함수 내부에 global 키워드를 사용하면 ..

E, S, M 은 각각의 범위를 가지고 있습니다. 그리고 그 범위를 넘어가면 1로 초기화 시켜주는 규칙만 지켜주며 전체를 카운트 해주는 변수를 결과로 출력해주면 됩니다. e, s, m = map(int, input().split()) year = 0 esm = [0, 0, 0] while esm[0] != e or esm[1] != s or esm[2] != m: year += 1 esm[0] += 1 esm[1] += 1 esm[2] += 1 if esm[0] == 16: esm[0] = 1 if esm[1] == 29: esm[1] = 1 if esm[2] == 20: esm[2] = 1 print(year) www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라..

점화식을 찾아봅시다. 그림을 보고 입력받은 수가 n이라 할 때, n-2번째 까지의 경우는 두 가지이고 n-1번째 까지의 경우는 한 가지입니다. 좀 더 자세히 말하면 n-2번째까지 타일이 채워진 경우에서 너비가 2인 블럭으로 채우면 n번째 항까지 채운 경우가 되고 n-1번째 까지 타일이 채워진 경우에서 너비가 1인 블럭으로 채우면 n번째 항까지 채운 경우가 되는 것입니다. 그래서 f(n) = 2 * f(n-2) + f(n-1) 이렇게 점화식을 구할 수 있습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[0] = 0 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(d..

10을 세 가지 연산을 이용하여 1로 만든다고 할 때 모든 경우 중에 가장 작은 수를 찾아내야 합니다. 10 -> 9 -> 8 -> 7 -> ... -> 1 (x) 10 -> 9 -> 3 -> 1 (o) * 점화식: 수열의 각각의 항들의 관계를 나타낸 식 모든 경우의 수를 고려할 경우 점화식을 떠올리는 방법을 생각해 내는 것이 좋은 방법이 될 수 있습니다. 이 문제의 경우 수를 줄일 수 있는 연산은 세 가지 밖에 없으므로 점화식은 이 경우를 포함하여 적어줘야 합니다. f(n) = 1 + min(f(n/3), f(n/2), f(n-1)) 그런데 가령, f(n/3)이 반드시 존재하는 값은 아닐 수 있지만 이렇게 점화식 형태로 표현이 가능한 경우 다이나믹 프로그래밍을 적용하여 문제를 해결하는 것이 가장 일반적..