하나씩 알아가기

이 문제는 직관적으로 이해하기가 정멀 어렵습니다. 예시를 보면서 식을 세워 문제를 풀어야 합니다. 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번까지 리모컨을 누를 수 있게 됩니다. 백만번까지 되는 경우를 모두 확인해 보면 답을 찾을 수 있습니다. 기본적으로 +나 -만 사용해서 버튼을 누르는 것이 최대 값이고 이것부터 생각해 봅니다..

가장 첫번째 예시를 보면 1을 네 장 사서 4가 되는 것 보다 두장 짜리를 두 번 사서 4를 만드는 것이 4 < 5 * 2 로 금액이 더 큰 것을 알 수 있습니다. 작은 문제로 나눠서 생각하는 것이 중요합니다. 예를 들어 세번째 카드를 구매하면 N개 중 3이 소모되는 것 입니다. 그러면 나머지 N-3개에 대한 dp를 출력하면 됩니다. dp를 갱신시켜나가는데 현재카드와 [N-현재카드의 번호]의 dp값을 비교해서 더 큰 것으로 갱신시키면 됩니다. n = int(input()) card = list(map(int, input().split())) card.insert(0, 0) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for j in range(1, i+1..

토마토가 존재하는 곳으로부터 상하좌우로 하루에 한 칸씩 익어나가는데 며칠이 걸리는 것인지 구하는 문제입니다. 기본적으로 지난번에 풀어본 "미로탐색(BOJ_2178)" 문제와 비슷합니다. 하지만 추가로 생각해야 할 문제가 있었는데 여러 곳에서 토마토가 익어 나갈 수 있다는 점(미로 탐색 문제와 다르게 한 시작점에서 탐색을 해나가지 않는다)입니다. 그래서 토마토 밭에서 1인 곳을 찾아서 큐에다 다 넣어주고 너비탐색을 한 후(미로탐색과 동일하게 1씩 증가시킵니다) 너비탐색이 끝났는데 0인 경우는 -1을 출력하고 얼마나 걸리는 지 구할 때는 단순히 토마토 밭에서 최댓값을 구하면 됩니다. if days < tomatoes[i][j]: days = tomatoes[i][j] 파이썬 삼항 연산자(Ternary ope..

이 문제는 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 ..

입력 받은 수를 제곱수의 합으로 나타낼 때 각 항(반드시 양의 정수의 제곱)의 수의 최소값을 구하는 문제입니다. 수 1 2 3 4 5 6 7 8 ... 항의 개수 1 2 3 1 2 3 4 2 ... DP 테이블을 갱신시켜 나가는데 바깥 루프에서는 dp[i] = i 즉, 그 수 만큼의 값으로 채워주고 이것이 최댓값입니다. 안쪽 루프에서는 더 작은 횟수로 줄일 수 있을 때 갱신 해 나갑니다. dp[i] = min(dp[i], dp[i-j**2] + 1) 이것이 가장 핵심이 되는 구문인데 이 식을 생각해 내는것이 정말 어려운 것 같습니다. 여기서 +1을 해주는 이유는 어떤 수든지 최소 한 개의 항으로는 나타내야 하기 때문입니다. 즉 dp[x] = 0 은 불가능합니다. 1부터 시작합니다. n = int(inpu..

틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다. 노드, 간선, 시작점을 첫째 줄에 입력 받고 둘째 줄 부터는 간선의 개수만큼 두 정점의 번호를 입력 받습니다. 두 개의 리스트를 생성합니다. 연결 정보를 나타낸 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..

n = int(input()) dp = [0 for _ in range(91)] dp[1] = 1 dp[2] = 1 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 0으로 시작하지 않으면서 11을 부분 문자열로 갖지 않는 수를 이친수라 합니다. 일단 낮은 차수의 항들을 수동으로 구해줍시다. 1 2 3 4 1 10 100 101 1000 1010 1001 첫번째 두번째 항을 주목해 보면 한자리 수 이친수에 01을 붙이고 두자리 수 이친수에 0을 붙이면 101, 100으로 세자리 수의 이친수가 되는 것을 발견할 수 있습니다. 두자리 수 이친수에다가 01을 붙이고 세자리 수 이친수에 0을 붙이면 1001, 1000, 1010으로 네자리 수의 이친..