CSE 전공노트

해당 문제는 bfs와 dp를 함께 사용하여 해결할 수 있습니다. 일반적인 bfs문제와 크게 다르지 않지만, 2차원 배열만으로 문제를 해결할 경우 코너에 대한 예외 경우가 너무 많아져 문제를 해결하기 어렵습니다. 따라서 height * width * 4 (4는 방향의 수) 크기의 배열을 만들어 방향 별로 가장 비용이 덜 드는 경우를 저장해주면 됩니다. 어떤 지점으로 이동하고자 할 때에 해당 지점의 해당 방향으로 이미 지나간 경로가 있는지를 확인하고, 이미 지나간 경로가 있다면, 해당 경로보다 비용이 적을 경우 큐에 추가해주는 형식으로 해결해 나가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

해당 문제는 2중 for문을 이용해 해결할 수 있습니다. 우선 문자열 s의 길이가 1이거나 2이면, 어떤 방법을 사용하더라도 문자열의 길이를 압축할 수 없기 때문에 그냥 문자열의 길이를 그대로 리턴해줍니다. 그 외의 경우에 대해 두 개의 반복문을 이용해 문제를 해결합니다. 외부 반복문: 압축을 진행할 단위 수를 조절해줍니다. 처음에는 1글자로 시작해서 문자열 s의 길이까지 확인해 줍니다. 내부 반복문: 문자열 내부에서 특정 문자열이 압축이 가능한 지를 확인합니다. 문자열에서 substring 함수는 문자열을 잘라주는 역할을 합니다. 즉 문자열 s에 대해 s.substring(0,3)과 같이 사용하면 index 0부터 2까지의 문자열을 잘라서 저장해줍니다. 예를 들면, String s = "hello"; ..

해당 문제는 스택을 이용하면 쉽게 해결할 수 있습니다. 입력으로부터 받은 s로부터 앞에서부터 한 글자씩 확인하며, 다음의 단계를 수행합니다. 1. 스택이 비어있다면, 해당 글자를 스택에 push한다. 2. 스택 최상단의 글자와 해당 글자가 같다면 스택을 pop 해준다. 3. 스택 최상단의 글자와 해당 글자가 다르다면, 스택에 push한다. 전체 문자열 s에 대해 위의 단계를 수행했다면, 정답을 도출해 낼 수 있게 됩니다. 만일 스택이 비어있다면, 모든 문자열이 제거된 것이므로 1을 리턴합니다. 반면, 스택에 하나의 글자라도 차있다면, 모든 문자열을 제거하지 못했으므로 0을 리턴합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2..