![]()
https://www.acmicpc.net/problem/1184 1184번: 귀농 상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단 www.acmicpc.net 난이도 골드 1 풀이 임의의 한 점을 기준으로 분할 해준 뒤 점을 기준으로 대각선에 있는 부분의 합이 같으면 된다. 일단 한 좌표를 기준으로 분할을 한다. 가장자리를 기준으로 분할하면 크기가 0인 부분이 생기기 때문에 가장자리를 제외한다면 (N-2)^2가지 경우의 수가 있다. 그럼 다시 그 좌표를 기준으로 대각선에 있는 두 부분에서 좌표 하나를 선정해준다. 위 사진 기준으로 파란 점 4와 빨간 점 1..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 유형 다익스트라 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 ..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제요약 첫번째 노드부터 주어진 N번째 노드까지의 최단경로를 구한다. 다만, 두개의 노드가 추가로 주어지는데 이 두 노드를 반드시 경유해야 한다. 문제해결 다익스트라 알고리즘을 여러번 사용하여 문제해결을 하였다. 다만 고려사항이 몇가지가 있다. 고려사항 1. 주어진 두 노드를 지나는 순서에 따라 최단거리가 달라질 수 있다. 따라서 두가지 경우를 고려해야..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해석 최단거리에 대한 문제이므로 다익스트라를 생각해볼 수 있다. 또한, 문제에 '단방향'이라고 적혀있다. 다익스트라 문제를 풀어보면서 '단방향'이 일반적인 문제이고 여기에 조금 더 심화된 것이 '양방향'인 것 같다. 그래도 결국 다익스트라 로직에서는 크게 벗어나지 않는다. 해당 문제도 '단방향'인 것은 맞지만 왔다가 다시 돌아와야하는 문제이다. 그래서 예제를 보..
![]()
문제 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net Algorithm 양방향 간선이고, 문제에서 요구하는 것이 건우의 위치를 지나는 path가 최단거리인지 확인하는 문제이다. 양방향 간선이므로, 시작점이 1인 dijkstra알고리즘과 시작점이 4인 dijkstra알고리즘을 돌려서 두개의 path의 값을 비교해 주면 된다. 둘의 값이 같으면 건우의 위치를 지나도 최단거리이므로 SAVE HIM을..
![]()
문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Algorithm 문제의 상황을 그래프로 나타내고 다익스트라로 해결할 수 있다. 생성해야 할 그래프는 왼쪽으로, 또는 오른쪽으로 갈 수 있으면 현재 점 i에서 i-1 또는 i+1인 노드로 이동하며 이 때의 비용은 각 1이고, 순간이동이 가능하다면 i에서 2*i노드로 이동하며 비용은 0인 그래프이다. 이 때 노드의 개수는 N 또는 K의 범위의 길이이다. C..
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(N..
![]()
문제 풀이 1부터 N까지의 노드가 있고, 1에서 N까지 가는 최단 거리를 찾는 문제와 동일하다. 다익스트라를 사용하여 최단 거리를 구해주었다. 코드 import sys from heapq import heappop, heappush input = sys.stdin.readline INF = 1e9 def dijkstra(graph, n): hq = [(0, 1)] distance = [1e9] * (n + 1) distance[1] = 0 while hq: dist, cur = heappop(hq) if dist > distance[cur]: continue # 예외 처리 for weight, next_node in graph[cur]: next_dist = dist + weight if next_dis..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 ..
beginning 에서 target 으로 가려고 한다. 우선 바꿔져야 하는 곳을 1로 표현해보면 아래와 같이 change_spot을 만들 수 있다. change_spot을 만들어보면 특징을 볼 수 있는데, 행 별로 서로 같거나, 반전된 비트이다. 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 이를 우선적으로 체크해서 만약 같거나 반전되지 않는 경우가 있다면 -1을 return 하고, 그렇지 않다면 된다는 가정 하에 최소 경우의 수를 찾는다. def solution(beginning, target): answer = 0 row = len(beginning[0]); col = len(beginning) #열, 행 change_spot = [['0' for _ in ..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제요약 격자에 바이러스가 위치한 좌표, 벽의 좌표가 표시되어있다. 벽을 3개 세워서 바이러스가 퍼지지 않는 곳의 최대넓이를 구하라. 문제해결 시뮬레이션 단계에 따라 각각 그래프 순회를 해야한다. 먼저 주어진 격자의 정보를 입력 받고, 벽을 3개 세울 때는 원본정보가 변하지 않게 다른 격자에다가 복사를 한 뒤 시뮬레이션을 한다. 벽을 시뮬레이션할 때는 DFS를 적용하였다. 벽을 다 세운뒤에는 바이러스 확산을 ..
