본문 바로가기

분류 전체보기464

[백준] 25501번 재귀의 귀재 사용 언어 - Python3 25501번: 재귀의 귀재 (브론즈2, 재귀) 문제 ★재귀 문제★ 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 정답 문제에 나온 코드를 파이썬으로 구현하는 문제 (코드 풀이) recursion 함수에서 문자열s의 첫(0) 문자와 끝(len(s)-1) 문자가 같은지 재귀적으로 계속 비교한다. 비교하려는 문자열의 인덱스들이 뒷문자가 더 인덱스가 작다면, 1을 return한다. 첫 문자와 끝 문자가 같지않다면, 0을 return한다. 첫 문자와 끝 문자가 같다면, 그 다음 문자들을 비교한다. recursion(s,l+1,r-1) # 정답.. 2023. 1. 23.
[백준] 10872번 팩토리얼 사용 언어 - Python3 10872번: 팩토리얼 (브론즈5, 재귀) 문제 ★재귀 문제★ 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정답 재귀 함수 또는 for문으로 처리하기 (코드 풀이) 1. 정답1 - 재귀함수 def factorial(n) 재귀함수 정의하기 n이 0보다 클때만 result = n*factorial(n-1) # 정답1 n = int(input()) def factorial(n): result = 1 if n > 0 : result = n * factorial(n-1) return result print(factorial(n)) 2. 정답2 - for문 n이 0보다 클때만 i를 한개씩 증가.. 2023. 1. 23.
[백준] 12015번 가장 긴 증가하는 부분 수열 2 사용 언어 - Python3 120154번: 덱 (골드5, 큐) 문제 ★이분 탐색 문제★ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 정답 이분탐색으로 시간복잡도 O(nlogn) 개선 (코드 풀이) ans=[0] 리스트에 값 비교하면서 append 해주기 ans[-1] ans의 가장 마지막 값이 i보다 작으면 ans에 append해준다. 그렇지 않다면, 이분탐색으로 인덱스 mid값을 조정해준다. ans[mid]가 i보다 작으면 start = mid+1, i보다 크면 end = mid로 범위를 업데이트해준다... 2023. 1. 23.
[백준] 5430번 AC 사용 언어 - Python3 5430번: 덱 (골드5, 큐) 문제 ★큐 문제★ 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 정답 큐 reverse 처리하기 (코드 풀이) 1. 입력 형태 주의하기 input 형태가 [1,2,3,4]이다. 우리는 deque의 입력값으로 '1','2','3','4'를 넣기 위해 데이터를 가공해줘야한다. 앞과 끝의 대괄호 []는 없애고, 컴마(,)로 split하여 인식하여 deque의 입력값을 넣어준다. 2. 시간복잡도 reverse 해결하기 R 함수는 전체 큐를 q.reverse() 해야하기 때문에 시간 초과된다. reverse 해주.. 2023. 1. 22.
[백준] 1021번 회전하는 큐 사용 언어 - Python3 10866번: 덱 (실버4, 큐) 문제 ★큐 문제★ 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 정답 deque([]) 사용하기 (코드 풀이) 위치값이 큐의 첫번째 원소와 같으면 큐 앞에 있는 원소를 pop한다. q의 i번째 위치값 q 길이의 절반 인 경우, 맨 오른쪽의 원소를 q의 맨 앞으로 appendleft 한다. q의 첫.. 2023. 1. 22.
[백준] 10866번 덱 사용 언어 - Python3 10866번: 덱 (실버4, 큐) 문제 ★큐 문제★ 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정답 deque([]) 사용하기 (코드 풀이) 큐의 맨 앞(왼쪽)에 push => q. appendleft 큐의 맨 앞(왼쪽에 pop => q.popleft q는 앞선 명령어들로 길이가 계속 달라지므로 인덱싱할 때 주의해야한다. 가장 오른쪽 값 출력 => d[len(d)-1] # 정답 import sys from collections import deque d = de.. 2023. 1. 22.
[백준] 1966번 프린터 큐 사용 언어 - Python3 1966번: 프린터 큐 (실버3, 큐) 문제 ★큐 문제★ 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 정답 k-1명을 popleft() 하면서 바로 append해주는 deque([]) 문제 (코드 풀이) 1. 변수 선언 n 문서의 개수 / n 문서에서 m이 있는 인덱스 찾기! 가장 중요도가 높은, 큰 숫자를 best에 입력한다. q의 가장 왼쪽에 있는 숫자를 pop하고 front에 입력한다. 2. 맨 왼쪽의 숫자(front) 와 가장 큰 숫자(best)를 비교한다. m앞에 있는 숫.. 2023. 1. 22.
[백준] 11866번 요세푸스 문제0 사용 언어 - Python3 11866번: 요세푸스 문제 0 (실버5, 큐) 문제 ★큐 문제★ 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 정답 k-1명을 popleft() 하면서 바로 append해주는 deque([]) 문제 (코드 풀이) popleft()를 k번째 전까지 총 k-1번 진행한다. popleft() 된걸 바로 append하면서 뒤에 순차적으로 추가해준다. 마지막 k번째도 popleft()로 삭제하면서 그 값을 정답에 append한다. 마지막까지 한 원소만 남았을 때까지 while문을 진행한다. 마지막 한 원소만 제외하고 answer를 출력한다. answer의 마지막 원소는 따.. 2023. 1. 22.
[백준] 2164번 카드2 사용 언어 - Python3 2164번: 큐 2 (실버4, 큐) 문제 ★큐 문제★ 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 정답 deque([]) 문제 (코드 풀이) 1. 시간제한 & queue.popleft() 파이썬 라이브러리 중 collections의 deque로 q를 구현하기 import sys from collection import deque n = int(sys.stdin.readline()) q = deque([]) pop 명령어가 입력되었을 때, 큐에서 가장 앞(왼쪽)에 있는 정수를 빼.. 2023. 1. 22.
[백준] 18258번 큐 2 사용 언어 - Python3 18258번: 큐 2 (실버4, 큐) 문제 ★큐 문제★ 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정답 deque([]) 문제 (코드 풀이) 1. 시간제한 import sys n = int(sys.stdin.readline()) from collection import deque deque로 queue를 구현한다. queue = deque([]) 2. queue.popleft() pop 명령어가 입력되었을 때, 큐에서 가장 앞(왼쪽)에 있는 정수를 빼고.. 2023. 1. 21.

티스토리툴바