DP 문제를 풀다보니 자주 등장하는 유형이 있어 구글링을 해보니 '최장 증가 부분 수열'이라는 유형이였다. # 최장 증가 부분 수열 (Longest Increasing Subsequence) DP 문제로 자주 나오는 유형 O(N^2)의 시간 복잡도 아니면 O(NlogN)의 시간 복잡도를 가진다. 어려운 문제의 경우 당연히 후자.. 개념 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 '오름 차순을 유지하면 증가하는 부분 수열' 즉, 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열이 LIS 위의 여러 수열 중 가장 길이가 긴 수열은 [2,3,5,6,7] 뿐만 아니라 [1..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net # 조건 - 트리에서 리프노드란, 자식의 개수가 0인 노드 - 트리가 주어질 때, 노드 하나를 지울 것인데, 그 때 남은 트리에서 리프 노드의 개수를 구하여라 # 접근 방법 - 노드 하나를 지웠다면 아래 자식 노드들 또한 함께 지워지는 것이 규칙 - 따라서 지워지는 노드 기준, 아래로 연결되어 있는 노드들을 -2로 변경해준다. - -2인 경우는 나올 수 없는 수 이기도 하며 False로 설정..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net # 조건 - 토마토를 보관하는 창고가 있는데 익힌 토마토는 1, 비어있는 경우 -1, 그냥 토마토는 0으로 표시 - 익힌 토마토의 좌우상하 토마토는 다음날 익어있다. - 이 때, 모든 토마토를 다 익히는 경우, 최소 일 수를 구하여라 - 만약, 익히지 못한다면 -1 출력 # 접근 방법 - 좌우상하 탐색이 필요하므로 델타 함수를 이용하여 접근해준다. - 또한 바로 내 주변에 토마토가..

https://www.acmicpc.net/problem/1325 B 컴퓨터를 신뢰하는 관계라면, B 컴퓨터만 해킹하여도 A는 자동으로 해킹된다. 이 때, 한 컴퓨터를 해킹해서 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 출력하여라! 여러 대가 있다면, 오름차순 출력 # 접근 방법 자식 노드만 확인하는 것이 아닌 그 컴퓨터를 '신뢰하는' 또 다른 컴퓨터까지 확인해 주어야한다. 따라서 BFS를 확인하여 각 컴퓨터마다 해킹가능한 컴퓨터 수를 기록해주고 가장 많이 해킹하는 컴퓨터를 출력한다. BFS 기본 예제 문제와 비슷해보이지만, 1번이 아닌 모든 컴퓨터를 체킹한다는 것이 다르다. 그러다보니 많은 메모리, 시간을 사용하게 되고 PyPy로 제출하지 않는 이상 통과가 힘들었다.. ```python # N개..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 프로그래밍을 하며 '재귀'를 접하게 되면 가장 먼저 만나게 되는 문제라고 볼 수 있다. 그만큼 유명하고 재귀를 가장 잘 표현하였다고 생각이 드는 것이 '하노이의 탑'이라고 볼 수 있다. # 조건 세 개의 장대가 있고 첫 번째 장대에는 서로 크기가 다른 N개의 원판이 쌓여있다. 한 번에 한 개의 원판만 이동 가능하며 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. # 접근..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ## 조건 - 캠프 때 쓸 N개의 랜선을 만들어야 한다. - 이미 자체적으로 가지고 있는 K개의 랜선을 이용하여 N개 이상의 랜선을 만든다. - 항상 센티미터 단위로 정수 길이만큼 자르며, 만들 수 없는 경우는 없다. - 최대 랜선 길이를 구하여라 ## 접근방법 - 처음에는 평균값을 구한 후, -1씩 해주면서 주어진 개수를 만족시키는 값을 구하려고 하였지만 시간초과! ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LsaaqDzYDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 접근 방법 우선 제일 처음 빵이 만들어지기 전에 손님이 방문한다면 "Impossible" 출력과 동시에 끝내주었다. 또한 빵을 받아가는 사람 수가 처음 만든 빵의 개수보다 적다면 위의 조건 이후에 elif 조건문을 이용하여 "Possible" 출력을 해주며 끝내주었다. 이제 나머지 조건에 맞추어서 답을 내주면 되는데, 방문하는 사람을 "시간 초"로 표현하였기에 "시간"에 관점을 두고 풀이를 하였..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 접근 방법 제일 큰 행렬 속 작은 행렬들을 찾는 문제였다. 작은 행렬들을 찾아 개수와, 넓이 순으로 행과 열의 좌표를 출력하면 된다. 작은 행렬의 시작점과 끝점의 인덱스를 기록해주며 2중 for문으로 구현해보려 하였지만 쉽지 않았다. 역시나 이런 행렬 관련 문제는 델타 탐색과 4중 for문으로 먼저 접근하는 것이 빠르다는 것을 느낄 수 있었다. 또한, swea 등 제출 시 제출형식을 잘 맞춰야 ..

https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 접근 방법 주어진 조건에 맞게 함수를 완성시켜야한다. 같은 인형이 바구니에 들어온다면 터트려 주고 총 터진 인형의 수를 반환 해주는 문제이다. 2중 리스트이므로 전치행렬을 이용하여 구할수도 있지만, 나는 반복문 내에서 행과 열의 인덱스 번호를 반대로 적어주며 풀었다. 스택을 이용하여 LIFO 구조로 제일 위에 인형만 비교해주고 출고 시켜주었다. # 0은 빈칸 # 1~100은 각기 다른 인형 #..