📌 문제 조건오른쪽으로 한 칸, 아래쪽으로 한 칸만 이동할 수 있다.자원이 있는 지역을 1, 없는 지역을 0이라고 한다. 📌 구해야 하는 정답   로봇이 (1,1)이 (N,M)까지 이동하며서 캘 수 있는 최대 숫자를 구해야 한다. 📌 풀이 하기(n, m) 자리에서 캘 수 있는 최대 광석의 갯수는 바로 왼쪽인 (n, m - 1)의 최대 광석의 수와 바로 위인 (n - 1, m)의 최대 광석의 수 중에서 MAX의 값에 본인의 값을 더한 값과 같다고 볼 수 있다.따라서 dp의 점화식은 아래와 같다. D[ i ][ j ] = max(  D[ i - 1 ][ j ],  D[ i ][ j  - 1] ) +  S[ i ][ j ] 주의할 부분은 1열과 1행 각각의 D[ i ][ j ] 값은 그 이전의 값이 될 ..

▶ 문제 탐색하기재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다.  ◇ 입력첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)둘째 줄부터 N개 줄에는 그림이 주어진다. ◇ 원하는 출력 조건적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.가능한 시간복잡도  알고리즘 선택- BFS 알고리즘 사용▶ 코드 설계하기  ▶ 회차별 수정사항 ▶ 정답 코드import sysdx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]N = int(sys.stdin.readline())graph = []for _ in range(N): graph.append(list(sys.stdin.readline().strip()))def bfs(..

▶ 문제 탐색하기재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다.  ◇ 입력징검다리 개수 N (1~10,000 정수)N개의 징검다리에 쓰여진 자연수 ---> arr =[]시작 a번째 징검다리, 도착 b번째 징검다리 ◇ 원하는 출력 조건 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 만약 갈 수 없다면 -1 출력N : 나무판 길이 (1≤N≤100)M : 버섯 포자의 수 (0≤M≤1,000,000)K : 버섯이 자라는 최대 칸수 (1≤K≤108)버섯 포자를 최소 개수로 심을 때 농사가 가능하지 판단하고, 가능하면 남은 버섯 포자 개수를 출력하는 문제이다.가능한 시간복잡도  알고리즘 선택- BFS 알고리즘 사▶ 코드 설계하기위의 조건으로 버섯 포자를 심을 때 최소 개수만 이..

https://www.acmicpc.net/problem/1326난이도: 실버2▶ 문제 탐색하기재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다.  ◇ 입력징검다리 개수 N (1~10,000 정수)N개의 징검다리에 쓰여진 자연수 ---> arr =[]시작 a번째 징검다리, 도착 b번째 징검다리 ◇ 원하는 출력 조건 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 만약 갈 수 없다면 -1 출력  가능한 시간복잡도  알고리즘 선택- BFS 알고리즘 사▶ 코드 설계하기 1. 가장 먼저, arr[ a-1 ] 시작점 값과 뛰어야하는 전체 거리 ( b-a )를 찾는다.   2. 만약 전체 거리가 시작점 값으로 나누어 떨어진다면 한 번에 뛰어 건널 수 있다.①  if (b-a) % a..

https://www.acmicpc.net/problem/2805▶ 구해야하는 것입력: 나무의 수: N, 자를 나무의 총 길이: M (나무의 길이는 최대 2억...)         N개의 나무의 높이 (1억 보다 작거나 0이상이다)출력: 적어도 M만큼 가져가기 위해 설정한 높이의 최댓값(H)을 찾는다.!!▶ 풀이 탐색O(log H): 나무의 높이(H)를 이분 탐색한다.O(N): 각 나무마다 잘릴 수 있는지 확인한다.총 O(NlogH)의 시간 복잡도가 소요된다. 약 천만 이므로 시간 제한에 어긋나지 않음아이디어: 목재절단기 H가 클수록 가져갈 수 있는 나무 길이는 작아지고,  H가 작을수록 커진다.적절한 높이(H)를 찾을 때까지 이진탐색을 수행하며 반복해서 H를 조정한다.현재 이 높이로 자르면 조건을 만족..

https://www.acmicpc.net/problem/17266▶ 구해야하는 것N 길이의 굴다리에 M개의 가로등으로 전체 굴다리를 비춘다.가리기 위해서는 H 높이의 가로등이 좌우로 H만큼 비추고 있다.이 때 설치해야할 가로등의 최소 높이를 구하는 거다. ▶ 풀이 탐색O(M): 가로등마다 다 비출 수 있는지 확인O(N): 가로등의 높이 탐O(NM): 시간 복잡도가 소요됨. 약 10만^개의 연산이 필요해 시간 안에 불가능하다. -> 이분 탐색을 이용해야한다.O(log N): 가로등의 높이를 이분 탐색한다.O(M): 각 가로등마다 다 비출 수 있는지 확인한다.총 O(MlogN)의 시간 복잡도가 소요된다.1. 이분 탐색으로 가능한 최소 높이 찾기- 규칙: 가로등의 높이가 높아지면 비출 수 있는 거리가 길어지..

https://www.acmicpc.net/problem/2839 ▶ 문제 탐색하기전체 설탕의 양인 N을 3a + 5b 로 풀어내어서 (a+b)의 최솟값을 구하는 문제로 생각했다. 몫이 상대적으로 작은 a값을 중심으로 이중 for문을 이용해서 풀었다.  이중 for 문(아래)을 사용해 푼 문제가 while~else로 푼 문제(위)보다 시간이 엄청 오래걸렸다. O(nm) 시간 복잡도가 크긴 하다. ▶ 정답 코드 (이중 for 문)N = int(input())a = N // 5 # 5의 최대 몫b = N // 3 # 3의 최대 몫w = [] # 5a + 3b = 15가 가능한 (a+b)의 배열for i in range(a+1): for j in range(b+1): ..

https://www.acmicpc.net/problem/4963난이도: 실버2 ▶ 문제 탐색하기 알고리즘 선택- BFS 알고리즘 사용- DFS 알고리즘도 사용 가능하다▶ 코드 설계하기 ▶ 회차별 수정사항문제 조건에 대각선도 걸어갈 수 있는 조건이 있었다. 그렇면 dx, dy 좌표 정해주기▶ 정답 코드import syssys.setrecursionlimit(10 ** 4) #재귀쓸 때 널기d=[(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] #하부터 시계반대방향으로 순회, 하 대각선 우 대각선 상 대각선 좌 대각선def dfs(x, y): arr[x][y]=0 for i in range(8): nx = x + d[i][0] ..

https://www.acmicpc.net/problem/1326난이도: 실버2▶ 문제 탐색하기재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다.  ◇ 입력징검다리 개수 N (1~10,000 정수)N개의 징검다리에 쓰여진 자연수 ---> arr =[]시작 a번째 징검다리, 도착 b번째 징검다리 ◇ 원하는 출력 조건 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 만약 갈 수 없다면 -1 출력  가능한 시간복잡도  알고리즘 선택- BFS 알고리즘 사▶ 코드 설계하기 1. 가장 먼저, arr[ a-1 ] 시작점 값과 뛰어야하는 전체 거리 ( b-a )를 찾는다.   2. 만약 전체 거리가 시작점 값으로 나누어 떨어진다면 한 번에 뛰어 건널 수 있다.①  if (b-a) % a..

https://www.acmicpc.net/problem/5585난이도: ▶ 문제 탐색하기가로, 세로, 대각선으로 그을 수 있는 직선은 총 12개이다. 이중에서 3개를 택하는 조합은 12C3=220가지 이므로 경우의 수가 많지 않다. ◇ 입력 5X5의 빙고판을 입력받은 후, 2차원 배열로 저장한다. 사회자가 부르는 수를 1차원 배열로 저장한다. ◇ 원하는 출력 조건 1차원 배열에서 5개의 칸이 3번 채워지는 그 순간의 index+1을 출력한다.▶ 코드 설계하기 1. 위치 탐색: 사회자가 부르는 숫자가 2차원 배열의 어디에 위치해있는지 찾는다. 2. 해당 숫자의 index를 저장한다. Q. 이차원배열로 저장할지[[ i, j ], [ i1, j2] ,..].., dict의 형태로 {''row'':col, "..