본문 바로가기

💻 Programming/알고리즘 테스트17

[python] 프로그래머스_자물쇠와 열쇠 (완전 탐색) 문제 풀이 열쇠를 적당히 회전/이동시켜서 자물쇠 홈에 딱 맞게 끼워야 한다. 열쇠와 자물쇠 사이즈가 크지 않으므로 완전탐색으로 풀 수 있다. 수월한 풀이를 위해 자물쇠 리스트의 크기를 3배 이상으로 변경(자물쇠를 중간에 두고 나머지는 zero padding)하고 열쇠를 슬라이딩/회전 시키면서 하나씩 확인하면 된다. 2차원 리스트를 90도 회전시키는 함수와 자물쇠 리스트의 중간 부분이 모두 1인지 확인하는 함수를 만든다. 메인인 solution 함수에서는 자물쇠의 크기를 3배로 변환하고 새로운 자물쇠 리스트 중간에 기존의 자물쇠를 넣는다. 그리고 4가지 방향과 열쇠가 이동하는 하는 것을 for문을 돈다. 열쇠는 각 위치에서 자물쇠에 넣고 열쇠가 자물쇠에 정확히 들어맞는지 확인하고 다시 자물쇠에서 열쇠를 빼.. 2022. 2. 14.

[python] 프로그래머스_카펫 (완전 탐색) 문제 풀이 카펫 그림을 보고 가로길이 = a, 세로길이 = b 로 두고 조건에 부합하는 식을 만들고 for 문 돌면서 if 문으로 조건에 맞는 경우를 찾으면 된다. def solution(brown, yellow): total = brown + yellow for b in range(1, total+1): if total/b % 1 == 0: a = total/b if a>=b: if ((a-2)*(b-2) == yellow) and (2*a + 2*b -4 == brown): return [int(a),int(b)] 2022. 2. 14.

[python] 프로그래머스_타겟넘버 (DFS&BFS) 문제 풀이 BFS 를 이용하여 풀 수 있다. 다음 수를 더하고 빼는 경우 두가지를 모두 큐에 넣으면서 BFS를 진행시키고 target 과 동일한 경우에 카운트해준다. 코드 from collections import deque def solution(numbers, target): answer = 0 queue = deque() n = len(numbers) queue.append([numbers[0],0]) queue.append([-1*numbers[0],0]) while queue: temp, idx = queue.popleft() idx += 1 if idx < n: queue.append([temp+numbers[idx], idx]) queue.append([temp-numbers[idx], id.. 2022. 2. 6.

[python] 프로그래머스_단어변환 (DFS&BFS) 문제 풀이 BFS 로 풀 수 있고, 현재 단어와 words 중에 단어 하나만 다른 경우에 해당 words 를 방문하고 카운트해준다. 그렇게 반복하다가 현재 단어가 target 단어와 같아 지는 순간 BFS 종료하고 카운트한 수를 리턴해준다. 코드 def bfs(begin, target, words, visited): count = 0 stack = [(begin, 0)] while stack: cur, depth = stack.pop() if cur == target: # target에 도달했으면 depth 리턴 return depth for i in range(len(words)): if visited[i] == True: # 이미 지나쳤던 words 이면 패스 continue cnt = 0 for a.. 2022. 2. 6.

[python] 프로그래머스_네트워크 (DFS&BFS) 문제 풀이 모든 컴퓨터를 돌면서 방문 안한 위치에 방문하여 DFS를 수행하여 풀 수 있다. 하나의 DFS가 종료되면 +1 해서 네트워크 수를 계산하고, DFS 함수는 해당 위치를 방문처리하고 모든 컴퓨터를 for문으로 확인하면서 자기 자신이 아니고 연결되어 있는 경우 그리고 방문을 안한 경우에 DFS로 방문처리한다. 코드 def solution(n, computers): answer = 0 visited = [False]*n # 컴퓨터 개수 만큼 for com in range(n): # 각 컴퓨터를 돌면서 방문 안했으면 DFS if visited[com] == False : DFS(n, computers, com, visited) answer +=1 # 연결된 하나의 네트워크 +1 return answe.. 2022. 2. 6.

[python] 백준18405_경쟁적 전염 (DFS&BFS) 문제 풀이 BFS를 이용하여 풀 수 있고, 각 바이러스가 낮은 번호부터 증식하기 때문에 초기에 큐에 원소를 삽입할 때 낮은 바이러스의 번호부터 삽입해야 한다. 큐에서 낮은 바이러스 번호부터 pop하여 상하좌우로 바이러스 번식시키고, 번식된 위치를 다시 큐에 넣고, 원하는 시간이 될 때까지 반복한다. 코드 from collections import deque n, k = map(int,input().split()) graph = [] # 전체 보드 정보를 담는 리스트 data = [] # 바이러스에 대한 정보를 담는 리스트 for i in range(n): # 보드 정보를 한 줄 단위로 입력 graph.append(list(map(int, input().split()))) for j in range(n):.. 2022. 2. 6.

이전 1 2 3 다음

티스토리툴바