본문 바로가기

전체 글110

프로그래머스 - 호텔 대실 (파이썬) 1. heapq 사용 heapq를 사용하면 우선순위큐처럼 값을 저장 시 오름차순으로 정렬되는 장점이 있다. 먼저 book_time 배열의 시간,분 값을 분단위로 합친후 대실시작시간을 기준으로 정렬한다. heapq를 사용하여 queue를 만든다. 방 개수만큼 큐 인덱스가 늘어나고, 해당 방의 대실 종료시간이 값으로 들어간다. queue에 값이 없거나 queue의 첫번째 값이 대실시작시간보다 크면 queue에 book_time의 대실 종료시간+10을 queue에 넣는다. 그렇지 않다면 queue에서 첫번째 인덱스를 빼고 해당 book_time의 대실 종료시간+10을 queue에 넣는다.( 해당 방을 book_time[i]가 빌릴 수 있으므로 방을 하나 늘리지 않고 해당 방의 대실종료시간을 업뎃하는 의미로 생.. 2024. 4. 14.
프로그래머스 - 롤케이크자르기 (파이썬) 1. set 이용(x) topping배열을 두조각으로 나누기 위해 set1, set2를 만들었다. topping을 앞에서부터 돌면서 topping[i]번째 값 전까지 set1에 넣고 topping[i]번째부터 배열 끝까지의 값을 set2에 넣어 set1과 set2의 값을 비교했다. 반복문을 돌때마다 set을 만들어야 해서 시간초과가 발생했다. def solution(topping): answer = 0 for i in range(1,len(topping)): set1=set(topping[:i]) set2=set(topping[i:]) if len(set1)==len(set2): answer+=1 return answer 2. 딕셔너리 이용 dic1, dic2를 만들어 topping의 모든 토핑 값을 k.. 2024. 4. 14.
프로그래머스 - 뒤에있는큰수찾기(파이썬) 스택을 사용하여 풀었다.(stack=[]) 배열을 뒤에서부터 돌면서 stack 안에 배열의 i번째 값보다 큰값이 있을 때까지 pop을 해주었고 그 후에 i번째 값을 스택에 추가시켰다. -> 따라서 스택에는 i번째 값부터 오름차순으로 정렬되어있다. def solution(numbers): answer = [] stack=[] for i in range(len(numbers)-1,-1,-1): while stack and stack[-1]numbers[i]: answer.append(stack[-1]) else: answer.append(-1) stack.append(numbers[i]) answer.reverse() return answer 2024. 4. 14.
벨만포드 알고리즘 (파이썬 구현) 벨만포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과의 차이점 출발노드가 1번, 도착노드가 3번노드라고 하자. 다익스트라 알고리즘은 그리디 알고리즘 기반이므로 1번 노드에서 가중치가 10, 20 중 더 짧은 10을 선택해 3번으로 갈 것이고 3번 노드는 도착 노드이므로 최단거리 10을 반환할 것이다. 하지만 벨만 포드 알고리즘은 출발노드에서 갈수 있는 모든 경로를 확인하기 때문에 1->2->3 의 경로를 확인해 최단거리 5를 반환한다. 즉 벨만포드 알고리즘은 가중치에 음수가 포함되어 있는 경우 사용한다. 동작순서 1. 출발 노드를 설정한다. 2. 최단거리 테이블을 무한대 값으로 초기화한다. 3. 최단거리 테이블에서 출발노드의 값을 0으로 초기화 한다... 2024. 4. 14.
다익스트라 알고리즘 (파이썬 구현) 1. 다익스트라 알고리즘이란? 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다. 출발노드에서 갈 수 있는 모든 노드들의 최단 경로를 구할 수 있다. 다익스트라 알고리즘은 그리디 기반으로 작동하므로 가중치가 음수일 경우 최단거리를 구할 수 없다. 2. 동작 순서 1) 출발 노드를 설정한다. 2) 출발 노드에서 각 노드로 갈 수 있는 최단 거리를 저장하는 테이블을 만든다. 3) 출발노드부터 시작하여 각 노드로 갈 수 있는 거리가 현재 최단거리 테이블에 저장되어 있는 값보다 작으면 최단거리 테이블을 업데이트 하고 현재 노드에서 갈 수 있는 노드들을 확인한다. 4) 3번 과정을 반복하여 갈 수 있는 모든 노드들을 확인한다. 3. 다익스트라 함수 로직 구현 1) 파라미터로 받은 출.. 2024. 4. 14.
완전탐색 알고리즘 완전탐색이란? 가능한 모든 경우의 수를 구한 후 문제에 나와있는 조건과 일치하는 값을 찾는 방법이다. 모든 가능성을 고려하기 때문에 항상 최적의 해를 찾을 수 있다. 완전탐색 알고리즘은 반복문이 여러번 중첩되어 사용되는 경우가 많으므로 입력값의 범위, 또는 비교해야할 범위가 작은 경우에 유용하다. 완전탐색 알고리즘 종류 2024. 4. 11.

티스토리툴바