본문 바로가기

STUDY/Python

(56)
[알고리즘] 코딩테스트 단골 알고리즘(이진탐색/정렬/그래프탐색) 설명, 예제 코드 코딩 테스트에서 자주 다뤄지는 알고리즘 몇 가지와 간단한 설명 및 예시 코드를 제시하겠습니다 1. 이진 탐색 Binary Search 정렬된 배열에서 특정 값을 찾는 알고리즘 중간 값을 선택하여 찾고자 하는 값과 비교하고 탐색 범위를 반으로 줄여나감 시간 복잡도 : $O(logN)$ 예제 코드 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left
[자료구조] 리스트 list와 딕셔너리 dictionary의 차이점, 장점, 단점, 그리고 예시 코드 리스트는 순서가 중요하고 다양한 타입의 요소를 다룰 때 유용함 반면, 딕셔너리는 키-값 쌍의 관계와 검색이 필요한 데이터를 다룰 때 유용함 적절한 자료구조를 선택하여 데이터를 관리하는 것이 중요 [리스트 list] 리스트는 순서가 있는 요소의 컬렉션 각 요소는 인덱스를 통해 접근할 수 있음 1. 장점 순차적으로 저장되어 검색과 반복 작업이 용이함 다양한 타입의 요소를 포함할 수 있음 2. 단점 검색 속도가 느릴 수 있고, 원소가 많을 경우 성능에 영향을 줄 수 있음 3. 예제 코드 my_list = [1, 2, 3, 'apple', 'banana'] print(my_list[0]) # 1 my_list.append('orange') print(my_list) # [1, 2, 3, 'apple', 'ban..
[알고리즘] 그리디 알고리즘 교재 : "이것이 취업을 위한 코딩테스트다" 그리디 알고리즘¶ 현재 상황에서 가장 좋아 보이는 것만 선택하는 알고리즘 정확한 답 도출보단 그럴싸한 답을 도출하는데 도움됨 그리디 알고리즘의 정당성을 고민하면서 문제를 해결해야 함연계 알고리즘 : 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 거스름돈 p87¶ '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것화폐의 종류가 $K$개라고 할 때, 시간 복잡도 $O(K)$ 아래 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와 무관 In [ ]: x = int(input()) x 1260 Out[ ]: 1260 In [ ]: cash_list = [500, 100, 50, 10] count = 0 for cash in ca..
[Softeer] GBC python [첫번째 풀이 - 테케만 맞음..] import sys n, m = map(int, sys.stdin.readline().split()) limit_length = [] limit_speed = [] for _ in range(n): limit_num = sys.stdin.readline() limit_num = limit_num.replace('\n','') a, b = map(int, limit_num.split()) limit_length.append(a) limit_speed.append(b) test_length = [] test_speed = [] for _ in range(m): test_num = sys.stdin.readline() test_num = test_num.replace('\n..
[Softeer] 바이러스 python [첫번째 제출 - 시간초과] import sys # 1초당 p배씩 증가 k, p, n = map(int, sys.stdin.readline().split()) total_birus = (k*(p**n)) % 1000000007 print(total_birus) input이 최대 10^8 이어 단순연산만으로도 시간 초과를 일으킬 수 있다는데... 이해가 잘되진 않았다.. 아무튼 다른 방식으로 접근하려고 해보았다. [두번째 제출 - 시간초과] import sys k, p, n = map(int, sys.stdin.readline().split()) total_birus = k for _ in range(n): total_birus *= p print(total_birus % 1000000007) [통과 코드..
[백준] 18258번 큐2 python 이 문제는 큐 문제이다. 이 문제의 꿀팁 1. import sys를 사용하여 입력을 받는다. 2. from collections import deque를 사용하여 문제를 푼다. 위 꿀팁을 꼭 써야 시간 초과가 나지 않는다. [나의 풀이 1 - 시간 초과] import sys len_element = int(sys.stdin.readline()) box = [] for i in range(len_element): command = sys.stdin.readline() if command.find('push')!= -1: command = command.replace('push ', '') box.append(int(command)) elif command.find('pop')!= -1: if len(box..
[백준] 9012번 괄호 python [나의 풀이] len_element = int(input()) right_num = 0 left_num = 0 for i in range(len_element): box = input() for s in box: if s == '(': right_num += 1 else : left_num += 1 if right_num == left_num: while box.find('()') != -1: box = box.replace('()', '') if box == '': print('YES') else: print('NO') else: print('NO') right_num = 0 left_num = 0
[백준] 10828번 스택 python 이 문제는 스택을 이용하여 푸는 문제이다. [나의 풀이 - 첫 번째 시도] len_element= int(input()) stack = [] for i in range(len_element): element = input() if element.find('push') != -1: x, y =map(str, element.split()) stack.append(int(y)) elif element.find('pop') != -1: if len(stack)==0: print(-1) else: print(stack[-1]) stack.pop() elif element.find('top') != -1: if len(stack)==0: print(-1) else: print(stack[-1]) elif eleme..

728x90