[백준/Python] 14226. 이모티콘

14226. 이모티콘 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net BFS 처음 접근은 DP로 했었다. S만큼의 2차원 배열을 선언할 수 있고, 1,2,3번을 수행하기 이전의 값+1을 이후 경우에 점진적으로 대입해주면 된다고 생각했기 때문이다. 하지만 이 문제는 단순히 DP로 풀기 어렵다. DP로 풀기 어려운 이유 탐색할 수가 점진적으로 증가하는 것이 아니라, 무작위로 증가 또는 감소하게 된다. DP는 값의 갱신이 단방향으로 일어나기 때문에, 증가/감소가 함께 일어나는 탐색에서 사용할 수 없다. 따라서 이 문제..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 5. 31.
• textsms

[Algorithm] 가중치와 최단거리, BFS와 Dijkstra

특정 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘에서 사용될 수 있습니다. 그러나 가중치의 유무에 따라서는, 반드시 Dijkstra를 사용해야 하는 경우도 있습니다. 가중치란? 비용(cost), 무게(weight) 등 여러 가지 단어로 나타나는, 중요도(우선 순위)를 말합니다. 가중치가 있는 경우에 대한 예시로 경매장을 들 수 있습니다. 경매장에서의 가중치는 가격입니다. 더 늦게 손을 든 사람일지라도 더 높은 가격(중요도가 큰 것)을 제시한 사람이 우선적으로 소유권을 갖습니다. 그러나 반대로, 이미 정해진 같은 가격으로 물건을 파는 타임 세일의 경우 먼저 물건을 집은 사람이 반드시 먼저 사게 됩니다. 이러한 경우에는 가중치가 없다고 말할 수 있습니다. 가중치가 있는 경우 따라서 가중치가 있는..

• format_list_bulleted 학습/Algorithm
• · 2021. 5. 7.
• textsms

[백준/Python] 1068. 트리

1068. 트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색 트리 프로그래머스 코드 챌린지를 하다가 느낀 거지만 트리 유형에 약한 것 같아서 트리 문제들만 골라 풀어보기로 했다 😢 트리는 모든 노드가 한 개 이하의 출발점, 한 개 이하의 도착점만 갖는 단방향 그래프이다. 따라서 노드의 방문 여부(visited)를 체크하지 않아도 된다는 특이점이 있다. 아이디어 Python에서는 포인터를 이용한 linked list 구조로 tree를 구현하지 않기 때문에, 실제로 node(와의 연결)을 제..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 4. 22.
• textsms

[Algorithm] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

사전 지식 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue) 재귀함수 자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다. 그래프 그래프에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph) DFS (깊이 우선 탐색, Depth-First Searc..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms