algorithm19 프로그래머스 - 롤케이크자르기 (파이썬) 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. 프로그래머스 - 섬연결하기 (파이썬) 프로그래머스 Lv3 - 섬연결하기 문제설명 n개의 섬 사이에 다리를 건설하는 비용이 주어지고, 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구한다. 그래프에서 최소비용으로 모든 노드를 연결할 수 있는 최소신장트리를 찾는 문제이다. 문제풀이 1. 크루스칼 알고리즘 사용 # 부모 노드를 찾기 위한 함수 def find(parent,x): if parent[x]==x: return x else: return find(parent,parent[x]) # 부모 노드가 다를 경우 두 노드가 속한 집합을 합침 (두 집합에 간선을 연결한다고 생각하기) def union(parent,a,b): root_a=find(parent,a) root_b=find(parent,b) # 부모 노드는 무조건 작은 값을.. 2024. 3. 5. 이전 1 2 3 4 다음
