Algorithm/BOJ
-
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 14502, 연구소 📌 난이도 : Gold 4 📌 알고리즘 : BFS & DFS 이번 문제는 Multi-Source BFS 문제이다. 벽 3개를 두어서 안전 공간을 최대한 확보하는 것이 중요하다. 그렇기에 빈 공간에 차례로 벽 3개를 두는 경우를 탐색하며 BFS 로 안전 공간을 구하는 로직을 구현하겠다. 🧩 프로세스 📚 초기화 및 선언 : 빈 공간을 확인할 int[] blank 를 선언해준다. 이는 전체 넓이..
(JAVA) [BOJ]백준 14502번, 연구소https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 14502, 연구소 📌 난이도 : Gold 4 📌 알고리즘 : BFS & DFS 이번 문제는 Multi-Source BFS 문제이다. 벽 3개를 두어서 안전 공간을 최대한 확보하는 것이 중요하다. 그렇기에 빈 공간에 차례로 벽 3개를 두는 경우를 탐색하며 BFS 로 안전 공간을 구하는 로직을 구현하겠다. 🧩 프로세스 📚 초기화 및 선언 : 빈 공간을 확인할 int[] blank 를 선언해준다. 이는 전체 넓이..
2023.08.26 -
https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2251, 물통 📌 난이도 : Gold 5 📌 알고리즘 : 그래프이론, BFS 이번 문제는 본인 기준으로 어려워서 이해하는데만 한 시간 이상이 걸린 것 같다. 이 문제를 읽고 그래프와 BFS 를 떠올리기가 쉽지 않았고 그에 맞는 구조체를 구현하는게 쉽지 않았다. 🧩 프로세스 📚 State, 물의 이동을 표현할 구조체 : 물을 붓고 나서의 양을 구하는 클래스이다. 생성자로 A,B..
(JAVA) [BOJ]백준 2251번, 물통https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2251, 물통 📌 난이도 : Gold 5 📌 알고리즘 : 그래프이론, BFS 이번 문제는 본인 기준으로 어려워서 이해하는데만 한 시간 이상이 걸린 것 같다. 이 문제를 읽고 그래프와 BFS 를 떠올리기가 쉽지 않았고 그에 맞는 구조체를 구현하는게 쉽지 않았다. 🧩 프로세스 📚 State, 물의 이동을 표현할 구조체 : 물을 붓고 나서의 양을 구하는 클래스이다. 생성자로 A,B..
2023.08.26 -
https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 20922, 겹치는 건 싫어 📌 난이도 : Silver 1 📌 알고리즘 : 투포인터 이번 문제는 투포인터 문제이다. 루프 안에서의 범위 설정에 주의해야 한다. 🧩 프로세스 📚 초기화 및 선언 : 정수 N 과, 중복의 수 K를 입력받고 N개만큼의 int[] 를 생성해서 값을 넣어준다. 또한 수의 중복값을 확인하기 위해 int[] arr 을 생성해준다. N 의 범위 때문에 new int[100,..
(JAVA) [BOJ]백준 20922번, 겹치는 건 싫어https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 20922, 겹치는 건 싫어 📌 난이도 : Silver 1 📌 알고리즘 : 투포인터 이번 문제는 투포인터 문제이다. 루프 안에서의 범위 설정에 주의해야 한다. 🧩 프로세스 📚 초기화 및 선언 : 정수 N 과, 중복의 수 K를 입력받고 N개만큼의 int[] 를 생성해서 값을 넣어준다. 또한 수의 중복값을 확인하기 위해 int[] arr 을 생성해준다. N 의 범위 때문에 new int[100,..
2023.08.23 -
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1068, 트리 📌 난이도 : Gold 5 📌 알고리즘 : DFS 📌 자료구조 : 트리 이번 문제는 DFS 와 트리 구조를 사용하여 문제풀이를 진행했다. 💻 📚 Process 초기화 및 선언 : 노드의 개수만큼 ArrayList[] adj 를 생성해준다. 이는 부모 노드에 연결된 자식 노드들을 표기하기 위함이다. N개 만큼 ArrayList를 선언해주고 시작 노드와 삭제할 노드를 차례로 입력..
(JAVA) 백준 1068번 : 트리https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1068, 트리 📌 난이도 : Gold 5 📌 알고리즘 : DFS 📌 자료구조 : 트리 이번 문제는 DFS 와 트리 구조를 사용하여 문제풀이를 진행했다. 💻 📚 Process 초기화 및 선언 : 노드의 개수만큼 ArrayList[] adj 를 생성해준다. 이는 부모 노드에 연결된 자식 노드들을 표기하기 위함이다. N개 만큼 ArrayList를 선언해주고 시작 노드와 삭제할 노드를 차례로 입력..
2023.08.17 -
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1987, 알파벳 📌 난이도 : Gold 4 📌 알고리즘 : DFS 완전탐색 이번 문제는 DFS로 쉽게 풀었다가 틀려서 1시간 정도 고생했었다. DFS 접근하지만 최대값을 구해야 하기 때문에 완전 탐색으로 모든 구역을 탐색해야 한다는 점을 주의해야 한다. 📚 Process 초기화 및 선언 : 알파벳을 순서대로 char[][] map 에 넣어주는 것으로 시작한다. 알파벳을 사용했는지 확인하기..
(JAVA) [BOJ]백준 1987번, 알파벳https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1987, 알파벳 📌 난이도 : Gold 4 📌 알고리즘 : DFS 완전탐색 이번 문제는 DFS로 쉽게 풀었다가 틀려서 1시간 정도 고생했었다. DFS 접근하지만 최대값을 구해야 하기 때문에 완전 탐색으로 모든 구역을 탐색해야 한다는 점을 주의해야 한다. 📚 Process 초기화 및 선언 : 알파벳을 순서대로 char[][] map 에 넣어주는 것으로 시작한다. 알파벳을 사용했는지 확인하기..
2023.08.17 -
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 14938, 서강그라운 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제는 DFS 로 풀이를 시도했다가 처참하게 틀리고 플로이드 와샬로 재풀이를 진행하였다. 📚 Process 초기화 및 선언 : 지역의 개수 N, 수색범위 M, 길이개수 R 을 차례로 입력받고 아이템 개수를 받을 item[] 을 선언해서 차례로 채워준다. 수색 길이를 입력받을 int[][]..
(JAVA) [BOJ]백준 14938번, 서강그라운드https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 14938, 서강그라운 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제는 DFS 로 풀이를 시도했다가 처참하게 틀리고 플로이드 와샬로 재풀이를 진행하였다. 📚 Process 초기화 및 선언 : 지역의 개수 N, 수색범위 M, 길이개수 R 을 차례로 입력받고 아이템 개수를 받을 item[] 을 선언해서 차례로 채워준다. 수색 길이를 입력받을 int[][]..
2023.08.16 -
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1956, 운동 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제도 플로이드 와샬을 통한 최단 거리를 구하는 문제이다. 📚 Process 초기화 및 선언 : 마을의 개수 V, 도로의 개수 E 를 입력받고 E개만큼 단방향 그래프를 생성해준다. 양방향이 아님에 주의해야 한다. 추가로 여기서 연결되는 노드가 없을 때는 I..
(JAVA) [BOJ]백준 1956번, 운동https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1956, 운동 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제도 플로이드 와샬을 통한 최단 거리를 구하는 문제이다. 📚 Process 초기화 및 선언 : 마을의 개수 V, 도로의 개수 E 를 입력받고 E개만큼 단방향 그래프를 생성해준다. 양방향이 아님에 주의해야 한다. 추가로 여기서 연결되는 노드가 없을 때는 I..
2023.08.16 -
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 11404, 플로이드 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제는 문제 이름에서부터 알 수 있듯이 플로이드 와샬 문제이다. a -> b 도시에 가는데 비용이 주어지는데 중복이 있을 수 있으므로 최소 값을 저장해야 한다. 📚 Process 초기화 및 선언 : 도시의 개수 N, 버스의 개수 M을 입력받고 M개만큼의 비용이 주어진다. 이것을 단방향..
(JAVA) [BOJ]백준 11404번, 플로이드https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 11404, 플로이드 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall) 이번 문제는 문제 이름에서부터 알 수 있듯이 플로이드 와샬 문제이다. a -> b 도시에 가는데 비용이 주어지는데 중복이 있을 수 있으므로 최소 값을 저장해야 한다. 📚 Process 초기화 및 선언 : 도시의 개수 N, 버스의 개수 M을 입력받고 M개만큼의 비용이 주어진다. 이것을 단방향..
2023.08.16