Python43 [백준] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 +1, -1, 순간이동(X2)를 통해 도달할 수 있는 모든 경우를 체크해주었습니다. 우선순위 큐를 활용하여 cnt가 낮은 상태가 먼저 나오도록 하여 현재 숫자에 도달할 수 있는 가장 적은 횟수가 visited에 저장되도록 하였습니다. 그 다음으로는 순서를 정하는 방법입니다. K를 시작으로 +1을 통해 도달한 경우, -1을 통해 도달한 경우, 순간이동.. 2023. 2. 6. [백준] 군사 이동 https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 경로에 존재하는 가장 넓은 너비를 구하는 것이 목적인 문제입니다. 지나갈 수 있는 최소 너비를 지정해주고 이보다 큰 간선만을 택하면서 다익스트라를 수행한 다음 목적지에 도달할 수 있는지를 체크하면 풀 수 있습니다. # 문제링크: https://www.acmicpc.net/problem/11085 import sys, os, heapq from c.. 2023. 2. 5. [백준] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 두 정점 사이의 경로가 가장 긴 값(트리의 지름)을 구하는 것이 이번 문제의 목표입니다. 트리의 특성상 부모 노드를 하나만 가질 수 있기 때문에 하나의 부모노드에서부터 자식 노드를 연결하여 만들 수 있는 최대 경로의 길이를 정할 수 있습니다. dfs로 탐색해주면서 현재 노드에서 도달할 수 있는 최대 길이를 리턴해주고 현재 노드에서 만날 수 있는 상위 2개의 최대 길이를 더해주면 트.. 2023. 2. 4. [백준] 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 삼성 기출 문제의 경우 설계를 잘해야하는데 심신미약 상태에서 푸느라 설계부터 꼬여서 고생을 많이한 문제입니다. 포인트가 되는 부분은 상어의 다음 위치를 가져오는 next_pos 함수입니다. 핵심 포인트는 행이 1, R, 열이 1, C를 벗어나게 됐을 때 얼마나 벗어났는지 계산하여 반영해주어야하는게 포인트입니다. 왼쪽으로 향하다가 벗어나서 오른쪽으로 방향 전환하여 진행해도 격자를.. 2023. 2. 3. [백준] 물대기 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제의 특징을 생각해봤을 때 논에 물을 끌어오려면 연결 그래프여야하고 각각의 연결 비용을 합쳤을 때 최소비용이 되어야하므로 자연스럽게 최소 신장 트리로 풀어야한다고 생각했습니다. 문제는 직접 논에 우물을 파는 것을 처리해야하는데 이 부분은 별도의 노드(코드에서는 other_node)를 만들어서 우물을 팔 때 발생하는 비용으로 각 노드와 연결시켰습니다. 이렇게 구축한 .. 2023. 2. 3. [BOJ] 일요일 아침의 데이트 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제의 지문을 잘 읽어야하는 국어문제입니다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다. 라는 지문의 내용이 있는데 이 부분을 처리하지 않으면 잘못된 답이 나오게 됩니다. S, F인 경우에는 쓰레기에 인접해있지 않는 칸으로 처리하여 해결하면 됩니다. 큐에서 빠져나오는 우선순위를 정해주기 위해 우.. 2023. 2. 2. [프로그래머스] 파괴되지 않은 건물 - python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 일반적으로 skill이 적용되어야 하는 범위에 매번 (r1, c1) ~ (r2, c2)에 적용을 하면 최악의 경우 O(Skill의 개수 * 최대 가로 길이 * 최대 세로 길이) = O(250000 * 1000 * 1000)가 되어 시간 초과가 나게 됩니다. 매번 범위에 적용하지 않고 한번에 발생한 Skill을 적용하기 위하여 누적합 방식이 필요합니다. 1차원 배열을 기준으로 생각했을 .. 2022. 9. 25. 이전 1 2 3 4 5 다음