L.O.K

11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net ◎ 문제 풀이 산다 2) 판다 3) 아무것도 안한다. 3가지 경우가 있고 목표하는 n 날에 최대이익을 구하는 문제이니, 처음에는 DP를 발상하였다. 그러나 DP로 풀기에는 한계가 있었다. 주식을 하나 팔 수도, 두 개 팔 수도 있었다. DP로 이런 복잡한 경우의 수까지 고려할 수 없었다. 주식은 가장 쌀 때 사서 비쌀때 파는 것이다. 그러므로 그리디 알고리즘이 적합하다. 매일 주가를 기준으로 향후 가장 비싼 주가인 날에 팔면 된다. 주가를 내림차순으로..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 상자 안에는 다음 오픈할 상자의 번호가 적혀있는 카드가 들어있다. 임의의 한 상자를 오픈하여 연달아 오픈해서 이미 오픈한 상자를 만날 때까지 오픈한다고 했을 때, 연달아 오픈할 수 있는 상자의 개수가 가장 많은 것과 그 다음 많은 것의 곱을 구하는 문제이다. 문제가 복잡해보이지만 싸이클을 찾는 문제이다. 방향그래프에서 싸이클을 찾는 문제는 DFS 알고리즘을 사용하면 된다. DFS 알고리즘으로 가장 큰 싸이클과 그 다음 싸이클을 찾아서 싸이클 안의 상자수를 곱하면 된다. 주의할 점은 입력으로 주어진..

17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net ◎ 문제풀이 진우가 지구에서 달까지 높이마다 정해진 방향으로 이동할 때, 비용의 최솟값을 구하는 문제이다. 처음에는 높이마다 정해진 방향으로 이동하므로, 계층에 따른 모든 경우의 수를 완전탐색하는 DFS 알고리즘을 떠올렸다. 그러다가 문제가 탐색(재귀호출)으로 어떤 조합을 찾기보다는 최적해를 구하는 문제이므로, 메모리제이션을 활용한 DP 풀이가 더 적합하다는 생각으로 바뀌었다. 이동에는 3가지 경우가 있다. 1) 좌측 아래로 대각선..

1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net ◎ 문제풀이 1부터 N까지 공백없이 이어붙인 수열에서 임의로 몇 개의 수가 제거되었을 때, 제거된 수열만보고 N의 최솟값을 알아내는 문제이다. 수열의 좌측의 수부터 하나씩 그 수를 포함하는 수의 최솟값을 구하면된다. 134211 이 임의로 제거된 수열이라고 해보자. 가장 좌측인 1을 포함하는 수의 최솟값은 1이다. 그 다음 3을 포함하는 수의 최솟값은 3이다. 그 다음 5를 포함하는 수의 최솟값은 5이다. 그 다음 2를 포함하는 수의 최솟값은 2이다. 그 다음..

20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net ◎ 문제풀이 우선순위로 주어진 3가지 조건에 부합하도록 단어를 나열하는 문제이다. 우선순위가 한 가지가 아니라 3가지를 한번에 고려하여 정렬을 해야하므로 우선순위큐를 발상하였다. 또한 가장 높은 우선순위 조건이 가장 자주 나오는 단어이므로, 동일한 단어가 등장할 때마다 O(1) 시간복잡도로 카운트할 수 있도록 해시맵을 이용하였다. ◎ 코드 import java.io.*; import java.ut..

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net ◎ 문제풀이 2차원 배열에 존재하는 치킨집들에서 M개의 경우를 선택하여 그중 치킨거리가 최소인 거리를 구하는 것이다. N개중 M개를 뽑는 모든 경우를 탐색하는 가장 좋은 방법은 재귀호출을 이용하는 것이다. 재귀호출을 이용하여 가장 적합한 경우를 구하는 문제는 백트래킹(BackTracking)을 활용하면 좋다. 백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 ..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net ◎ 문제풀이 문제요약 : 2차원 배열에서 아기상어가 상하좌우로 이동하여 가장 가까운(가장 우선순위가 높은) 먹이를 먹을 때, 먹이를 더이상 먹지 못하고 엄마상어를 부를 때까지 걸리는 시간을 구하라. 문제풀이 : 상하좌우로 이동하며 가장 가까운 먹이를 찾는다는 점에서 최단거리를 구하는 BFS를 떠올렸다. BFS까지는 떠올렸으나 일반적인 BFS 코드로는 먹이를 먹는 우선순위를 적용하기 힘들었다. 일반큐가 아닌 우선순위큐를 사용하여 조건에 맞는 가장 가까운 먹이..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ◎ 문제풀이 문제요약 : 학생들이 원하는 팀원 정보가 그래프로 주어질 때, 싸이클을 형성하면 팀으로 구성된다. 싸이클을 형성하지 못하는 팀원의 수를 구하라. 문제풀이 : - 방향그래프에서 싸이클을 찾는 문제이므로 DFS를 발상하였다.( 무방향 그래프에서 싸이클을 찾는 문제는 UNION-FIND 알고리즘 사용 ) - 방문여부 배열과 싸이클 여부 배열로 DFS 로직을 구성하였다. - 탐색과정에서 이미 방문한 노드를 다시 접근하면 싸이클이 형성된다. - 싸이클 여부가 결정..

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net ◎ 문제풀이 2차원 배열로 치킨집과 집의 위치가 좌표로 주어질 때, 집과 치킨집의 거리의 총합이 최소인 치킨집 M개를 선별하고, 치킨집 M개와 집 사이 거리의 총합이 최소일 때의 거리를 구하는 문제이다. 치킨집도 최대 13개이니 무식하게 푸는 것이 좋겠다고 생각했다. 1) 치킨집 M개 조합을 모든 경우를 완전탐색한다. ( DFS ) 2) 모든 경우의 조합과 집 사이의 치킨거리를 구한 뒤, 가장 최소인 치킨거리를 출력한다. N개 중이 M개의 조..

18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net ◎ 문제풀이 땅을 평탄화 하는데 최소시간이 걸리는 높이와 시간을 구하는 문제이다. 요구하는 조건이 많아 처음에는 막막했지만 다시 생각해보니 쉬운 문제였다. 최고높이와 최저높이의 사이 높이 하나하나의 평탄화 시간을 구한 다음 비교하여 최소시간과 높이를 구하면 되었다. 높이도 최대 256이고 가로세로 최대 500x500이니 삼중for문을 만들어도 최대 64만번 연산한다. 그러므로 시간복잡도에 걸리지 않는다. ◎ 코드 import java.io.*; import ja..