본문 바로가기

algorithm/coding test14

프로그래머스 - 롤케이크자르기 (파이썬) 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.
프로그래머스 - 섬연결하기 (파이썬) 프로그래머스 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. dfs(x) 가능한 모든 경우의 수를 구하기 위해 dfs를 사용했다. 깊이가 깊어지면 런타임에러가 발생하게 된다. answer=0 def dfs(land,now_x,now_y,pre_y,tot): global answer if len(land)==now_x: answer=max(answer,tot) elif pre_y != now_y: for i in range(4): dfs(land,now_x+1,i,now_y,tot+land[now_x][now_y]) def solution(land): global answer for i in range(4): dfs(land,0,i,-1,0) return answer 2. i행에서 i-1행을 값 선택 i행의 각 값에 선택할 수 있는 i-1행의 값들중 가장 큰값.. 2024. 2. 23.
프로그래머스 모음사전 파이썬 완전탐색 알고리즘에 관한 문제이다. 이 문제는 permutations함수를 사용할 사용할 수 없고 재귀 함수를 이용해야 하는 문제이다. dfs를 돌면서 현재 값의 순서를 1씩 증가시켜주고 word와 동일한 단어가 되면 해당 단어의 순서를 ans에 넣어주었다. ans=0 cnt=0 alphabet=['A','E','I','O','U'] def dfs(word,str): #arr에 알파벳 추가 global alphabet,ans,cnt if str==word: ans=cnt #현재 단어와 word값 일치시 정답에 현재단어순서(cnt)를 넣음 return for i in range(len(alphabet)): if len(str) 2024. 2. 23.
프로그래머스 게임 맵 최단거리 파이썬 1. dfs 사용 (x) bfs 사용하기 위해서는 현재 위치를 다시 방문하지 않아야 하는데 이 문제는 오른쪽, 아래로 이동할 뿐만 아니라 위, 왼쪽으로 이동도 가능하므로 현재 위치를 또 방문할 가능성이 생긴다. 따라서 bfs가 아닌 완전탐색 문제로 풀어야 한다. 그러나 완전탐색으로 풀면 깊이가 너무 깊어져 효율성 테스트에서 런타임 오류가 발생한다. import sys answer= sys.maxsize #int 최대값으로 초기화 # cnt = 이동한 칸 횟수 , point = 현재 위치 좌표 , check = 방문한 좌표인지 확인하기 위해 def dfs(maps,cnt,point,check): global answer if point[0]==len(maps)-1 and point[1]==len(maps[.. 2024. 2. 23.

티스토리툴바