📝 알고리즘

문제 (Gold 1) https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 숫자와 연산자를 한번에 저장할 수 있는 Expression 클래스 생성 -> 숫자를 char로 한번에 저장했더니, 9 이상의 숫자는 제대로 작동하지 않음 ㅠㅠ 연산 리스트에서 숫자가 나오는 짝수 인덱스를 돌며 연산 수행 후, 남은 연산 리스트를 재귀 돌림 기저조건: 리스트에 원소 하나만 남아있을 때 ( == 숫자 하나가 남아있을 때 ) 짝수 idx( ..

문제 (Gold 4) https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 문제 해석 1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다. 2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다. 즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다. 소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다..

문제 (GOLD 2) https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 시뮬레이션은 문제를 천천히 보면서 하나하나 구현하는게 가장 중요한 것 같다. Logic 높이 입력 받기 던지는 위치에 따라 분기 없어질 미네랄 위치 찾기 없어질 미네랄을 중심으로 오른쪽 공격이면 상, 하, 좌 왼쪽 공격이면 상, 하, 우 탐색하며, 떨어질 클러스터가 있는지 확인 ( breakMineral() ) BFS 돌며, 바닥과 맞닿아 있는 곳이 있는지 확인 있으면 fals..

문제 (Gold 1) https://www.acmicpc.net/problem/2233 2233번: 사과나무 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리 www.acmicpc.net 풀이 트리는 어렵다!!!!!!!!!!!!!!!!! 전체 로직 1. parent 배열과 root 배열 채우기 Stack을 이용하여 트리 만들기 이진 배열을 비교하며 삭제하고자 하는 노드의 '실제 인덱스' 구하기 2. 가장 가까운 공통 조상 구하기 parent배열을 사용한 재귀 기저조건: 루트까지 왔을 경우 or 다른 노드가 이미 방문 했던 노드를 방문할 경우 로..