분류 전체보기91 백준(BOJ) 1167 트리의 지름(Python) DFS를 두 번 사용하면 되는 문제. 트리의 지름을 구하는 방법은 간단하다. 임의의 한 노드에서 DFS 혹은 BFS를 실행해 가장 거리가 먼 노드를 택하고, 그 노드에서 다시 한 번 DFS를 실행하면 가장 거리가 먼 노드의 거리가 트리의 지름이 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq input=sys.stdin.readline sys.setrecursionlimit(100000000) def dfs(x,p): visited[x]=1 for i in D[x]: a,b=i if not visited[a]: length[a]=p+b dfs(a,p+b) v=int(input()) .. 2022. 7. 8. 백준(BOJ) 2448 별 찍기 - 11(Python) 단순한 재귀 문제. 지겹도록 보는 프랙탈 구조를 재귀로 표현하면 된다. 처음에는 줄마다 출력할려고 했으나, 그러면 이런저런 조건이 많이 붙어야 할 것 같아 귀찮아서 패스했다. 그렇게 생각한게 그냥 2차원 리스트 안에 텍스트를 다 집어넣고 한 번에 출력하는 방식이다. 일종의 분할 정복이라고 볼 수 있을 것 같다. 3*2^n 형태로 입력을 받는데, 세로 길이는 3*2^n이고 가로 길이는 공백 포함 6*2^n-1이다. 최소 단위의 삼각형을 기준으로 프랙탈이 총 n번 이루어지기 때문에, n회 재귀를 실행했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq #input=sys.stdin.readl.. 2022. 7. 8. 백준(BOJ) 7662 이중 우선순위 큐(Python) solved.ac의 Class 3에 있던 문제. 예전에 한 번 풀어보려 했다가 알고리즘 구상이 귀찮아서 미뤘는데, 이번에 하게 됐다. 최소 힙과 최대 힙을 동시에 사용해서 풀었다. 최소 힙과 최대 힙은 그 값의 부호 차이로 결정되는데, 값을 힙에 집어넣을 때 고유 넘버를 설정해주고, 값을 뺄 때 그 넘버에 해당하는 매핑 리스트 내의 값을 수정해준다. 최소 힙과 최대 힙에서 같은 값을 동시에 뺄 수 없기 때문에, 나중에 값이 등장하더라도 그 값이 이미 처리됐음을 기록할 수 있게 된다. 그 후에는 최소 힙과 최대 힙에 고유 넘버에 해당하는 매핑 리스트 값이 1인 값이 남아있다면 최솟값과 최댓값을 출력하게 되고, 없었다면 EMPTY를 출력한다. 코드는 다음과 같다. # -*- coding: utf-8 .. 2022. 7. 8. 백준(BOJ) 3866 풍선 수집(Python) 2차원 DP 문제. 가로 길이는 전체 풍선의 개수, 세로 길이는 현재 로봇에 달려 있는 풍선의 개수로 2차원 DP 리스트를 설정했다. 당연히 풍선은 빨리 떨어지는 순으로 받아줘야 하고, 첫 풍선은 선택지 없이 집에서 출발해 받아줘야 한다. 그 다음부터 떨어지는 풍선에 대해서는 2가지의 선택지가 존재한다. 풍선을 집에 두고 받을 것인지, 그냥 받으러 갈 것인지. 이를 DP에 적용해주면 된다. i가 전체 풍선의 개수만큼의 반복문의 인자, j가 로봇에 달릴 수 있는 풍선의 개수만큼의 반복문의 인자라고 하면 첫 번째 경우 풍선의 개수가 1개로 변하는 과정이므로 dp[1][i+1]=min(dp[1][i+1],dp[j][i]+p+x)라는 점화식을 세울 수 있다. 두 번째 경우 풍선의 개수가 (현재 풍선의 개수).. 2022. 7. 8. 백준(BOJ) 1132 합(Python) 뻔한 그리디 문제였다. 솔직히 그리디에 굉장히 자신이 없어서 그냥 다른 거 풀까 싶었는데, 취약점을 보완하기로 목표를 잡았기 때문에 그냥 도전했다. 해결 방법은 간단하다. ABC=100A+10B+C BCA=100B+10C+A ABC+BCA=101A+110B+11C 이런 식으로 입력값을 모두 정리한 다음, 계수가 낮은 순으로 수를 배정한다. 합이 최대가 되어야 하므로 가장 많이 등장하는 알파벳 순으로 큰 수를 배정한다면 자연스럽게 합이 가장 커지는 구조이다. 계수를 구한 다음 정렬할 때는 최소 힙을 사용했다. 사실 그냥 리스트에서 sort()하면 될 것 같은데 이런저런 자료구조를 끌어다 쓰면서 익숙해지려고 겉멋 좀 부렸다. 수를 배정할 때는 먼저 0이 될 수 있는 알파벳인가를 먼저 확인해 가능하다면 0을 .. 2022. 7. 8. 백준(BOJ) 1022 소용돌이 예쁘게 출력하기(Python) 생각해줘야 할 부분들이 많아서 조금 까다로웠지만 나름 재미있었다. 처음에는 일단 다 그려놓고 입력받은 사이즈에 맞춰서 출력하면 되지 않을까 싶었는데, 소용돌이의 최대 크기가 10000x10000이라 다 그리다간 시간 초과 아니면 메모리 초과 둘 중 하나는 무조건 뜰 거라고 생각했다. 따라서 연산 횟수를 줄이는게 불가피했는데, 어떻게 줄여볼까 하다가 (0,0)을 기준으로 오른쪽 아래 대각선이 모두 제곱수인 걸 이용하기로 했다. 사실 처음에는 직관으로 제곱수를 골라 해결한 감이 있지만, 곰곰히 생각해보니 소용돌이의 한 cycle이 제곱수로 끝나기 때문에 제곱수를 기준으로 문제를 해결하는 것이 맞다고 생각했다. 대각선이니까 x,y좌표는 똑같고, 좌표값을 n이라고 하면 그 칸에 오는 제곱수는 (2*n+1.. 2022. 7. 8. 이전 1 ··· 12 13 14 15 16 다음
