전체 글

문제 링크: https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 DP 문제였다. 그것도 3차원 배열을 사용하는...🥹 DP 문제에서는 저장해야 할 상태가 하나 늘어날 때마다 배열 차원이 늘어난다. 예를 들어, RGB 거리에서는 이전 집에 칠한 색을 저장해야 했으므로, 2차원 배열을 이용했다. 이 문제에서는 왼발의 위치와 오른발의 위치를 저장해야 한다. 왼발과 오른발이 어디에 있었느냐에 따라 현재 스텝을 밟는 ..

문제 링크: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 문제 내용과 구현 자체는 그리 어렵지 않지만, 시간 제한이 빡빡한 문제였다. 그래서 어떤 자료구조를 선택할지 많이 고민했다. 문제에서 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 고 했으므로, 나이가 어린 나무부터 순회해야 한다. 하지만 매년 나무를 나이 순으로 정렬하면 시간 초과가 날 것 같았기 때문에, 최초 1번만 정렬한 뒤에 ..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 8번, 18번 테스트케이스에서 자꾸 틀려서 고생했다🥲 풀이 평균 대기 시간을 최소화하는 문제였다. 스케줄링 알고리즘을 기억하는 사람이라면 단번에 SJF(Shortest Job First) 알고리즘이라는 걸 알아챌 수 있다. (증명은 이 포스팅에서 다룰 문제가 아니므로 생략한다.) 현재 작업 큐에 들어온 일 중에 실행시간이 가장 짧은 일을 선택해야 하므로, 우선순위 큐를 이용하면 쉽게 풀 수 있다. 💡SJF(Shortest Job First)란? 작업 소요시간이 짧은 일부터 처리하는 스케줄링 알고리즘..