본문 바로가기

알고리즘/백준

 (51)
[백준] 21610 마법사 상어와 비바라기 JAVA 문제 링크 : https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제에서 하라는 대로 구현하면 된다. import java.io.*; import java.util.*; public class baekjoon_21610{ public static int N,M; public static int board[][]; public static int dir[][] = {{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{..
[백준] 13911 집 구하기 [JAVA] 문제링크 : https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 코드가 더럽다. 아이디어는 아래와 같다. 스타벅스거리 + 맥도날드 거리의 합이 최소인 집의 거리를 출력한다. 스타벅스거리와 맥도날드 거리를 따로 구해서 모든 집마다 스타벅스거리 + 맥도날드 거리의 합을 비교하는 것이다. 스타벅스거리를 구하는 방법은, 아무 스타벅스에서 다익스트라를 수행한다. 다음 노드가 집이면 스타벅스 거리가 늘어나..
[백준] 2479 경로 찾기 [JAVA] 문제링크 : https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 이진 수 코드 간 해밍 거리가 1인 이진 수 끼리는 연결돼 있다고 표현한다. 시작 점에서 연결된 이진 수 코드는 거리가 1이고, 연결된 이진 수 코드에서 다시 연결된 이진 수 코드간 거리는 1이므로, 이를 X번 반복해서 목적지 이진 수 코드를 찾을 수 있으면 해밍 거리가 X인 것이다. 이것은 BFS다. import java.io.*; import java.util.*; public..
[백준] 18223 민준이와마산그리고건우 [JAVA] 문제 링크 : 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 민준이가 최단 경로로 갈 때, 그 경로에 건우가 있다면 SAVE HIM을 출력하는 문제다. 최단 경로이므로 다익스트라를 활용할 수 있을 것이라 생각했다. 문제에서 최단 경로가 여러개이고 그 경로들 중에 건우를 구할 수 있을 때, 민준이는 건우를 구하는 경로를 택한다 하였다. 따라서 X->Y로의 거리가 X->Z->Y의 거리가 같은 경..
[백준] 1613 역사 [JAVA] 문제링크 : https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 문제 분류가 플로이드 워셜 알고리즘이란 것을 알고서 풀이를 시작한 문제다. 그러나 어떻게 플로이드 워셜로 해결되는지 파악이 안됐었다. 그러다가 최단 거리를 어떻게 갱신하는지 생각해봤다. 플로이드 워셜 알고리즘은 어떤 위치 x가 영향력을 끼치는(x를 지나가면 최단거리가 갱신되는) 모든 a->x->b(1 b OR a < x < b를 판단 가능하면 갱신해 나간다. 플로이드 워셜 알고..
[백준] 11562 백양로 브레이크 [JAVA] 문제링크 : https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 워셜 알고리즘에 대해 이해하고 있어야한다. A 와 B 사이의 간선이 양방향일 경우 거리는 0이며, A->B로 단방향일 경우 A->B의 거리는 0, B->A의 거리는 1이다. X -> Y로 갈 때 최소의 거리(단방향 도로를 양방향으로 바꾸는 비용)를 최대 3만번 구해야 한다. 건물의 수는 최대 250개 이므로 플로이드 워셜 알고리즘을 활용해서 최소 거리를 미리 구해놓고 해결했..
[백준] 21609번 상어 중학교 [C++] 문제링크 : www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 친구가 빨리풀기 대결하자고 해서 언어를 맞추기위해 오랜만에 C++로 풀었다. 최근 삼성 역량테스트 문제다. 그래서 구현이 조금 까다롭지만 시키는대로 잘 하면 된다. 이런 문제를 많이 풀어보는 게 삼성 역량테스트에서 중요한 것 같다. 메인함수부터 순서대로 설명하면 이렇다. 조건에 해당하는 블럭이 있을 경우(loop==true) 반복한다. 블럭 묶음의 갯수를 파악하기 위해 dfs함수를 호출했다. 0..
[백준] 2098 외판원 순회 문제링크 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어떤 위치에서 출발해서 모든 여행지를 방문하고 마지막엔 다시 원래 위치로 돌아오는 방법 중 가장 짧은 거리를 구하는 문제이다. 처음에 문제를 잘못 알아서 모두 방문 후에 원래 위치로 돌아올 때는 여행지를 방문하면서 와도 되는 줄 알았다. 그래서 플로이드 워셜로 여행지 간 최소거리를 저장해두고 dfs의 마지막에는 start로 돌아오는 최소 거리를 더해주었었다. 하..

티스토리툴바