1. 문제 설명문제 링크뭔놈의 극장이 티켓을 샀는데, 양 옆으로 옮겨 앉을 수 있음...예를 들어 3번 좌석을 산 사람은 4번 좌석에 앉아도 되고, 2번 좌석에 앉아도 됨.하지만 3번 좌석을 산 사람이 양 옆 이외의 좌석에는 못 앉음. 예를 들어 7번 좌석이나 1번 좌석으로 이동은 불가.또, VIP석이라는 개념이 있음. 이름이랑 맞지 않게 이거 산 사람은 그냥 그 자리 앉아야함.예를 들어 7번 좌석이 VIP석이면 7번 산 사람은 7번에 무조건 앉아야함.N번까지의 좌석이 있고, 만석일 때, 사람들끼리 자리를 바꿔 앉을 수 있는 경우의 수를 구하라.2. 접근 방식도저히 못 풀겠어서 다른 사람 풀이를 봤다.KEY WORD : DP(1) 기본 원리패턴이 안 보이면, 무작정 가짓수를 적어서 패턴을 생각해봐야 한다..

1. 문제 설명문제 링크숫자의 자릿수가 주어질 때, 해당 자릿수를 가지고 만들 수 있는 오르막수의 개수를 구하라.오르막수?숫자의 가장 왼쪽부터 시작해 오른쪽으로 갈수록 자릿수의 크기가 작아지지 않는 수를 오르막수라고 한다. 다시 말해,1234, 2569 등이 오르막수이다.작아지지 않으면 된다고 하였으므로,1111, 1119도 오르막수가 된다.2. 접근 방식KEYWORD: DP자릿수가 1000의 자리까지 주어진다. 중복 순열로 문제를 푼다면, O(1000!) 이니까, 당연히 문제를 풀지 못한다. 따라서 해당 문제는 DP를 사용해야 한다.그렇다면, DP는 어떻게 생각해야 할까?2차원 배열로 DP를 만들어보겠다. 세로는 자릿수, 가로는 맨왼쪽의 숫자가 무엇으로 시작하는지 나타내는 것이다. 01234567891..

1. 문제 설명문제 링크(1) 1~N번까지의 집이 있음. 이 집들을 빨강, 초록, 파랑으로 색칠하려고 함.(2) 집은 인접한 번호와 색깔이 달라야 함.예를 들어 1번 집은 2번집과 색깔이 달라야 함. i번 집은 i-1번 집과 i+1번 집과 색깔이 달라야 함.(3) 각 집을 빨강, 초록,파랑으로 칠했을 때의 비용이 주어질 때, 조건에 맞도록 칠한 최소 비용을 구하라.2. 접근 방식KEY WORD: DP해당 문제는 생각할 것이 많이 없는 DP 문제이다.N행 3열의 DP 배열을 만든다. 0행은 빨강, 1행은 초록, 3행은 파랑에 해당하는 행이다. 그렇다면 각 배열의 원소는 무엇을 뜻할까?만약 dp[i] [2] 라면 i번째 집을 초록으로 칠했을 때의 최소 비용 이다.dp[3] [0] 은 3번째 집을 빨강으로 칠..

1. 문제 설명문제링크2차원 배열의 값을 집어넣고, 그것을 1차원 배열로 늘어뜨려서, 문제에서 원하는 구간 내의 숫자들을 묶어서 반환하는 문제이다.2. 접근 방식KEY WORD: Brute Force, 1차원 배열과 2차원 배열의 위치 관계해당 문제는 n의 maximum이 10^7이므로, O(n)을 초과하는 시간 복잡도를 사용하지 못한다. 따라서 2차원 배열에 값을 다 집어넣고, 그것을 1차원으로 만드는, 마치 문제에서 지시한대로는 풀이를 하지 못한다. 또한 1차원 배열을 바로 만들더라도, n*n은 배열의 메모리를 초과하는 값을 초래할 수 있기 때문에 1차원 배열 전체를 만드는 것도 무리다.따라서 우리는 정확히 left ~ right 까지의 배열을 만들어 값을 구해 반환해야 한다.(1) 1차원 배열 2..

1. 문제 설명문제 링크(1) 회전 시킬 부분 행렬의 좌상단, 우하단의 List가 주어진다.(2) List의 값마다 행렬을 시계 방향으로 회전시킨다.(3) 회전할 때, 움직였던 값 중 가장 작은 값들을 모아서 반환한다.2. 접근 방식KEY WORD: BRUTE FORCE, 배열 회전배열 회전은 브루트 포스 문제를 풀 때 단골로 나온다. 코딩 테스트에서도 배열 회전이라는 키워드가 단독으로 문제에 나오지 않지만, 문제의 조연으로는 자주 등장했던 것 같다. 그래서 회전하는 법에 대해 알아두는 것은 중요하다.문제에서, 회전하는 모습을 친절하게 예시로 알려준다.14 -> 8의 자리로, 8이 9의 자리로 시계 방향으로 움직이고 있음을 볼 수 있다.그렇다면 구현을 할 때는 어떻게 해야할까? 구현할 때는 반 시계 방향..

1. 문제 설명문제 링크서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다. 2. 접근 방식인접 리스트 형태로, 노드와 연결 정보를 저장한다. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int n, int[][] computers) { ..

1. 문제 설명문제 링크(1) 일거리의 시작 시간, 끝 시간, 일을 끝냈을 때의 이익 이 주어진다.(2) 시작 시간과 끝 시간의 범위가 겹치는 일은 같이 하지 못한다. 반면 어떤 일이 끝나자마자 다른 일은 시작할 수 있다.예를 들어, job A의 끝 시간이 3시 이고 job B의 시작시간이 3시이면 두 일 거리는 연달아 할 수 있다. 반면 job C가 3~5시이고 job D가 4~6시이면 두 일은 일의 시간 범위가 겹치므로 같이하지 못한다.(3) 이때, 겹치지 않게 일을 해서, 최대 이익을 얻으려고 한다. 주어진 일거리들 중에서 가질 수 있는 최대 이익은 몇인가?2. 접근 방식KEY WORD: DP(1) 주어진 문제가 시작시간, 끝시간, 이익을 따로 따로 주기에 이를 하나의 일(job) 단위로 하나로 묶..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: DATA STRUCTURE(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.(1) value (2) stack의 top과 now를 비교한다.(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)(4) top == now 이면 stack에서 pop해서 값을 뺀다.Stack은 진짜 sta..