본문 바로가기

알고리즘 (Python)

 (259)
[그리디 알고리즘] 1이 될 때까지 - 파이썬(python) 1이 될 때까지 난이도 : 下 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, k = map(int, input().split()) count = 0 while (n > 1): if (n % k == 0): n = n / k count = count + 1 else: n = n - 1 count = count + 1 print(count) 예시 # N, K을 공백을 기준으로 구분하여 입력 받기 n, k = map(int, input().split()) result = 0 // N이 K 이상이라면 K로 계속 나누기 while n >= k: # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기 while n % k != 0: n -= 1 result += 1 # K로 나누기 n //= k re..
[그리디 알고리즘] 숫자 카드 게임 - 파이썬(python) 숫자 카드 게임 난이도 : 下 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) result = [] for i in range(n): array = list(map(int, input().split())) result.append(min(array)) print(max(result)) 예시 # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) result = 0 # 한 줄씩 입력 받아 확인하기 for i in range(n): data = list(map(int, input().split())) # 현재 줄에서 '가장 작은 수' 찾기 min_value = min(data) # '가장 작..
[그리디 알고리즘] 큰 수의 법칙 - 파이썬(python) 큰 수의 법칙 (11399번) 난이도 : 下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m, k = map(int, input().split()) array = list(map(int, input().split())) count = 0 array.sort(reverse=True) first = array[0] second = array[1] while True: if (m == 0): break else: for i in range(k): count = count + first if (m == 0): break m = m - 1 count = count + second m = m - 1 print(count) 예시 # N, M, K를 공백을 기준으로 구분하여 입력 받..
[그리디 알고리즘] 당장 좋은 것만 선택하는 그리디 그리디 알고리즘 (탐욕법) - 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘 - 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 - 유형이 다양하기 때문에 암기가 아닌 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함 - 보통 코딩 테스트에서는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 문제에서 '가장 큰 순서대로'와 같은 기준을 알게 모르게 제시 - 대체로 위 기준은 정렬 알고리즘을 사용하여 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제 - '가장 큰 화폐 단위부터'와 같이 탐욕적으로 문제에 접근했을 때 정..
[CodeUp] 코드업 기초 100제 6098번 풀이 - 파이썬(python) 6098 : [기초-리스트] 성실한 개미(py) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다. 왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데, 그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다. 개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다. (오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.) 이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다. 미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로만 움직였다. 미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고, ..
[CodeUp] 코드업 기초 100제 6097번 풀이 - 파이썬(python) 6097 : [기초-리스트] 설탕과자 뽑기(py) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 부모님과 함께 놀러간 영일이는 설탕과자(설탕을 녹여 물고기 등의 모양을 만든 것) 뽑기를 보게 되었다. 길이가 다른 몇 개의 막대를 바둑판과 같은 격자판에 놓는데, 막대에 있는 설탕과자 이름 아래에 있는 번호를 뽑으면 설탕과자를 가져가는 게임이었다. (잉어, 붕어, 용 등 여러 가지가 적혀있다.) 격자판의 세로(h), 가로(w), 막대의 개수(n), 각 막대의 길이(l), 막대를 놓는 방향(d:가로는 0, 세로는 1)과 막대를 놓는 막대의 가장 왼쪽 또는 위쪽의 위치(x, y)가 주어질 때, 격자판을 채운 막대의 모양을 출력하는 프로그램을 만들어보자. 입력 첫 줄에 격자판의 세로(h), 가로(w)..
[CodeUp] 코드업 기초 100제 6096번 풀이 - 파이썬(python) 6096 : [기초-리스트] 바둑알 십자 뒤집기(py)) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 부모님을 기다리던 영일이는 검정/흰 색 바둑알을 바둑판에 꽉 채워 깔아 놓고 놀다가... "십(+)자 뒤집기를 해볼까?"하고 생각했다. 십자 뒤집기는 그 위치에 있는 모든 가로줄 돌의 색을 반대(1->0, 0->1)로 바꾼 후, 다시 그 위치에 있는 모든 세로줄 돌의 색을 반대로 바꾸는 것이다. 어떤 위치를 골라 집자 뒤집기를 하면, 그 위치를 제외한 가로줄과 세로줄의 색이 모두 반대로 바뀐다. 바둑판(19 * 19)에 흰 돌(1) 또는 검정 돌(0)이 모두 꽉 채워져 놓여있을 때, n개의 좌표를 입력받아 십(+)자 뒤집기한 결과를 출력하는 프로그램을 작성해보자. 입력 바둑알이 깔려 있는 ..
[CodeUp] 코드업 기초 100제 6095번 풀이 - 파이썬(python) 6095 : [기초-리스트] 바둑판에 흰 돌 놓기(설명)(py) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 기숙사 생활을 하는 학교에서 어떤 금요일(전원 귀가일)에는 모두 집으로 귀가를 한다. 오랜만에 집에 간 영일이는 아버지와 함께 두던 매우 큰 오목에 대해서 생각해 보다가 "바둑판에 돌을 올린 것을 프로그래밍 할 수 있을까?"하고 생각하였다. 바둑판(19 * 19)에 n개의 흰 돌을 놓는다고 할 때, n개의 흰 돌이 놓인 위치를 출력하는 프로그램을 작성해보자. 입력 바둑판에 올려 놓을 흰 돌의 개수(n)가 첫 줄에 입력된다. 둘째 줄 부터 n+1 번째 줄까지 힌 돌을 놓을 좌표(x, y)가 n줄 입력된다. n은 10이하의 자연수이고 x, y 좌표는 1 ~ 19 까지이며, 똑같은 좌표는..
[CodeUp] 코드업 기초 100제 6094번 풀이 - 파이썬(python) 6094 : [기초-리스트] 이상한 출석 번호 부르기3(py) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 정보 선생님은 오늘도 이상한 출석을 부른다. 영일이는 오늘도 다른 생각을 해보았다. 출석 번호를 다 부르지는 않은 것 같은데... 가장 빠른 번호가 뭐였지? 출석 번호를 n번 무작위로 불렀을 때, 가장 빠른 번호를 출력해 보자. 단, 첫 번째 번호와 마지막 번호가 몇 번인지는 아무도 모른다. 음수(-) 번호, 0번 번호도 있을 수 있다. 입력 번호를 부른 횟수(n, 1 ~ 10000)가 첫 줄에 입력된다. n개의 랜덤 번호(k)가 두 번째 줄에 공백을 사이에 두고 순서대로 입력된다. 출력 출석을 부른 번호 중에 가장 빠른 번호를 출력한다. 입력 예시 10 10 4 2 3 6 6 7 9..
[CodeUp] 코드업 기초 100제 6093번 풀이 - 파이썬(python) 6093 : [기초-리스트] 이상한 출석 번호 부르기2(py) 시간 제한 : 1초 메모리 제한 : 128 MB 문제 설명 정보 선생님은 수업을 시작하기 전에 이상한 출석을 부른다. 학생들의 얼굴과 이름을 빨리 익히기 위해 번호를 무작위(랜덤)으로 부르는데, 영일이는 선생님이 부른 번호들을 기억하고 있다가 거꾸로 불러보는 것을 해보고 싶어졌다. 출석 번호를 n번 무작위로 불렀을 때, 부른 번호를 거꾸로 출력해 보자. 입력 번호를 부른 횟수(n, 1 ~ 10000)가 첫 줄에 입력된다. n개의 랜덤 번호(k, 1 ~ 23)가 두 번째 줄에 공백을 사이에 두고 순서대로 입력된다. 출력 출석을 부른 번호 순서를 바꾸어 공백을 두고 출력한다. 입력 예시 10 10 4 2 3 6 6 7 9 8 5 출력 예시 5 8..

티스토리툴바