더보기 준비운동 PART2. 약점 체크 문제풀이를 쭉쭉하기 전, 기본 알고리즘을 잘 습득했는지 점검할 수 있는 문제를 소개합니다. 뼈대 문제는 시간을 두고 반복 구현하여 손에 익혀서 응용문제가 나왔을 때 유연하게 대처할 수 있는 생각을 길러야 합니다. 재귀 탐색의 기본: 연산자 끼워넣기 (🥈실버 1티어) 스택의 응용: 괄호의 값 (🥈실버 2티어) 시뮬레이션 기본: 빗물 (🥇 골드 5티어) 완전탐색의 유연한 생각: 가르침 (🥇 골드 5티어) 그리디의 기본: 멀티탭 스케줄링 (🥇 골드 2티어) 투 포인터의 기본: 부분합 (🥇골드 4티어) 벨만포드 뼈대문제: 최소비용 구하기 (🥇 골드 5티어) Prime, Kruskal 뼈대문제: 최소 스패닝 트리 (🥇 골드 4티어) KMP 뼈대문제: 부분 문자열 (🥇 골드 ..
2609번: 최대공약수와 최소공배수 (🥈 실버 5티어) 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net a, b = map(int, input().split()) def GCD(a, b): if b == 0: return a return GCD(b, a % b) gcd = GCD(a, b) print(gcd) print(a * b // gcd) 유클리드 호제법. 처음 접근은 실제 최대공약수, 최소공배수 구하는 식으로 처음 부터 다 따졌는데, 시간 초과 남. 최소공배수는 두 수의 곱을 최대공약수로 나누면 됨. 2693번: N번째 큰 수 (🥈 실버 5티어) 2693번: N번째 큰..
3460번: 이진수 (🥉 브론즈 3티어) 3460번: 이진수 양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다. www.acmicpc.net t = int(input()) testCase = [] for i in range(t): testCase.append(int(input())) for i in testCase: temp = i count = 0 while True: if temp == 1: print(count) break if temp % 2 == 1: print(count, end=" ") temp = temp // 2 count += 1 bin(), 직접 풀어볼 ..
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 2시간 30분 잡고 풀었음 해결 과정 예시 한 번 그려서 보고, 글로 되어 있는 것을 그대로 코드로 구현하면 되는 문제. 마지막에 direction 행, 열 바꿔놔서 답이 안나왔었음 ㅋ 나의 풀이 from collections import deque direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] def changeDirection(next, cur): if next == 'D': next_direction_index = direct..
코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 해결 과정 나의 풀이 import math import itertools # 소수 판별 함수 def isPrimeNumber(number): if number == 1 or number == 0: return False for i in range(2, int(math.sqrt(number)) + 1): # n의 제곱근을 정수화 시켜준 후 + 1 if number % i == 0: return False return True # numbers로 만들..