모카의 촉촉한 개발 로그

1이 될 때 까지 어떠한 수 N,K가 입력이 들어오면 두가지의 연산을 통해 N의 값을 1로 만드는 과정 중 연산의 최소 횟수를 구하는 문제. 단, 두번째 연산은 N이 K로 나누어 떨어 질때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K 로 나눈다. 나의 코드 n,k=map(int,input().split()) cnt =0 while n!=1: if n%k==0: n=n//k cnt+=1 else: n=n-1 cnt+=1 print(cnt) '최소 회수' 라는 단어에서 그리디 알고리즘을 떠올렸다. 또한 두가지 연상 종류 중 뺴기 보단 나누기가 횟수를 줄이는데 효과가 좋다. 우선 2번 연산이 가능한지(n이k로 나누어 지는지) 확인 후 가능하면 2번을 하고 2번 연산이 안되면 1번 연산을 한다. ..

숫자 카드 게임 가장 높은 숫자를 뽑는 게임. - NxM형태로 놓여있으며 N은 행 M 은 열을 뜻한다. - 먼저 행을 선택한다 - 그 다음 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다. 입력 예시) 3 3 3 1 2 4 1 4 2 2 2 출력 예시) 2 입력 예시) 2 4 7 3 1 8 3 3 3 4 출력 예시) 3 나의 코드 n,m=map(int, input().split()) arr=[list(map(int,input().split())) for _ in range(n)] res=[0]*n for i in range(n): res[i]=min(arr[i]) print(max(res)) 가장 높은 숫자와 가장 낮은 숫자 라는 단어가 보여 바로 그리디임을 직감했다. 또한 결국 출력 값은 '모든..

큰수의 법칙 - 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙 - 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. - 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른것으로 간주 입력 예시) 5 8 3 2 4 5 4 6 출력 예시) 46 나의 코드 n,m,k=map(int,input().split()) arr=list(map(int,input().split())) arr.sort(reverse=True) s=0 cnt=0 while True: for _ in range(k): if cnt==m: print(s) break s+=arr[0] cnt+=1 if cnt==m: print(s) break s+=arr[..

그리디 알고리즘(Greedy Algorithm) 현재 상황에서 지금 당장 좋은 것만 고른다. 정당성 분석이 중요하다.(단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토) 일반적인 상황에서 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 , 이론을 추론할 수 있어야 풀리도록 출제가 된다. 정렬과 함꼐 주로 사용이 되며 '가장 큰', '가장 작은' 과 같은 기준을 문제에서 제시해 준다. 예시 문제) 거스름돈 해결 아이디어 : 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면된다. 정당성 분석 가장 큰 화페 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까? => 가..

컴퓨터 개수 현수는 종합학원에 다니고 있습니다. 현수가 다니는 종합학원은 서버 컴퓨터가 있는 큰 교실 과 수학을 공부하는 작은 교실로 되어 있다. 서버 컴퓨터가 있는 큰 교실의 모든 컴퓨터는 서 버와 직간접적으로 연결되어 인터넷이 되지만 수학교실에 있는 컴퓨터들은 서버와 연결되어 있지 않아 인터넷은 되지 않는다. 서버 컴퓨터는 1번 컴퓨터이다. 1, 2, 3, 4, 5, 6번 컴퓨터는 인터넷이 되지만 7, 8, 9, 10, 11번 컴퓨터는 수학교실에 있는 컴퓨터들로 인터넷이 되지 않는다. 수학교실에 있는 컴퓨터들끼리는 서로 연결이 되어 있을 수도 있고, 연결이 되어 있지 않을 수도 있다. 매개변수 n에 학원의 컴퓨터 총 개수가 주어지고, 매개변수 edges에 컴퓨터간 연결정보가 주 어지면 현수가 다니는 ..

• 그래프는 G(V, E)로 정의하고, V(Vertext : 정점)과 E(Edge : 간선) 의 집합을 의미한다. • 연결되어 있는 원소들간의 관계를 표현하는 자료구조이다. 인접행렬 2차원 배열을 이용해 그래프를 표현하는 방법 1) 무방향 그래프 입력 형식 : edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]] graph = [[0] * (n+1) for _ in range(n+1)] for [a, b] in edge: graph[a][b] = 1 graph[b][a] = 1 2) 방향 그래프 입력 형식 : edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]] graph = [[0] * (n+1) for _ in range(n+1)] fo..

검정색 영역구하기 5 * 5 이차원 배열에 모니터 화면을 표현합니다. 모니터의 화변은 최초 검정색과 흰색으로만 표현되어 있습니다. 검정색은 1, 흰색은 0으로 표현됩니다. 상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다. 화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2곳입니다. 매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 영역은 총 몇 개가 있는지 구하여 반환하는 프로그램을 작성하세요. 제한사항: • 검정색 영역은 1개 이상 반드시 존재합니다. 나의 코드 from collections import deque def solution(board): answer = 0 dx=[-1,0,1,0] dy=[0,1,0,-1] dq=deque() for i in..

최소 점프 현수는 놀이터에서 놀다가 집으로 가려고 합니다. 놀이터의 위치와 집의 위치가 수직선상의 좌표 점으로 주어집니다. 놀이터는 수직선상의 0지점입니다. 현수는 놀이터에서 스카이콩콩을 타고 점프를 하면서 집으로 이동하려고 합니다. 점프는 다음과 같은 규칙으로 합니다. 1) 현재 지점에서 앞으로 +1 만큼 점프이동할 수 있습니다. 2) 현재 지점에서 뒤쪽으로 -1 만큼 점프이동할 수 있습니다. 3) 현재 지점에서 앞쪽으로 +5 만큼 긴 점프이동을 할 수있습니다. 매개변수 home에 현수의 집의 위치가 주어지면 놀이터에서 집까지 최소 몇 번의 점프로 집에 도착할 수 있는지 최소 점프횟수를 구하여 반환하세요. 제한사항: • 수직선의 좌표는 0부터 10,000까지입니다. • 현수가 집으로 반드시 갈 수 있습..

픽셀수 구하기 5 * 5 이차원 배열에 모니터 화면을 표현합니다. 모니터의 화변은 최초 검정색과 흰색으로만 표현되어 있습니다. 검정색은 1, 흰색은 0으로 표현됩니다. 상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다. 화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2이고, 첫 번째 영역의 픽셀수(격 자수)는 5개이고, 두 번째 영역의 픽셀수는 3개입니다. 매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 각 영역의 픽셀수를 순서대로 배열에 담아 반환하세요. 영역의 순서는 각 영역의 행번호, 열번호가 가장 작은 픽셀 을 기준으로 행번호가 작은 것부터이며 행번호가 같을 경우 열 번호가 작은 영역 순으로 배열 에 담습니다. 나의 코드 dx=[-1,0,1,0] ..

검정색 영역구하기 5 * 5 이차원 배열에 모니터 화면을 표현합니다. 모니터의 화변은 최초 검정색과 흰색으로만 표현되어 있습니다. 검정색은 1, 흰색은 0으로 표현됩니다. 상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다. 화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2곳입니다. 매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 영역은 총 몇 개가 있는지 구하여 반환하는 프로그램을 작성하세요. 제한사항: • 검정색 영역은 1개 이상 반드시 존재합니다. 나의 코드 def DFS(x,y,board): board[x][y]=0 dx=[-1,0,1,0] dy=[0,1,0,-1] for k in range(4): nx=x+dx[k] ny=y+dy[k] if 0