문제https://www.acmicpc.net/problem/14267 풀이트리에서의 dfs 방법으로 문제를 해결했습니다. dfs이지만, 배열에서의 누적 합의 매커니즘과 굉장히 비슷한 문제입니다. 누적합은 쉽게 말해, [0,1,1,0,1,1] 과 같은 배열을 nums[i+1] += nums[i] 와 같은 식을 통해 [0,1,2,2,3,4] 과 같은 결과를 도출하는 것입니다. 이 문제도 마찬가지로, 배열에 값을 입력받고 누적합을 돌리는데 위와 같이 인덱스가 연속된 경우가 아닙니다. 그래서 연속된 인덱스를 dfs로 탐색하며 누적합을 시키는 매커니즘입니다. 값을 입력받을 때, list에 사원 번호를 연결시킵니다. 그리고 1번(사장)에서 dfs를 시작해, score 배열을 누적 합을 시켜나갔습..
Java
문제https://www.acmicpc.net/problem/2661 풀이백트래킹을 활용한 문제입니다. 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다. 이 문제에서 포인트가 두 가지가 있다고 생각합니다. 첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다. 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다. 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니..
문제https://www.acmicpc.net/problem/1063 풀이 구현 문제입니다. 입력값을 어떤 형식으로 받을 것인지, 그리고 구현을 위한 메서드를 어떻게 나누고 적용할 것인지가 중요한 포인트 같습니다. 처음 구현시에 입력값도 String으로 받고 메서드를 제대로 분리하지 못했더니 너무 코드가 난잡해져서, 다시 입력 자료구조와 메서드를 정의해 문제를 해결했습니다. 우선 입력 시 char[] 배열을 통해 체스의 행과 열을 각각의 인덱스에 저장을 해주었습니다. 메서드는 크게 두 가지인데, chess를 옮기는 것과 범위를 체크하는 것입니다. 이 메서드를 king과 stone을 옮길 때 모두 사용할 수 있게끔 유연하게 만들어주었습니다. 그리고 조건에 통과해야지만, 이동된 배열 값에 업데이트를..
문제https://www.acmicpc.net/problem/1240 풀이 트리에서의 탐색 문제입니다. Dfs를 이용해서 문제를 해결했습니다. 우선 Arraylist[] 배열에 입력값을 입력받습니다. 이 때, 방향은 양방향 모두 갈 수 있으니 양뱡향으로 입력 받습니다. 그리고 dfs메서드를 통해 시작점부터 탐색을 시작합니다. 한 가지 주의해야할 것은, 거리의 합을 구하는 것에 있습니다. 만약 아래와 같은 입력 값이 주어질 때를 생각해보겠습니다. 4 11 2 12 3 12 4 11 4// 정답 2 이 반례 코드에서 2는 3, 4의 두 방향으로 뻗게 됩니다. 그래서 3으로 보낸 dfs에서 거리의 합에 거리를 더하고, 그것을 바로 4로 보내게 되면 중복해서 값이 들어가게 됩니다. 그래서 한 노드에서 ..
문제https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱www.acmicpc.net풀이백트래킹 문제입니다. 연산자별로 입력받은 수를 통해, 연산자의 순서를 정하고 계산을 수행하면 됩니다. 순열을 통해 연산자의 순서를 결정할 수 있는데, 일반적인 순열 재귀 시 사용하는 visited 배열을 int[]로 선언하여, 해당 연산자 사용 시에는 해당하는 인덱스 값을 --해주는 것이 문제의 포인트입니다. ..
지난 포스팅에서 JCF를 다루었습니다. 이번 포스팅에서는 JCF의 ArrayList에 대해 살펴보겠습니다. ArrayList와 LinkedList 차이우선, ArrayList와 LinkedList의 개념적인 차이를 통해 ArrayList를 살펴보겠습니다. ArrayListArrayList는 데이터들이 쭉 늘어선 배열의 형식입니다. ArrayList는 데이터의 인덱스를 가지고 있어서, 탐색(시간 복잡도: O(1))이 매우 용이하지만 데이터의 삽입과 삭제에서는 인덱스들의 위치를 조절해주어야 하기 때문에 O(n)의 시간 복잡도를 가집니다. LinkedList 반면, LinkedList는 자료의 주소값으로 서로 연결되어있는 구조입니다. 내부적으로 양방향의 연결리스트로 구현되어있습니다. 탐색 시에 순차적으로 ..
