본문 바로가기

프로그래밍74

[다익스트라] 백준 레이저 통신 이번 문제는 백준 6087 레이저 통신 문제입니다. 다익스트라를 이용해서 풀었습니다. 각 지점의 최소거리(거울 개수)를 구하고, 이를 이용하여 또 다른 레이저 좌표까지 탐색하도록 했습니다. 중요한 점은 이전에 어떤 방향으로 진행했는지 알아야 합니다. 그래야지 거울 개수를 알 수 있기 때문입니다. import heapq def dij(razer_pos, board, r, c): hq = [] direction = {} direction['up'] = {'up':(1,0), 'left':(0,-1), 'right' : (0,1)} direction['down'] = {'down':(-1,0), 'left':(0,-1), 'right' : (0,1)} direction['left'] = {'left' : (0.. 2022. 12. 25.
[프로그래머스] 양과 늑대 접근 방법 단순한 단순탐색 문제. 방문했던 노드로 다시 돌아올 수 있다는 점이 차별점입니다.. 방문했던 노드와 인접한 모든 노드를 탐색하면 됩니다. 저는 lv2인 양궁대회보다 이 문제가 더 쉽다고 느껴졌습니다. import java.util.List; import java.util.ArrayList; class Solution { public int[][] graph = null; public int n = 0; public int maxSheep = 1; public int solution(int[] info, int[][] edges) { this.n = info.length; this.graph = new int[this.n][this.n]; for(int i = 0; i < edges.length.. 2022. 8. 20.
[bfs] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net #include #include #include #include using namespace std; int main(){ int map[100][1.. 2019. 4. 29.
[이분 탐색] 백준 2110 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net #include #include using namespace std; int main(){ int n, c; int arr[200000]; cin >> n >> c; for(int i = 0; i < n; i++) scanf("%d", arr+i); sort(arr,arr+n); int left = 0, right = .. 2019. 4. 8.
[이분 탐색] 백준 2343 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급 www.acmicpc.net 길이(mid)를 정해두고, 만약 이 길이를 넘거 같아지면 새로운 블루레이 cd에 길이를 저장하는 방식으로 풀었습니다. #include .. 2019. 4. 8.
[이분 탐색] 백준 10816 숫자 카드2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00 www.acmicpc.net #include #include using namespace std; int main(){ int n, m; int arr[50.. 2019. 4. 7.

티스토리툴바