https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🏗️ 설계 Board 배열에 전체 배열을 모두 입력 받고 minDP 배열과 maxDP 배열을 만들어 현재 줄까지 최댓값, 최솟값들을 구해가며 Dynamic Programming을 이용하여 풀이하고자 하였습니다. 하지만 Integer 배열 100,000 * 3 size의 배열 3개를 만들 경우 메모리가 초과되었습니다. 이 문제를 해결하기 위해서 2 * 3 size의 DP 배열 2개와, 3 size의 1차원 boa..
알고리즘 문제풀이
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 🏗️ 설계 가장 값이 작게 나오는 경우는 덧셈을 이용하여 값들을 최대한 키운 이후 해당 값들을 전부 뺄셈을 통해서 빼 주는 경우입니다. (그리디 알고리즘) 덧셈 기호를 만났을 경우에는 앞 뒤의 숫자를 계속해서 더해 나가고, 뺄셈 기호를 만났을 경우 지금까지 덧셈한 수를 Queue에 넣어둔 이후, Queue에 있는 값들을 마지막에 전부 빼 주는 방식으로 구현하였습니다. 📋 코드 import j..
https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 🏗️ 설계 입력받은 선수들 중 첫번째 선수는 4번타자로 고정 후 나머지 선수들의 타순을 순열(permutation)함수를 이용하여 선택합니다. 타순이 완성되었다면 완성된 타순으로 경기가 끝날 때 까지 얻을 수 있는 점수를 계산한 이후, maxScore 값을 갱신해 나가는 방식으로 풀이하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOExcepti..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 🏗️ 설계 주어진 수열이 있을 때 새롭게 입력받은 값에 따라서 부분 수열에 추가하는 방법을 달리 했습니다. 입력 받은 값이 현재 부분 수열의 가장 큰 값보다 클 경우 부분 수열의 맨 뒤에 새롭게 추가해 주기 입력 받은 값이 현재 부분 수열의 가장 큰 값보다 작거나 같은 경우 부분 수열 내에서 이분 탐색(Binary Search)를 이용해 현재 입력 받은 값과 가장 근접한 큰 수 (같은 수 포함)를..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🏗️ 설계 String을 입력받은 후 N / 4의 크기만큼 4개로 잘라 4개의 수를 Integer로 변환하여 Set에 넣음으로써 중복을 제거합니다. String의 맨 앞글자를 뒤로 옮기는 작업을 하며 위와 같은 행동을 반복 합니다. 총 3번 진행하면 초기 상태와 똑같아 지므로 이 때 Set에 있는 값을 ArrayList에 넣은 후 내림차순으로 Sort 하고, K번째 위치에 있는 값을 출력합니다. 📋..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🏗️ 설계 BFS를 사방 탐색 이외에 추가적으로 말처럼 이동할 수 있는 케이스 8개를 추가적으로 사용하였습니다. visited 배열을 jump 횟수에 따라 각각 따로 할당함으로써 해당 jump횟수에 방문하였는지 여부를 저장하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..
https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 🏗️ 설계 dynamic programming 기법을 사용하여 내가 지금까지 받은 칭찬을 직속 부하들에게 그대로 더해주는 방식을 사용하여 풀이하고자 하였습니다. 2차원 리스트를 이용하여 각 직원들 번호의 리스트에 직속 부하들의 번호를 저장하였습니다. dp[i] = dp[i] + dp[i - 1] 의 점화식을 사용하여 내가 기존에 상사로 부터 받은 칭찬 + 지금까지 상사가 받은 칭찬을 더해가는 방..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 🏗️ 설계 현재 익은 토마토들을 Queue에 넣고 근처 Queue들의 값을 들어있는 Queue의 값에 1씩 더해주며 최종적으로 나오는 가장 큰 값 - 1을 함으로써 다 익을 때까지 걸리는 시간을 구하고자 하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..
