반응형 알고리즘207 백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. 3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다. 1. 각 점을 정점이라고 생각한다. 현재 상황을 그래프로 나타낼 수 있다. 0부터 100,000번까지 총 100,001개의 정점이 있다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. X번 정점에서 1초 만에 다이렉트로 갈 수 있는 정점은 X+1, X-1, X*2이다. 그래프에 X에서 저 세 정점으로 가는 방향 간선을 추가해준다. 방향 간선이라는 것을 주의해야 한다.. 2022. 1. 15. 백준 7662번 이중 우선순위 큐 - C++(cpp) 풀이 문제 제목에서부터 알 수 있듯이 우선순위 큐를 써야 하는데, 스위프트에는 라이브러리로 우선순위 큐를 제공하지 않아서 C++로 풀었다. 1. 최댓값은 최댓값 큐에서 찾는다. 2. 최솟값은 최솟값 큐에서 찾는다. 3. 반대쪽 큐에서 제거된 값인지 구별하기 위해, map에 해당 숫자가 현재 몇 개 남아있는지 기록한다. 먼저 최대값과 최솟값을 모두 알아내야 하므로 우선순위 큐를 2개 운영해야 한다. 하나는 최댓값용, 하나는 최솟값용으로. 근데 이렇게 되면 삭제를 할 때 문제가 된다. 최솟값을 삭제하라는 쿼리가 들어오면, 최솟값 큐에서 pop을 할 것이다. 근데 이 최솟값이 최댓값 큐에는 남아있게 된다. 따라서 반대 큐에서 삭제 여부를 알 수 있도록, 어떤 수 x가 현재 몇 개 남아 있는지를 기록해두어야 한다. .. 2022. 1. 14. 백준 1966번 프린터 큐 - 스위프트(Swift) 풀이 배열로 환형 큐를 구현하면 된다. front를 현재 맨 앞에 있는 문서를 가리키는 포인터라고 하면, 1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기 : 그냥 front를 하나 뒤로 옮기면 저절로 된다! 2. 인쇄하기 : 해당 자리에 인쇄 표시를 하고 front를 뒤로 하나 옮긴다. (다음에 front가 이 자리에 오면 없는 셈 치고 스킵하면 됨) 3. 인쇄해야할 대상인지 판단 : 우선순위들을 정렬한 배열을 따로 둬서 남은 문서 중 우선순위 최댓값을 알 수 있도록 한다. 1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기 front를 하나 뒤로 옮기면, 그 다음 문서가 front가 되고, 현재 문서는 front의 바로 왼쪽으로 가게 된다. front를 계속 우측으로 한 칸씩 이동시킬 것이므로, front의 바로 왼쪽에 .. 2022. 1. 13. 백준 1436번 영화감독 숌 - 스위프트(Swift) 풀이 먼저 브루트포스로 가능한 지부터 고려해야 한다. 1, 2, 3... 이렇게 1부터 차례로 666이라는 수를 포함하는지 체크해서 N번째로 666을 포함하는 수를 만나면 출력하고 break 해주면 간단하게 구할 수 있을 것이다. 이 방법이 제한 시간 안에 통과되는지 계산해보자. 일단 N의 최대값이 10,000이다. N = 10,000일 때 답이 몇 일지 예상해야 한다. (예상 못하겠으면 그냥 N=10,000으로 두고 위에 반복문 돌려서 기다려보면 알 수 있긴 하다.) 대충 666이 맨 끝에 오는 경우만 생각해줘 봤는데, 10,000가지가 되려면 채우려면 666 앞에 4자리가 더 붙어야 한다. _ _ _ _ 666 이렇게 되면 각 자리마다 0-9가 들어갈 수 있으니까 10,000가지가 될 것이다. 따라서 N .. 2022. 1. 13. 백준 3770번 대한민국 - C++(cpp) 풀이 + 그림 설명 1615번 문제와 똑같고, 대신 테스트 케이스가 여러 개 주어지는 문제이다. 1615번은 Swift로는 시간 초과가 나서 못 풀었어서 이 문제도 그냥 C++로 도전. 서쪽을 기준으로 작은 수부터 차례로 동쪽과 연결해준다. 1, 2가 연결 완료된 상태이고, 이제 서쪽의 3번에 2개의 고속도로(3-2와 3-5)를 설치해야 하는 상황이라고 하자. 3-2로 가는 고속도로 먼저 설치해야 하는데(이유는 나중에), 이 고속도로를 설치할 때 생기는 교차점의 개수는 동쪽에서 2 초과인 곳 [3, 4, 5]에 연결된 고속도로 개수의 합과 같다. 이미 존재하는(검은색) 고속도로들은 전부 서쪽에서는 3(빨간 선의 시작점)보다 위에 있다. 따라서 방금 설치한 빨간색 고속도로와 교차하려면 동쪽에서는 2(빨간 선의 도착점)보다 아.. 2022. 1. 12. 이전 1 ··· 35 36 37 38 39 40 41 42 다음 반응형
