study/알고리즘 (44) 썸네일형 리스트형 [알고리즘/백준] 11724번 연결 요소의 개수 11724번 연결 요소의 개수 - https://www.acmicpc.net/problem/11724 Python으로 제출하면 시간 초과 / PyPy3로 제출하면 통과 (메모리 197904KB / 시간 868ms) 접근 방법 - BFS로 품 ( queue 사용) - 2644번 촌수계산 문제와 마찬가지로 중첩 리스트로 graph를 만들어주고 visited list를 활용하여 queue에 넣어준다. - sum(visited list) 가 N이 되면 모두 방문했다는 뜻으로 멈춰준다. from collections import deque def bfs(graph, N): visited = [0] * N count = 0 while sum(visited) != N: queue = deque([visited.ind.. [알고리즘/백준] 2644번 촌수계산 2644번 촌수계산 - https://www.acmicpc.net/problem/2644 ( 개인적으로 BFS로 푸는 코드를 생각하기까지 어려웠음 😥 ) 접근 방법 처음에는 BFS_DFS 문제라고 생각하지 못했다. 그래프 문제인 것은 알았는데 조금 복잡하게 구현했다. - 그래프를 dictionary로 만들었다. - num1의 부모 노드를 num1_list에 모두 담아주고 루트노드일 때 멈춘다. - num2도 num1과 마찬가지로 진행하되 num1_list에 들어있는 노드가 나오게 되면 index로 촌수를 계산해준다. def relatives(graph, num1, num2): result = -1 num1_list = [num1] num2_list = [num2] while num1 in graph.ke.. [알고리즘] 다이나믹 프로그래밍(LIS) - 병사 배치하기 출처 : 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 병사 배치하기 ( 직접 못 풀어서 답안 예시를 공부 ) N명의 병사가 무작위로 나열, 각 병사는 특정한 값의 전투력을 보유 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치 다시 말해서, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶다. 첫째 줄에 N이 주어진다. (1 [알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2 공부 : 동빈나 유튜브 + 책 실전문제 - 효율적인 화폐 구성 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 만들기 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분 첫째줄에 N, M ( 1 [알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1 공부 : 동빈나 유튜브 + 책 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 구현은 일반적으로 Top-Down(하향식)/Bottom-Up(상향식)으로 구성된다. - Top-Down은 재귀로 / Bottom-Up은 반복문으로 구현 가능 - 다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식 결과 저장용 리스트는 DP 테이블이라고 부른다. - 다이나믹은 자료구조의 동적과 다르게 별다른 의미 없이 사용된 단어 더보기 자료구조에서 동적 할당(Dynamic A.. [알고리즘/프로그래머스] 그리디 - 조이스틱 탐욕법(Greedy) > 조이스틱 (개인적으로 어려웠음) 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수 만들기 실패한 코드 아래의 코드는 테스트케이스 11번이 틀림 --> "ABAAAAAAAAABB" 일 때 7이 출력되야 하는데 15가 출력됨 한 방향으로 가는 것만이 아니라 2번째 B까지 갔다가 다시 돌아가는 것이 빠르기 때문에 출력값이 다름 def s.. [알고리즘/프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 실패율 2019 KAKAO BLIND RECRUITMENT > level1 실패율 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수/스테이지에 도달한 플레이어 수 N : 전체 스테이지 개수 stages : 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담겨있는 배열을 리턴 import heapq def solution(N, stages): fail = {} heapq.heap.. [알고리즘 / 자료구조] 트리(Tree) 공부 : 동빈나 유튜브 트리 : 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리 관련 용어 - 루트 노드(root node) : 부모가 없는 최상위 노드 - 단말 노드(leaf node) : 자식이 없는 노드 - 크기(size) : 트리에 포함된 모든 노드의 개수 - 깊이(depth) : 루트 노드부터의 거리 - 높이(height) : 깊이 중 최댓값 - 차수(degree) : 각 노드의 자식 방향 간선 개수 -- 자식의 개수 - 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이진 탐색 트리 (Binary Search Tree) : 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료.. 이전 1 2 3 4 5 6 다음
