너비 우선 탐색(Breath-First Search) 그래프에서 탐색을 한다는 것은 특정 노드(Node)를 찾아가는 기법입니다.
https://www.acmicpc.net/problem/1697이 문제를 풀기 위해서 BFS와 deque를 이용을 해야만 합니다. 노드를 탐색하면서 동생이 있는 위치에 도달하면 위치를 반환하기만 하면 되는 BFS의 간단한 문제였습니다.
https://www.acmicpc.net/problem/1932
https://www.acmicpc.net/problem/11055
https://programmers.co.kr/learn/courses/30/lessons/42577
🧑🏻💻 문제링크파이썬의 heapq 모듈은 기본적으로 Min Heap 구조를 갖는다. 그렇기 때문에 heappop()을 하게되면 가장 heap에서 최솟값을 빼게 된다.처음에 생각했던 방법은 max_heap, min_heap 두 개의 heap을 만들어서 각각 최댓값
🧑🏻💻 [문제링크]다음 문제는 파이썬의 dictionary(딕셔너리)를 사용하면 참 쉬게 풀 수 있는 것 같다. 아래 실패율에 대한 공식을 생각해서 풀면 된다.실패율 = 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수딕셔너리 Key값에는 스
🧑🏻💻 [문제링크] (https://programmers.co.kr/learn/courses/30/lessons/43162) 문제풀이 대표적인 알고리즘인 BFS와 DFS를 활용한 문제이다. 두 개념을 알고 구현만 할 수 있다면 쉽게 풀 수 있지만 아직 BFS
🧑🏻💻 [문제링크]words가 "hot", "dot", "dog", "lot", "log", "cog" 라고 주어졌을 때 begin인 "hit"가 target인 "cog" 까지 최소 몇 단계에 거쳐 변환할 수 있는지 찾는 문제이다."hit"이 "cog"까지 변환
GCD와 LCM Greatest Common Divider와 Least Common Multiple 은 코딩테스트에서 가장 많이 나오는 유형으로 최대공약수/최소공배수를 묻는 문제의 90% 이상은 이 알고리즘을 사용한다고 한다. 아마 중학교때 배웠던 건가? 초등학교때
🧑🏻💻 문제링크 동적계획법을 사용해서 푸는 문제이다. 처음에 문제를 제대로 안읽어서 엉뚱한 짓만 하다가 문제를 다시 읽어보니깐 숫자가 1인 경우에만 정사각형을 계산하는 것이었다. 앞으로는 시간이 없다고 해서 문제를 제대로 읽고 생각해서 푸는 연습을 해야겠다.동적
🧑🏻💻 문제링크 순열과 수학 개념을 사용한 완전 탐색 문제로 어떤 수의 문자열이 주어졌으면 모든 경우를 구한 다음에 그 값이 소수인지 아닌지 확인하는 문제이다. 파이썬에서 조합을 찾는 라이브러리는 다음과 같다.from itertools import permuta
🧑🏻💻 문제링크 출발지와 도착지가 주어졌을 때 방문하는 공항경로를 구하는 문제이다. 기존의 DFS 알고리즘을 for문으로 돌려서 풀었는데 while문으로도 저렇게 구할 수 있다는 것을 알 수 있었다. 그리고 문제를 defaultdict을 이용해서 풀면 더 간단
🧑🏻💻 문제링크 스택 문제 중에서 가장 대표적인 올바른 괄호나 팰린드롬과 같이 스택을 이용하여 균형이 맞는지 확인할 수 있는 방법만 알면 푸는데 크게 어렵지 않은 문제인 것 같다. 문제에서 이렇게변환 과정을 알려주기 때문에 저 지문에 따라서 코드를 작성하기만 하
🧑🏻💻 문제링크 주어진 방향대로 좌표에서 움직인 길이를 구하는 구현문제이다. 이 문제는 약간 백준 문제의 로봇 청소기 문제와 비슷한 것 같다. 중복된 선을 구분하기 위해서는 set() 함수를 사용하였다. 가끔씩 set() 함수가 기억이 안나면set 함수 정리 사
🧑🏻💻 문제링크 탐욕 알고리즘을 사용하여 푸는 문제이다. 문제를 보면 패턴 같은 것이 주어지는 데 만약, 7인 숫자를 2진수로 나타내면 0111로 표현할 수 있다. 여기서 7보다 크고 비트가 1~2 개로 다른 수들 중에서 제일 작은 수는 맨 앞에 0과 1을 1과
최단 경로 알고리즘은 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘입니다. 가중치 그래프(weighted)에서 간선(edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적으로 코딩테스트에서 많이 나오지는 않지만 간혹 나오기 때문에 알아 두는 것이 좋다고
최소 신장 트리 (Minimum Spanning Tree)이란? 신장 트리 (Spanning Tree)로 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프입니다. 즉, 신장 트리의 조건은 다음과 같습니다. 본래의 그래프의 모든 노드를 포함