AI Engineer

힙 알고리즘(heapq)힙은 트리형식으로 구성되나 보통은 최소값이 맨 위로 올라가는 최소 힙으로 구현되어 있어서 가장 작은 값을 효율적으로 관리 가능합니다. 그래서 최소값을 찾고 pop하기는 쉽습니다. 반면 최대값은 검색이 가능하지만 pop하기는 어려운 구조이기에 아래 문제를 풀 때는 리스트로 변경해서 remove하고 다시 heapify로 힙 구조로 변환하였습니다. # 프로그래머스 | 이중우선순위큐from heapq import heappush, heappop, heapifydef solution(operations): heap = [] for op in operations: if op[0] == "I": heappush(heap, int(op[2:])) ..

카테고리 없음 2024. 10. 16. 12:02

Breadth First Search (BFS)> Level 별로 탐색> 그래프가 딕셔너리 형태로 key는 node, value는 연결된 모든 node를 나열하는 경우, 아래와 같은 방식으로 해결할 수 있습니다. # 기본 방식문제를 풀어보면서 많이 느낀 부분은 기본 구조를 정확히 익히는게 중요하다고 생각이 들었습니다.말 그대로, 그래프를 깊이 우선이든, 너비 우선이든 다 탐색하는 것이기 때문에 visited라는 부분을 설정하고 점검하는 부분이 중요하고, queue를 사용함에 있어 initial 값을 넣고 popleft로 값을 뺐다가 추가로 다음 값을 넣는 부분을 생각해서 풀어야 한다는 것을 문제를 여러 개 풀면서 점점 익히는 것 같습니다. from collections import dequedef bfs..

카테고리 없음 2024. 10. 14. 16:28

완전탐색(Exhaustive Search)은 가능한 모든 경우의 수를 탐색하여 해답을 찾는 방법모든 가능성 탐색(브루트 포스)백트래킹: 재귀적으로 탐색하여 정답을 찾는 방법순열/조합/부분집합격자 탐색(DFS, BFS)python docs 공식 문서 itertools — Functions creating iterators for efficient loopingThis module implements a number of iterator building blocks inspired by constructs from APL, Haskell, and SML. Each has been recast in a form suitable for Python. The module standardizes a core set..

카테고리 없음 2024. 10. 10. 15:09

Queuedeque() 사용하여 문제 해결- BFS 구현- two pointer 사용 StackTop을 사용하여 문제 해결- 짝 맞추기- 되돌리기- DFS(재귀)  프로그래머스 | 프로세스from collections import dequedef solution(priorities, location): answer = 0 q = deque([[idx, val] for idx, val in enumerate(priorities)]) while q: p = q.popleft() if any(p[1]  프로그래머스 | 다리를 건너는 트럭from collections import dequedef solution(bridge_length, weight, truck_..

카테고리 없음 2024. 10. 8. 10:14

cmp_to_key 파라미터를 사용해서 커스텀 정렬 방식을 사용할 수 있습니다.리턴 값은 항상 1, 0, -1 이어야 합니다.return 1# 정렬 기준대로 앞으로 가기 위한 True의 의미# 먼저 들어온 요소가 뒤로 정렬됨(나중에 들어온 요소가 앞으로 정렬됨) return 0# 정렬 기준에 해당사항이 없어 그대로, 아무 변동 없음 return -1# 정렬 기준과 반대여서 뒤로가기 위한 False의 의미# 먼저 들어온 요소가 앞에 정렬됨 # 프로그래머스 | 가장 큰 수from functools import cmp_to_keydef compare(x,y): if str(x)+str(y)  # return 전에 map을 이용해서 str으로 join할 때 굳이 int로 바꿨다가 str으로 다시 바꾸는 이..

카테고리 없음 2024. 10. 6. 21:59

Python 해시테이블 사용법Hash table은 효율적인 탐색을 위한 자료구조로써 key-value 쌍을 데이터로 입력받습니다.> Dictionary는 hash table로 구현된 python의 유일한 매핑(mapping)형입니다. # 프로그래머스 | 베스트앨범def solution(genres, plays): answer = [] # 장르별 총 재생횟수 계산 most_plays = {} # 해시 형태로 장르별 재생횟수, 인덱스 넣기 genres_plays = {} for i in range(len(genres)): most_plays[genres[i]] = most_plays.get(genres[i],0) + plays[i] genres..

카테고리 없음 2024. 10. 6. 21:31

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 장점:- 효율성: 중복 감소- 명확한 구조: 문제 분할- 범용성: 최적화 문제에 적용 가능 단점:- 메모리 사용량: 중간 계산 결과 저장을 위한 메모리 사용- 초기 설계 복잡성: 부분 문제 해결 방법 설계에 대한 복잡성- 적용 제한성: 최적 부분 구조 + 중복되는 부분 문제의 특성일 때 사용 가능 # 아래 풀이는 상향식 접근법(Bottom-Up Approach)을 사용하여 가장 작은 하위 문제를 반복문으로 저장해가며 문제를 풀이했습니다. # 동적 계획법의 예- 피보나치 수열# 프로그래머스 정수 삼각형def solution(triangle): idx = len(triangle) - 1 while idx: ..

카테고리 없음 2024. 10. 5. 21:33

[백준] 11720 숫자의 합 구하기 | 링크sum = 0# 입력받을 숫자의 개수, 공백없이 주어진 N개의 숫자를 input으로 받음num_count = input()num = input()# input은 문자열로 취급하기 때문에 int로 형변환, 인덱싱해서 합계를 구함for i in range(int(num_count)): sum += int(num[i]) print(sum) [백준] 1546 평균 | 링크subject = input()scores = input()# 연속으로 된 숫자를 리스트에 담기list_scores = []list_scores = scores.split(' ')# 점수의 합 구하기avg_sub = 0sum_scores = 0for i in range(len(list_sc..

카테고리 없음 2024. 4. 27. 12:32