오늘은 유명한 유형 중 하나인 LIS 유형에 대해 정리해보고자 한다. 해당 유형을 안 지 얼마 되지 않았지만, 유형이 어느정도 정형화 되어있는 느낌이다. 해당 유형을 풀이하는 방법은 DP, 이분탐색 2가지가 있다. DP로 풀이할 경우 O(N^2)의 시간복잡도를, 이분탐색으로 풀이할 경우 O(NlogN)의 시간복잡도를 가진다. 따라서 문제에 나와있는 조건을 잘 보고 시간복잡도를 따져서 알고리즘을 선택하는 것이 중요하다. 해당 유형은 가장 긴 증가하는 부분 수열의 길이까지만 구하거나, 더 나아가 부분 수열 자체를 출력해야하는 문제들이 있다. 해당 유형은 1,2편으로 나누어 작성하고자 하며, 해당 글(1편)에서는 가장 긴 증가하는 부분 수열의 길이까지만 구하는 문제를 다뤄보고자 한다. 우선 백준 12015번 ..
이번 글은 삼성 코테 기출 문제인 19238번 문제를 복기하면서 쓰는 글이다.https://www.acmicpc.net/problem/19238 해당 문제는 문제설명에서도 나와있듯이, 택시가 승객이 위치한 곳으로 이동해야하며 이때 택시의 위치에서 가장 가까운 위치에 있는, 즉 최단경로에 있는 승객을 태우러 가기 때문에 BFS 알고리즘을 떠올려야 했다. + 조건을 잘 따져가면서 풀어야 하는게 중요했다. 해당 문제는 눈높이 개발에서 진행하는 코딩테스트 챌린지를 진행하면서 푼 문제인데, 여기서 힌트를 주신게 메모리 초과가 나지않게 점검해보라고 하셨던 거였다! 그래서 처음에 딱 생각이 났던게, 택시와 승객의 최단 경로 길이를 구해야하는데 이걸 승객마다 BFS를 돌리기에는 시간초과가 뜰 것 같다는 생각이 들었다..
백준(BEAKJOON) | 알고리즘 분류 이진탐색 #2110번 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 | 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 ..
UMC 프로젝트를 하다가 이 오류를 발견했다. 해결방법) Preferences > Gradle 에서 Build and run using 과 Run tests using을 다음과 같이 바꾸고, Run tests using도 바꿨다. 그리고 gradle 저 새로고침 버튼을 눌렀다! 참고) https://pika-chu.tistory.com/88
프로그래머스(programmers) | 2020 KAKAO BLIND RECRUITMENT #문자열 압축 https://school.programmers.co.kr/learn/courses/57/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문..
백준(BEAKJOON) | 알고리즘 분류 DFS #2606번 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 | 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과..
*이것이 취업을 위한 코딩테스트다 with 파이썬 교재를 공부한 내용을 바탕으로 작성했습니다. DFS (Depth-First Search) : 깊이 우선 탐색, 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하며 스택 자료 구조 이용, 재귀호출 알고리즘도 같이 많이 사용한다! 모든 노드를 방문하고자 할 때 BFS (Breadth-First Search) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘이며 큐(선입선출)를 이용한다. 두 노드 사이의 최단 경로 ex) 최단거리 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 ..
*이것이 취업을 위한 코딩테스트다 with 파이썬 교재를 공부한 내용을 바탕으로 작성했습니다. 그리디 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘, '최적의 해' 찾기 문제. 대표문제) 거스름돈, 1이 될 때까지 만들 수 없는 금액 1. 문제 N개의 동전이 주어질 때, 이 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오. 2. 입력 예시 5 3 2 1 1 9 3. 출력 예시 8 - 이 문제는 그냥 처음부터 접근하는 게 어려웠다.. 생각할수록 계속 어려운 알고리즘 밖에 생각나지 않아서 결국 해답을 봤다.. 답을 봤는데도 잘 이해되지 않는 문제였다. 우선 만들 수 없는 최솟값을 구해야 하므로 리스트를 정렬한다. 해답에서는 target을 이 금액을 만들 수 있는..
