https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 스택을 통해서 괄호를 확인하는 것은 잘 구현했는데, 점수를 매기는 부분에서 어려움을 겪었다. 처음에는 스택 하나로 '()'와 '[]'를 모두 해결하려 했지만 두 가지 경우 따로 스택을 만들어 주는 쪽이 계산하기 편했다. 여는 괄호가 나오면 tmp에 점수를 곱하고, 닫는 괄호가 나오면 바로 직전 값이 같은 유형의 여는 괄호인 경우에만 결과값에 더해주고 tmp를..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 2022.07.31 - [Algorithm/BOJ] - [BOJ][python] 2110. 공유기 설치 문제를 풀었던 것이 도움이 되었다. 랜선 길이를 찾기 위해서 왼쪽 값(l)은 1, 오른쪽 값(r)은 랜선 길이의 최댓값으로 초기화해주었다. N개 이상의 랜선을 가져야 하는데, 랜선의 개수는 모든 랜선을 이분탐색하며 중간 값(..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 문제의 분류를 보지 않으면 이분 탐색 문제라는 것을 알기 어려운 것 같다. 그리고 이 문제는 간격의 최대값을 찾는 문제이므로, 왼쪽 값과 오른쪽 값을 초기화 할 때 조심해야 한다. 왼쪽 값(l)은 최소 간격인 1, 오른쪽 값(r)은 최대 간격인 가장 작은 좌표값과 가장 큰 좌표값의 차이이다. 이분 탐색을..
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 현재 위치에 적혀있는 값만큼 오른쪽 또는 아래쪽으로 점프해서 이동하여 도착지점(0)에 다다르는 경로의 개수를 구해야 한다. 처음에는 BFS 문제인 줄 알았으나 DP로 풀 수 있는 문제였다. 시작점을 1로 두고 모든 행렬을 돌면서 점프한 후의 위치에 이전 DP값을 끌고가면 된다. 거치지 않는 부분은 0이므로 아무것도 더해지지 않고 계속 0이고, ..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 💡IDEA 구현하는 문제이다. 처음 문제를 보았을 때 BFS를 사용해야할 줄 알았으나, 간단하게 구현만 해주면 되는 문제였다. 구현하는 조건이 쉽지는 않아 조금 헤매긴 했다. 방향을 왼쪽으로 틀어준다는 점이 까다로워서 따로 함수를 만들어 현재 방향에 따른 왼쪽 방향 배열을 구했다. visited 배열을 사용하지 않고 하려면, 벽인 부분(1)과 방문한 부분(-1)을 구분해야한다. 현재 방향에 맞는..
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 점화식을 구하는 데 어려움을 겪었는데, 노가다로 N=3까지 계산했으나 규칙이 눈에 들어오지 않았다. 검색을 통해 점화식을 보고서야 이런 규칙이었구나 깨닫게 되었다. 현재 dp는 (한 단계 전 dp의 두 배 + 두 단계 전 dp)%9901 이다. 또다른 방법으로 3×N 행렬을 만들어 현재 우리가 빈 우리일 경우, 왼쪽에 사자가 있는 우리일 경우, 오른쪽에 사자가 있는 우리일 경우로 나누어 생각해보았다. 빈 우리일 경우, 이전 우리가 빈 우리든, 사자가 어디 있든 상관 없이 세 경우를 모두 ..
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 💡IDEA 그리디 알고리즘, 정렬을 사용하는 문제이다. 정렬은 key=lambda를 사용하여 배열의 0번째 값인 서류심사 성적으로 먼저 내림차순 한 후 1번째 값인 면접심사 성적으로 내림차순 했다. 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하기 위해 먼저 서류심사 성적으로 내림차순 정렬 후 첫번째 ..
https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 💡IDEA 수학의 소수를 사용하는 문제이다. 2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 6588. 골드바흐의 추측 [BOJ][python] 6588. 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 이분 탐색이란 가장 작은 값과 가장 큰 값을 기준으로 가운데 값을 찾아 타겟값을 비교하여 좌우 변수를 조정하며 탐색하는 방법이다. 이 문제에서는 가운데 값보다 큰 높이의 나무를 잘라낸 합으로 비교하며 좌우 변수를 좁힌다. 절단기에 설정할 수 있는 최대 높이를 구하기 위해 구한 합과 타겟값을 비교하며 가장 큰 높이를 ..
https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 문제는 크게 어렵지 않지만 시간초과의 늪에 빠지기 쉬운 문제이다. 소수를 구해두는 건 while문 안에 넣으면 시간이 오래 걸리므로 먼저 계산해두어야 한다. 구해둔 이 소수배열을 앞에서부터 확인하는데, 더해서 n이 되는 소수를 구해야 하므로 i번째가 소수인 것과 n-i번째가 소수인 것을 확인해주면 된다. 발견할 시엔 출력 양식에 맞추어서..
