본문 바로가기

프로그래밍/알고리즘126

백준 1629 - 곱셈 파이썬 문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제가 단 2줄이다 이해도 쉬워서 엄청 빨리 풀줄 알았는데... 어려워서 다른 사람 코드 참고했다... 직접 계산한다면 시간초과가 날 문제이다 def dac(a, b, c): if b == 1: return a % c # b가 1일 때 a를 c로 나눈 나머지 반환 if b % 2 == 0: return (dac(a, b // 2, c) ** 2) % c # b가 짝수일 때, dac(a, b // 2, c)를 제곱한 값에 c로 나눈 나머지 반환 else: return ((dac(a, b // 2, c) ** 2) * a) .. 2023. 4. 7.
알고리즘 최강자 찾기 알고리즘 문제를 풀다가 갑자기 궁금해져서 알고리즘 별로 시간복잡도와 공간복잡도 측면에서 가장 우수한 것이 무엇인지 찾아보았다 역시 문제 상황마다 조건이 달라서 '모든 알고리즘 중 1등'이런 건 없었다 물론, 시간복잡도가 가장 낮은 대표적인 상수시간알고리즘같은 건 논외로 했다(코딩테스트에 단독으로 안 나오니까) 분야별로 살펴본 알고리즘 최강자 정렬 알고리즘 시간 복잡도 측면에서 퀵소트(QuickSort)가 평균적으로 가장 우수 최악의 경우에는 힙소트(HeapSort)가 우수 공간 복잡도 측면에서는 병합정렬(MergeSort)이 우수 그래프 알고리즘 최단경로를 찾는 문제에서는 다익스트라(Dijkstra) 알고리즘이 가장 효율적 최소 스패닝 트리(Minimum Spanning Tree)를 찾는 문제에서는 크루.. 2023. 4. 5.
백준 14501 - 퇴사 파이썬 문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 해결 코드 # 변수 입력 받기 n = int(input()) # 총 상담 일수 arr = [list(map(int, input().split())) for _ in range(n)] # 각 상담 일정 정보를 담은 리스트 # DP를 위한 초기화 dp = [0 for _ in range(n+1)] # 각 상담 일자별 최대 수익 # DP 계산 for i in range(n-1, -1, -1): # 역순으로 탐색 # 현재 상담을 진행할 수 없는 경우 if i + arr[i][0] > n: dp[i] = dp[i+1] # 상담을 하지 않음 # 현재 상담을 진행할 수 있는 경우 else: # 상담을 하는 .. 2023. 3. 28.
백준 9465 - 스티커 파이썬 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 아이디어(구현은 안하고 우선 생각만 해봄) - 약간 그리디 스타일 제일 큰거 고르고 위, 아래, 왼쪽, 오른쪽 값 삭제 그리고 남은 것들 중 제일큰거 고르고 똑같이 위, 아래, 왼쪽, 오른쪽 값 삭제해서 모든 원소가 사라지면 멈추는 함수를 만든다 - 누적값을 메모하면서 탐색하기 대각선 값을 경우의 수로 두고 메모하면서 탐색하기 - bfs로 풀기 해결코드 t = int(input()) for i in range(t): s = [] n = int(i.. 2023. 3. 27.
이진 탐색(Binary Search) 이진 탐색 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 O(logN) 전제 조건 : 데이터가 '정렬' 되어 있어야 함 Tree 자료구조로 데이터를 저장하면 이진 탐색과 같은 기법으로 빠르게 탐색이 가능 재귀함수로 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start+end) // 2 # 찾은 경우 중간점 인덱스 변환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, start, mid-1) # 중간점의 값보다.. 2023. 3. 21.
프로그래머스 - 크레인인형뽑기게임 파이썬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 def solution(board, moves): stacklist = [] answer = 0 for i in moves: for j in range(len(board)): if board[j][i-1] != 0: stacklist.append(board[j][i-1]) board[j][i-1] = 0 if len(stacklist) > 1: if stacklist[-1] == stacklist[-2]: stacklist.pop(-1) stacklist.pop(-1) answer += 2 brea.. 2023. 3. 20.
프로그래머스 - 명예의 전당(1) 파이썬 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. 힙을 이용한 풀이 1. 점수 리스트를 힙에 추가 2. 힙 자료구조의 원소의 개수 > k일 경우 힙 구조에서 점수가 가장 낮은 원소의 값을 제거 from heapq import heappop, heappush def solution(k, score): answer = [] heap = [] for s in score: heappush(heap, s) if len(heap) > k: #힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환 heappop(heap) answer.appe.. 2023. 3. 14.
백준 3040 - 백설공주와 일곱 난쟁이 파이썬 문제 해결코드 arr = [] for i in range(9): arr.append(int(input())) for i in range(9): for j in range(i+1,9): if sum(arr)-arr[i]-arr[j] == 100: x,y = i,j break arr.pop(x) arr.pop(y-1) for i in arr: print(i) - 아홉명의 수를 다 더하기 - 한명씩 반복문을 사용하여 뺴보고 - 100을 기준으로 차액이 배열에 있는지 확인해서 있으면 그 것까지 뺴는 것을 생각했다 - 그리고 합해서 100이 되는 7개의 나머지는 그대로 하나씩 리턴한다 조합을 통해서도 풀이가 가능하다 from itertools import combinations nums = [int(input().. 2023. 3. 13.
프로그래머스 두 큐 합 같게 만들기 파이썬 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 .. 2023. 3. 10.

티스토리툴바