annyhpk.log

알고리즘

BFS - 너비 우선 탐색

BFS는 너비 우선 탐색으로 Start Node와 가까운 노드 부터 탐색하는 알고리즘입니다. DFS와 반대인 탐색알고리즘이다. 아래 Graph를 통해 BFS에 대해 알아보자. Graph Code로 보는 Graph graph = [ [], # root_node [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] BFS 탐색하기 간단한 BFS 알고리즘 from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v = queue.pop() print(v, end=' ') for no..

알고리즘

DFS - 깊이우선탐색

DFS는 깊이 우선 탐색으로 최대한 깊숙히 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 아래의 Graph를 통해 DFS에 대해 알아보자. Graph Code로 보는 Graph graph = [ [], # root_node [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] DFS 탐색하기 간단한 DFS 알고리즘 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for node in graph[v]: if not visited[node]: dfs(graph, node, visited) graph = [ [], # root_node [2,..

알고리즘

백준 5585 - 거스름돈

문제 : www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 ..

알고리즘

[2019 카카오 개발자 겨울 인턴십] 코딩테스트 문제 : 튜플

문제 : https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이 : def solution(s): new_s = s[2:-2].split('},{') numbers = [] for z in new_s: for y in z.split(','): numbers.append(int(y)) data = set(numbers) counter = {} for sd in ..

알고리즘

[2019 카카오 개발자 겨울 인턴십] 코딩테스트 문제 : 크레인 인형뽑기 게임

문제: https://programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이: def solution(board, moves): picked = [] bomb = [] for pick in moves: for i in range(0, len(board)): if board[i][pick - 1] == 0: continue else: picked.append(board[i][pick - 1]) board[i][pick - 1] = 0 if len(picked) > 1: if..