🔗 문제 링크 https://www.acmicpc.net/problem/5639 💬 문제 이진 탐색 트리의 전위 순회 결과가 주어졌을 때, 해당 트리의 후위 순회 결과를 출력하는 문제다. 🤔 접근 전위 순회 결과가 주어졌으니, 그걸 토대로 트리를 만들고 후위 순회를 하며 결과를 출력하면 되겠다! 라고 생각했다. 시간이 1초라서 조금 더 빠른 방법이 없나 생각해보다가, 문제에서 주어진 이진 탐색 트리의 특징을 자세히 보았다. 루트를 기준으로 왼쪽도, 오른쪽도 이진 검색 트리니까 두 서브트리를 재귀적으로 나눠 내려간 후, 마지막에 루트 노드를 출력하게 되면 그게 후위 순회 결과였다! 그림과 같이 루트를 기준으로 좌측 - 우측 순서로 서브트리를 탐색하고, 리프노드에 도달하면 출력한다. 그 결과는 트리의 후위 순회 결과와 같다. 순서는 다음과 같다. 입력을 배열에 저장한다. 배열의 첫 원소는 루트이다. 이후 인덱스부터 순회하며 루트보다 큰 값이 나오면 쪼갠다. 쪼개진 서브트리(왼쪽,…

🔗 문제 링크 https://www.acmicpc.net/problem/12851 💬 문제 🤔 접근 숨바꼭질과 비슷한 문제로, BFS를 통해 각 숫자에 도착하는 최소 시간을 계산하면 되는 것 같았다. 하지만 단순 최소 시간만 구하는 것이 아닌, 최소 시간으로 도달할 수 있는 경우의 수까지 추가로 구해줘야했다. 기존엔 visited 배열을 boolean으로 관리하여 true라면 큐에 추가하지 않는 방식을 사용했는데, 최소 시간으로 도달할 수 있는 여러 경우가 있을 수 있다보니 다른 방법 + 같은 최소 시간으로 특정 숫자에 도달하는 경우도 큐에 넣어 처리를 해줘야했다. 따라서 visited 배열을 -1로 초기화한 후, 도달하는 시간으로 덮어쓰자고 생각했다. ⚠️ 문제 처음 visited 처리 과정에서 시간 비교를 잘못하고 있었다. 로 처리하고 있었는데 일단 부등호 방향이 반대였고, 나는 visited 배열을 -1로 초기화했기 때문에 부등호 방향을 바꾸더라도 큐에 숫자가 들어가지 않고…

🔗 문제 링크 https://www.acmicpc.net/problem/2096 💬 문제 DP 문제인데, 최솟값과 최댓값을 둘 다 구해야하는 문제다. 🤔 접근 DP로 접근해서 접근 가능한 이전 줄 값들에 현재 줄 값을 더한다. 이후 최소, 최대값을 갱신하여 저장하는 방식으로 접근하고자 했다. ✏️ 해결 1. DP 배열로 풀기 처음엔 메모리 제한을 못 보고, minDP와 maxDP 배열을 만들어 풀어보고자 했다. 한 줄당 3개의 칸만 있어, 하나하나 계산하여 DP 배열을 갱신했다. 결과는 … 메모리 초과 !! 2. 배열 없이 변수 초기화해가며 풀기 배열의 크기가 너무 커서 메모리 초과가 났다고 생각했다. 따라서 값 별로 각각 변수를 만들고, 새로운 값을 덮었는 방식으로 접근해보았다. 이또한,,, 메모리 초과 !!!!! 3. 입력을 한 줄씩 처리하기 이전에 이중 우선순위 큐 문제 풀 때, input을 하나의 변수에 가지고 있는게 메모리 초과가 났던 기억이 났다. 그래서 한 줄씩 입력…

🔗 문제 링크 https://www.acmicpc.net/problem/7662 💬 문제 D 뒤의 값에 따라 최솟값을 pop하거나, 최댓값을 pop해야하는 문제이다. 🤔 접근 우선 힙을 써야한다는 것은 알겠는데, 우선순위가 두 개라서 어떻게 접근해야하나 고민했다. MaxHeap을 만들고, 최솟값을 pop해야할 땐 subtree끼리 비교하기 -> 구현 로직이 너무 어려워질 것 같았다. MaxHeap, MinHeap을 모두 두고, 부호에 따라 해당 힙에서 pop하기 + visited 배열로 삭제된 값 관리 -> 해당 방법이 좋을 것 같았다. ✏️ 해결 1. Heap 만들기 js로 우선순위 큐 문제를 풀 때의 가장 힘든 점 .. 내가 구현을 해야한다.(js를 선택한 죄) 이 또한 몇 번 만들다보니 이제 얼마 안걸리긴 한다. 문제 시작도 전에 200줄 가까이 되어버린 코드 2. visited 배열을 만들어 관리 MaxHeap에서 pop을 한 것은 MinHeap에서 알지 못한다. 나중에 M…

🔗 문제 링크 https://www.acmicpc.net/problem/2839 💬 문제 정수 n이 주어졌을 때, 해당 수를 3과 5로 묶을 수 있는 최소한의 묶음 수를 구하는 문제이다. 탐욕 알고리즘을 사용해야할 것 같다. 🤔 접근 탐욕 알고리즘 공부 중 마주한 문제라 당연히 해당 방법으로 푸는줄로만 알고 첫 접근을 이상하게 했다. 내가 알았던 탐욕 알고리즘(잘못됨) : 우선 제일 큰 것부터 이용해서 묶고 안되면 다시 돌아가서 해결하면 되는거 아니야? 이 잘못된 생각에 꽂혀 1시간동안 삽질했다.. ㅋㅋㅋ .. 쓰면서도 어이가 없고 지금 어지러울 정도임 너무 멘탈이 나갔다.. 사실 해결될 만도 한데 코드 짜면서도 뭔가 잘못됨이 계속 멤돌아서 해설 영상을 보았다. ✏️ 해결 바보같은 나 .. 해결방법은 다음과 같다. n이 0보다 크거나 같은 동안 계속 루프를 돈다. n을 3으로 빼며 묶음 개수를 증가시킨다. n이 0이거나 5로 나누어 떨어지면 5로 나누어 떨어지는 만큼 묶음 개수에 …

🔗 문제 링크 https://www.acmicpc.net/problem/1181 💬 문제 정렬을 이용하는 문제이다. node.js를 이용하여 풀 때는 sort메소드를 잘 알고 있다면 쉽게 풀 수 있다. 단어가 n개 주어지고, 단어의 길이대로 오름차순 정렬(1차), 단어의 길이가 같다면 사전순 정렬(2차) 해야한다. 여기에 추가된 조건으로 중복된 단어는 하나만 남기고 제거해야한다. ✏️ 해결 우선 입력받은 배열에서 중복된 단어를 먼저 제거하고 그 이후 정렬을 하는 것이 좋다고 생각했다. 중복을 허용하지 않는 js의 자료구조 중 집합(Set)이 생각났고, 배열 전체를 집합에 넣었다가 빼는(?) 방식으로 중복된 단어를 없앨 수 있을 것 같았다. 이후 arr를 조건에 따라 정렬해주면 된다. 정렬하기 전, JavaScript의 sort 함수에 대해 정리하고 넘어가자. sort함수 문자열의 경우 유니코드 순서로 정렬(따로 함수 넣어줄 필요 X) 숫자의 비교를 위해서는 정렬 함수를 추가로 작성…

코딩 테스트 준비를 위해 알고리즘을 기초부터 탄탄하게 공부하는 중이다. 제일 기초가 되는 정렬 알고리즘 중 선택, 버블, 삽입, 합병 정렬을 정리해보고자 한다. (with JavaScript) 선택 정렬(Selection Sort) 선택 정렬은 매 단계에서 가장 작은 원소를 선택하여 앞으로 보내는 정렬 방법으로, 한 번 제일 앞으로 보내진 원소는 더 이상 옮겨지지 않는다. 시간복잡도는 O(n^2)로 효율적이라고 볼 수는 없지만, 구현이 쉽기 때문에 라이브러리를 사용하지 못하는 상황 + 입력이 크지 않은 상황 이라면 빠르게 구현해서 사용하기 쉽다. 순서는 다음과 같다. 각 단계에서 원소를 순회하며 가장 작은 원소를 찾는다. 현재까지 처리되지 않은 원소(정렬된 원소 다음) 중 가장 앞의 원소와 자리를 교체한다. 모든 원소에 대해 반복한다. 아래 사진으로 이해해보자 1단계 : 배열을 모두 순회해서 가장 작은 원소 1을 제일 앞으로 보낸다. 2단계 : 1까지는 정렬이 완료되었으니 4(a…