본문 바로가기
728x90

TIL - 프로그래밍/Python 알고리즘198

이코테 Q.28 고정점 찾기 풀이 시간복잡도 O(logN)으로 설계 오름차순으로 정렬된 수열에서 특정 수의 개수 구하기 이진 탐색 시작위치, 마지막 위치 찾기 코드 import sys input = sys.stdin.readline # 원소의 개수 N = int(input()) # 원소 arr = list(map(int,input().split())) s = 0 e = N-1 flag = False while s 오른쪽 확인 if arr[mid] 왼쪽 확인 elif arr[mid] > mid: e = mid - 1 # 고정점이 있는가? if flag: print(mid) else: print(-1) 2023. 3. 9.
[프로그래머스] 가사 검색 - Python https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이1 문자열 검색에 최적화된 알고리즘 Trie ['frodo','front']를 Trie 형태로 바꾸기 {5: {'f': [2, {'r': [2, {'o': [2, {'d': [1, {'o': [1, {}]}], 'n': [1, {'t': [1, {}]}]}]}]}]}} 코드1 # Trie 사용 def make_trie(words,reverse): trie = {} # 얕은 복사 이용 for w.. 2023. 3. 8.
[프로그래머스] [3차] 압축 - Python https://school.programmers.co.kr/learn/courses/30/lessons/17684 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 사전에 다음 글자가 추가된 글자가 없으면 추가하고 색인번호 출력 입력한 단어는 지우고 남은 단어로 반복 있다면 추가하여 확인해보기 코드 def solution(msg): # 사전 alpha = {chr(i+65):i+1 for i in range(26)} answer = [] while True: # 해당 글자가 사전에 있다면 끝 if msg in alpha: answer.append(alp.. 2023. 3. 8.
이코테 Q.27 정렬된 배열에서 특정 수의 개수 구하기 풀이1 시간복잡도 O(logN)으로 설계 오름차순으로 정렬된 수열에서 특정 수의 개수 구하기 이진 탐색 코드1 import sys input = sys.stdin.readline # 원소의 개수, 찾는 수 n, x = map(int,input().split()) # 원소 arr = list(map(int,input().split())) # x의 시작 인덱스 구하기 # arr : 원소, x : 찾는 값, n : 원소의 총 개수 def find_start(arr,x,n): l = 0 r = n-1 while l 왼쪽부분을 확인해보자 if arr[mid] >= x: r = mid - 1 # 중간값이 x보다 작은 경우 -> 오른쪽부분을 확인해보자 elif arr[mid] < x: l = mid + 1 retur.. 2023. 3. 8.
이것이 취업을 위한 코딩 테스트다 CHAPTER 07 이진 탐색 순차 탐색 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 방법 데이터 개수가 N개일 때 최대 N번의 비교 연산이 필요 최악의 경우 시간 복잡도 O(N) count() 메서드를 이용할 때 내부에서 순차 탐색이 수행 이진 탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 배열 내부의 데이터가 정렬되어 있어야 함 시간 복잡도 O(logN) 탐색 범위가 큰 상황에서 탐색을 가정하는 문제 N이 1000만 단위 이상 or 탐색 범위가 1000억 이상 # 반복문 def binary_search(array,target,s,e): while s target: # 절반 중 왼쪽 부분 확인 e = mid - 1 # 중간점의 값이 찾고자 하는 값보다 작은.. 2023. 3. 7.
[프로그래머스] 보석 쇼핑 - Python https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 한 개씩 추가하면서 그 구간에 보석 종류가 다 있는지 체크 다 있다면 answer 리스트에 추가 이 구간에서 맨 앞 보석을 빼도 보석 종류가 다 있는지 체크 반복 Counter value에 +1을 하고 싶을 때 key가 없다면 key 생성(value가 0인) dict는 key가 없는 경우 +1이 안됨 코드 from collections import Counter def solution(gem.. 2023. 3. 7.
반응형

티스토리툴바