백준 2302번으로 보는 Backtracking과 DP의 목적 차이

2302. 극장 좌석 백준 2302번 문제인 극장 좌석을 풀기 위해, 처음에는 백트래킹 알고리즘을 이용했다. 오름차순으로 한 명씩 자리에 앉히고 다음 사람을 앉히기 위해 왼쪽, 자기자리, 오른쪽을 탐색을 반복하여 마지막 사람까지 자리에 앉으면 이것을 하나의 case로 보고 정답 값에 1을 더해주는 재귀 함수를 짜면 된다고 생각했기 때문이다. 그러나 시간 초과가 발생했다. 좌석의 수 N이 최대 40인데, 각 자리에는 왼쪽 사람, 자리 주인, 오른쪽 사람 총 세 명이 앉을 수 있으므로 시간 복잡도가 O(3^N)이다. 3^40은 조가 넘어가는 어마어마한 값이므로 당연히 안 된다. 결론적으로 이 문제는 Sub-Problem이 숨어 있는 DP 문제였다. VIP석이 Sub-Problem을 쪼개는 기준이었다. 이번 ..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2022. 9. 14.
• textsms

[백준/Python] 2023. 신기한 소수

2023. 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 백트래킹 처음에는 에라토스테네스의 체를 사용하는 문제일 것이라고 생각했다. 가능한 수의 범위가 컸기 때문이다. (10**8) 하지만 사용 가능한 메모리가 4MB 뿐이라서, 가능한 범위만큼의 배열을 선언할 수는 없는 문제였다. 순차 탐색을 통해 소수를 판별하는 가장 빠른 방법 소수란, 1과 자기 자신 이외의 약수를 갖지 않는 수를 말한다. 약수의 개수를 구하는 것이 아니라, 단순 소수를 판별하는 경우에는 자기 제곱근(내림) 까지만..

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

[백준/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

[백준/Python] 15681. 트리와 쿼리

15681. 트리와 쿼리 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리 DFS DP 힌트에서 제공하는 트리의 특성 "트리는 단 하나의 사이클도 존재하지 않는 그래프" 따라서 루트가 정해지면, 특정 노드에 도달하는 최단 경로는 한 가지 뿐이다. "한 노드와만 연결되어 있는 모든 노드가 루트가 될 수 있다" 또한 루트가 정해지면 노드 간에 부모 자식 관계를 정의할 수 있다. "아무 정점이든 root로 잡아 subtree를 구성할 수 있다" 따라서..

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

[백준/Python] 4256. 트리

4256. 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리 분할 정복 트리는 분할 가능한(큰 것을 작은 것으로 쪼갤 수 있는) 자료구조에 해당 따라서 트리의 탐색은 재귀+분할정복으로 이루어질 수 있다. 전체 트리의 루트는 3이지만, 루트 3을 기준으로 왼쪽/오른쪽으로 트리를 나누면 루트가 6, 7인 두 개의 subtree가 생긴다. 트리의 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)가 갖는 의미 전위 순회는 root, left child, ri..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 4. 24.
• 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