Hailey

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 난이도 문제 이해 ⭐⭐⭐⭐ 구현 ⭐⭐⭐⭐ | 문제 해결방법 💡Idea : 순열 + 브루트포스 알고리즘 1. 타순을 결정한다.( 한 번 결정된 타순으로 모든 이닝을 진행 ) - permutation() 2. 게임을 진행한다. ( 한 이닝은 아웃이 3회가 되면 종료한다. ) 2-1. 주어진 이닝 수 만큼 게임을 진행한다. - game() 2-2. 타자가 공을 친 만큼 주자들이 움직인다. - run() 3...

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net | 문제 해결방법 ⭐Idea : 백트랙킹 + dfs 백트랙킹이.. 어려워서 오래걸렸다. 약 2시간😥 아래 블로그를 참고해서 공부한 후 다시 풀었다. 참고 블로그 : https://sorjfkrh5078.tistory.com/22 [JAVA] 해설 코드 package simulation; import java.io.BufferedReader; import java.io.IOException; ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net | 문제 해결방법 ⭐Idea : 크루스칼 알고리즘 가장 기본적인 크루스칼 알고리즘 문제 [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net | 문제 해결방법 ⭐Idea : 크루스칼 알고리즘 ( '가장 적은 간선으로 모든 노드를 연결하는 방법' 을 구하기 ) 크루스칼 알고리즘은 모든 간선을 연결하는 최소 비용을 구할 때 사용한다. 각 간선의 크기가 주어진 경우라면, 간선의 크기로 오름차순 정렬을 해준 후 정렬된 순서대로 간선을 연결한다. ✔ 하지만 이 문제는 간선의 크기가 없어서 간선의 크기는 고려..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net | 문제 해결방법 ⭐Idea : 투 포인터 알고리즘 여기서 매번 값을 계산하기 위해 for문을 사용하면 시간초과 난다. 총 합에서 다음 요소를 더해주거나 맨앞의 요소를 빼주는 방법으로 접근. 유사한 문제 : 백준 2003 수들의 합2 (https://www.acmicpc.net/problem/2003) [JAVA] 해설 코드 package week11; import java.io.B..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net | 문제 해결방법 ⭐Idea : 투 포인터 알고리즘 [JAVA] 해설 코드 package week11; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BO..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net | 고려 요소 상어의 속력이 큰 경우, map안에서 1. 위, 아래 또는 2. 좌, 우 로 같은 길을 반복해서 이동 반복으로 인해 시간 초과 문제 발생 | 해결 방법 상어의 속력을 저장하기 전에 1. 위, 아래의 경우 map의 row로 2. 좌, 우의 경우는 col 크기로 mod 연산한 후 그 값을 속력으로 저장 이 방법으로 불필요한 반복을 줄일 수 있다. // d==1 상 d..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 비트마스킹에 대한 글을 포스팅 한 후 금방 터득한 생생한 지식으로 바로 풀어보았다✨ | 문제 해결방법 부분집합 구하는 공식 + 비트마스킹 부분집합을 구할 때 1. boolean배열을 사용할 수도 있고 2. 비트마스킹 기법을 사용할 수도 있다. 이번 문제에서는 비트마스킹 기법을 사용하였고, 이 기법은 비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net | 문제 해결방법 이 문제는 제목에서 대놓고 힌트를 주고 있다. 플로이드-워셜 알고리즘으로 문제를 풀면 된다. 기본적인 플로이드-워셜 문제와 거의 동일하다. 한 가지 다른 점은 예제를 한 번 손으로 적으면서 돌려보면 알 수 있는데, 같은 간선에 비용만 다른 경우가 존재한다. 이 경우 우리가 하려고 하는 값은 최소 비용이기 때문에 작은 비용을 선택해주면 된다. 그리고 내가 두 번이나 틀렸던 이유로 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs + 인접행렬 1. 입력받은 네트워크 쌍을 이용해 인접행렬을 초기화 한다. 2. (1,1) 부터 시작하여 네트워크로 연결되어 있는 컴퓨터를 모두 탐색한다.( bfs + visited[] ) 3. visited[] (방문한 컴퓨터는 true가 됨) 배열에서 true의 개수를 반환(1번 컴퓨터는 counting하지 않음) [JAVA] 해설 코드 import java..