Junior-Developer

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

문제풀이/백준oj

https://www.acmicpc.net/problem/12837 12837번: 가계부 (Hard) 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 문제를 해결했습니다. 먼저 세그먼트 트리는 완전 이진트리의 모양을 띄기 때문에 먼저 선언을 해주어야 하는데, 간편하게 4*N의 높이로 설정을 해주며 세그먼트 트리를 생성해주었습니다. static class SegTree { long tree[]; public SegTree(int n) { tree = new long[4 * n]; } } 문제의 1번 Operation은..

2022. 12. 28.

문제풀이/백준oj

https://www.acmicpc.net/problem/1473 1473번: 미로 탈출 세준이는 직사각형 모양의 미로에 갇혔다. 미로 안에는 1*1크기의 작은 방이 있다. 정사각형 모양의 각 방은 네 개의 면이 있는데, 이 네 개의 면에는 문이 있을수도 있고, 없을수도 있다. 각 방은 www.acmicpc.net 풀이 일반적인 BFS문제에서 N행M열을 돌렸는지 안돌렸는지 체크를 해주는게 문제의 포인트가 된다. 따라서 비트 마스크를 이용하여 visited[돌린 행을 체크해주는 비트][돌린 열을 체크해주는 비트][x][y] = 최소 시간 을 이용하여 문제를 해결해주었습니다. 예를 들면 4x4 행렬이 있고, (0,1) 좌표에서 방을 돌렸다고 가정을 하면 행 : 1000 => 1 열 : 0100 => 2 가 ..

2022. 12. 28.

문제풀이/백준oj

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 그리디하게 문제를 해결하기 위해서 먼저 도착지점을 기준으로 오름차순 정렬을, 도착지점이 같다면 출발지점을 기준으로 오름차순 정렬을 했습니다. 예제 1번을 가져와 보면 아래와 같이 정렬됩니다. 보내는 마을 받는 마을 박스 개수 1 2 10 1 3 20 2 3 10 1 4 30 2 4 20 3 4 20 그런 뒤, 각 마을에서의 관점에서 현재 트럭에 존재하는 박스의 개수를 담는..

2022. 12. 27.

문제풀이/백준oj

https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 풀이 먼저 입력을 받으면서 텔레포트 정거장을 그래프를 이용해서 연결해주었습니다. 그런 뒤, S부터 시작하며 BFS를 실행하여 E까지의 최단거리를 구했습니다. 1. 해당 정거장이 텔레포트 정거장이면, 연결된 정거장들을 통해 최단거리를 비교하며 진행합니다. 2. 다음정거장이 범위안에 있으면, 최단거리를 비교하며 진행합니..

2022. 12. 18.

문제풀이/백준oj

https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 풀이 간단한 DP문제입니다. DP[N] = 2*N의 타일을 배치할 수 있는 경우의 수라고 한다면, 아래의 설명과 같은 논리로 인해 일반식이 완성이 됩니다. 1. 2*N의 타일은 2*(N-1)의 타일에 2*1타일을 세로로 배치하면 되기때문에 DP[N-1]일때의 개의 경우의 수가 생깁니다. 2. 2*N의 타일은 2*(N-2)의 타일에 2*1 타일 두개를 나란히 가로로, 세로로 배치하거나 2*2 타일을 배치하면 되기때문에 DP[N-2] * 3의 경우의 수가 생깁니다. 3. 하지만 ..

2022. 12. 15.

문제풀이/백준oj

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 가장 기본적인 BFS문제이다. 그림을 만나면 해당 그림에 대한 BFS 탐색을 실시하며 넓이를 구해주고, 최대 넓이를 갱신해주면 된다. 시간복잡도 최악으로 모든 원소를 탐색하기 때문에 O(NM)이 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

2022. 12. 13.

문제풀이/백준oj

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 'w' = 0, 'o' = 1, 'l' = 2, 'f' = 3 으로 인덱스를 정해준 뒤, 문자열을 탐색하면서 조건을 확인해주었습니다. 이전 알파벳의 인덱스 == 현재 알파벳의 인덱스 이 경우에는 해당 인덱스의 cnt를 갱신시켜 줍니다. 이전 알파벳의 인덱스+1 == 현재 알파벳의 인덱스 이 경우에는, 이전 알파벳의 인덱스를 갱신시켜주고, 현재 알파벳의 개수를 갱신시켜줍니다. 현재 알파벳이 w인경우(새로운 wolf의 시작점인 경우) 현재까지 나온 w,o,l,f의 개수가..

2022. 12. 6.

문제풀이/백준oj

https://www.acmicpc.net/problem/13413 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 풀이 2가지 작업중 하나를 골라서 최소 횟수로 원하는 목표상태를 만들어야 합니다. 따라서 초기상태와 목표상태를 비교하여 Black -> White 의 개수와 White -> Black의 개수를 카운트 해준 뒤, 짝을 맞춰서 맞는짝은 1번작업을, 나머지는 2번작업을 해줍니다. 예를들어 아래와 같은 상황인 경우 WBBWW WBWBW Black -> White 의 개수는 1개, White -> Black..

2022. 12. 5.