본문 바로가기
반응형

알고리즘19

[백준 1816] 암호키 (자바) package week_01; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_1816_암호_키 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // 테스트 케이스의 수 입력 long[] S = new long[n]; // 테스트 케이스의 암호를 저장할 배열 생성 // 암호들을 배열에 저장 fo.. 2024. 4. 7.
[프로그래머스] 야근 지수 (level3) (파이썬) 문제 접근 정렬 된 최대 값이 필요하므로 우선순위큐로 표현해야 된다고 생각하였다 가장 빠른 삽입 삭제 시간복잡도 N(데이터) logN을 가진 힙(heap)을 이용하여 문제를 접근 풀이 코드 # 19:10 ~ 19:30 # https://programmers.co.kr/learn/courses/30/lessons/12927?language=python3# import heapq def solution(n, works): answer = 0 h = [] # 우선순위 큐 최대힙으로 저장 for value in works: heapq.heappush(h, -value) while n > 0: # 힙에서 하나 꺼내어 다시 넣음 work = -heapq.heappop(h) if work != 0: heapq.hea.. 2021. 6. 28.
[프로그래머스] 더 맵게 (level2) (파이썬) 문제 접근 힙의 특징을 이용하여 문제를 푼다. 문제 해결 # 09:30 ~ 09:55 # https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 # 정렬 시간 복잡도 NlogN, 삽입 삭제 logN # heapq.heappush() 삽입 # heapq.heappop() 꺼냄 import heapq def solution(scoville, K): # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 return answer = -1 count = 0 flag = True h = [] for value in scoville: heapq.heappush(h, value) # pop 하면서 스코빌 지수와 체크 하며 섞을지 .. 2021. 6. 28.
[프로그래머스 ] 짝지어 제거하기 (level2) (파이썬) 문제 접근 스택에 쌓으면서 짝이 지어지면 바로바로 제거하는 방식을 선택하였다 풀이 코드 # https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 # 9:40 ~ 09:52 def solution(s): answer = -1 stack = [] for i in s: if len(stack) != 0: if stack[-1] == i: stack.pop() else: stack.append(i) else: stack.append(i) if len(stack) == 0: answer = 1 else: answer = 0 return answer 2021. 6. 21.
[프로그래머스] 예상 대진표(level 2) (파이썬) 문제 접근 수학 문제 a,b 중 b가 큰것이 보장된다면 둘이 만나는 경우는 b가 2의 지수이면서 b - 1이 a일 때 뿐이다. 코드 # 13:45 ~ 14:10 import math def solution(n,a,b): if a > b: a, b = b, a cnt = 1 while True: if b % 2 == 0 and b - a == 1: break a = math.ceil(a/2) b = math.ceil(b/2) cnt += 1 return cnt 노트 2021. 5. 19.
[프로그래머스] 위장(level 2) (파이썬) 접근 경우의 수를 잘 생각해야 하는 문제 최소한 1개의 옷을 입어야 하므로 모두 안입은 경우를 -1 해야 한다. 각각의 경우의 수에서 옷의 종류는 독립변수로 작용한다. # 위장 level2 # 3시 57분 ~ 4시 43분 # 경우의 수 문제 종류가 2인 경우 00, 10, 01, 11 2*2 -1(00) def solution(clothes): answer = 1 hmap = dict() for i in range(len(clothes)): if clothes[i][1] in hmap.keys(): hmap[clothes[i][1]] = hmap[clothes[i][1]] + 1 else: hmap[clothes[i][1]] = 1 value_list = hmap.values() for value in .. 2021. 5. 18.
[프로그래머스] 다음 큰 숫자(level 2) (파이썬) 접근 2진수로 변환 하는 함수를 알아야했다 (bin이나 format 방식을 이용한다) 숫자를 하나 씩 늘려가며 일치할 시에 반복문을 빠져나오면 된다. # 다음 큰 숫자 # https://programmers.co.kr/learn/courses/30/lessons/12911 # 3시 8분 - 3시 25분 (17분) def solution(n): b_origin = str(format(n, 'b')) b_count = b_origin.count('1') num = n while True: num += 1 v = str(format(num, 'b')) if v.count('1') == b_count: return num def solution2(n): cnt = format(n, 'b').count('1') .. 2021. 5. 18.
[항해99] 알고리즘 복습 2021. 3. 19.
[항해99] 알고리즘 문제 유형 정리 (03-19 최신화) 수학 사칙연산 10869 (브론즈5) 52.622% 곱셈 2588 (브론즈4) 51.513% 알람시계 2884 (브론즈3) 39.168% 더하기 사이클 1110 (브론즈1) 48.102% 평균은 넘겠지 4344 (브론즈1) 37.371% 셀프 넘버 4673 (브론즈1) 50.276% 달팽이는 올라가고 싶다 2869 (브론즈1) 26.831% ACM 호텔 10250 (브론즈3) 34.605% 소수 구하기 1929 (실버2) 27.372% 암호 만들기 1759 (골드5) 44.837% 설탕 배달 2839 (브론즈1) 32.830% Fly me to the Alpha Centauri 1011 (실버1) 29.486% 베르트랑 공준 4948 (실버2) 29.486% 약수 1037 (실버5) 49.806% 최대공.. 2021. 3. 18.
[백준] [다익스트라 알고리즘] 최단경로 1753 (파이썬) 문제접근 주어진 V E의 범위가 큰 편이기 때문에 시간 복잡도를 고려했을 때 다익스트라 알고리즘을 적용해서 풀어야 한다고 파악했다. 또한 특정지점 (주어진 시작점)에서 다른 지점으로 까지 가는 최단 경로를 구하기 때문에 모든 정점에 대해 최단 경로를 알 수 있는 플루이드 워셜 알고리즘 시간복잡도와 문제를 보았을 때 적합하지 않았다. 최단 경로 알고리즘에 대해 정리한 글을 참조하면 도움이 될 것 같다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘.. 2021. 3. 17.
[알고리즘] 정렬 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬) 정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 이진 탐색을 하기위한 전처리과정 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 다뤄보자 선택 정렬 O(N^2) 가장 작은것을 선택하여 맨 앞과 바꾼다 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택정렬 소스코드에 익숙해지자 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스, i번째 인덱스와 바꿀 가장 작은 인덱스를 찾는다. for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index =j array[i], array[min_inde.. 2021. 3. 17.
[알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대표적인 문제는 N-Queen이 있다. 2021. 3. 17.
[알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘 O(ElogV), O(V^2) 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 0 보다 작은 간선이 없을 때 이용된다 매 상황마다 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘에 속한다. 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3번과 4번을 반복한다. 특징 각 노드에 대한 현재까지의 최단 거리 정보를.. 2021. 3. 17.
[알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutation) 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것 $nPr = n! / (n-r)!$ 코딩테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)를 다 출력하도록 요구 파이썬 itertools 라이브러리를 이용한다. import itertools data = [1, 2, 3] for x in itertools.permutations(data,2): print(list(x), end= '') # [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 조합 .. 2021. 3. 15.
[알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 유클리드 호제로 최대 공약수 구하기 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다 최소공배수 = 두 수의 곱 / 최대공약수 def gcd(a,b): if a % b == 0: return b else: return gcd(b, a % b) 2021. 3. 14.
반응형

티스토리툴바