Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 모든 경우의수를 다 대입해서 탐색했습니다. 순서에 대한 모든 경우를 결정한 뒤, 결정된 배열의 각 층을 모두 돌려서 모든 경우를 구한 뒤, BFS를 통해 최소경로를 찾았습니다. 이때 어차피 모든 경우의 수를 다 탐색하기때문에, 임의로 입구를 (0,0,0), 출구를 (4,4,4)로 고정해도 문제가 해결됩니다. 시간복잡도 순서를 정하는 경우의 수 O(5!), 각 순서를 정한..

2022. 12. 31.

문제풀이/백준oj

https://www.acmicpc.net/problem/21943 21943번: 연산 최대로 $N$개의 양의 정수 $X_{i}$와 곱하기 연산자, 더하기 연산자가 총 $N - 1$개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다. www.acmicpc.net 풀이 백트래킹을 이용하여 모든 경우의수를 구해주었습니다. 이때 만약 곱셈이 2개가 있다면, 아래와 같이 3개의 그룹을 생성해준 뒤, 곱해주며 갱신하는 방식으로 백트래킹을 진행했습니다. 시간복잡도 백트래킹의 시간복잡도이고, N개 각각 최대 N-1개의 선택지가 있기때문에 O(N^(N-1)) 이 됩니다. 코드 import java.io.BufferedReader; import java.io..

2022. 12. 28.

문제풀이/백준oj

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다. 그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다. 이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다. 시간복잡도 ..

2021. 11. 7.

문제풀이/백준oj

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 1. 맵을 입력받는다. 2. 입력받은 뒤, 좌 우 좌 우 순서대로 부술 라인을 입력받는다. 3. 해당라인, 해당 방향에서 처음 만나는 미네랄을 부순 뒤, 상/하/좌/우 를 BFS로 탐색을 하면서, 바닥과 연결되어있지않은(중력에의해 떨어져야 하는 미네랄 덩어리)를 찾아준다. 문제에서 2개의 덩어리가 동시에 떨어지지 않는다는 조건이 있으므로, 하나의 덩어리만 찾아질것이다. 4. 만약 3번에서 중력에의해 떨어져..

2021. 9. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 최단거리를 구하기 위한 알고리즘 중 다익스트라 알고리즘을 이용했다. 다익스트라 알고리즘을 이용해서, 먼저 S지점, H지점, G지점에서 각각 모든지점까지의 최단거리를 구해준다. 그런뒤, S에서 각 목적지까지의 거리가, S->H->G->목적지 또는 S->G->H->목적지 까지의 거리와 같다면, 요란한 옷차림을 한 서커스 예술가들이 H와 G도시 사이에 있는 경로를 지나왔다는 의미가 되므로, ..

2021. 9. 11.

문제풀이/백준oj

https://www.acmicpc.net/problem/6209 6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 풀이 https://khu98.tistory.com/257 [프로그래머스] 징검다리 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개.. khu9..

2021. 9. 3.

문제풀이/백준oj

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 입력받은 이름들을 숫자로 매핑해준뒤, Find-Union 알고리즘을 이용해서 네트워크를 연동시켜준다. 이때, 연결하고 카운팅을 하면 시간초과가 날 수 있으므로, 네트워크를 연결함과 동시에, 부모노드에 다른하나에 연결된 노드의 cnt를 더해준뒤, 부모노드의 cnt를 리턴해주면 시간초과가 나지 않고 값을 바로 구할 수 있게된다. 또한, 친구관계를 최대 100,000개 입력받는다 했으므..

2021. 8. 29.

문제풀이/백준oj

https://www.acmicpc.net/problem/14595 14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net 풀이 먼저 빅-종빈 빌런이 문을 뿌수는 행동을 입력받은것들을, 시작 방을 기준으로 오름차순 정렬을 해준다. 그런뒤 처음 종빈 빌런이 뿌수는 방을 left와 right에 저장을 해둔뒤, 다음오는 행동의 시작방이 right보다 작거나 같으면, 지금 부수고 있는 방과 한방으로 합쳐지므로, right를 갱신해준다. 만약 다음행동의 시작방이 ..

2021. 8. 23.