문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 최대한 중복이 많이 발생하는 구간마다 카메라를 설치해나가면 된다. 시작 시간, 종료시간이 작은 순서로 정렬한 뒤, 현재 route와 다음 route 사이에 중복 구간이 존재하는지 확인한다. 만약 존재한다면, 현재 구간과 새롭게 편입한 route의 중복 구간을 구한 뒤, 다음 route를 통해 또다시 중복구간이 형성되는지 확인한다. 최대한 많은 자동차가 겹칠 수 있는 중복기간..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42885# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 어렵게 생각할 필요 없다. 가장 무게가 많이 나가는 사람 ( == 가장 제한된 합승 조건을 가진 사람) 부터 최대한 사람을 많이탑승 시키면 정답이 나온다. 이를 구현하기 위해 Sort를 진행한 뒤, back에서부터(가장 높은 무게의 사람) 최대한 많은 사람과 합습 시키기위해 가장 무게가 적게 나가는 순서대로 합승 시킨다.( Sort 했기에 역시 Front 부터 쭉) 정답 코..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보고 플로이드 와샬이 떠올랐다. A >B 이고, B> C 라면 A>C라는 것은 곧, A 가 1 다리만 걸친다면 B만 이기는 것이지만, 'B' 를 거치면 C 를 이기는 경우의 수를 찾을 수 있기 때문이다. 따라서, i 번 사람이 j 번 사람과 붙어서 이기는가? 에 대해서 아래와 같이 규정하였다. dp[i][j] 1: i가 j에게 이긴다 0: i와 j의 승패는 모른다 -..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12952# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 이 문제는 dfs를 통한 완전탐색 과정에서, 백트래킹으로, 불가능한 트리의 가지를 가지치기 하여 수행 시간을 감소시켜야만 시간초과가 발생하지 않는다. 나는 이를 위해, 퀸이 8방향 모든 칸으로 이동하는 특성 중 좌, 우 모두 이동 가능한 특성을 활용하여 각 dfs(depth) 에서, depth 번째 행에 퀸을 놓을 수 있는 위치를 찾는 것으로 문제를 해결했다. 퀸을 놓을 행은..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 이 문제는 " 전체를 연결하는 최소 비용" 에서 MST문제임을 캐치할 수 있다. MST란? union-find 알고리즘을 통해 트리로 구성하여 새롭게 그룹에 참여하는 간선을 비용이 낮은 순으로 Union 해서 최소 비용을 찾는 문제이다. N개의 Vertex가 있다면, N-1 개의 간선을 병합하여 전체를 1개의 그룹으로 만들 수 있다. 정답 코드 #include #includ..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 최대 1000000 자리 수 이므로, 모든 가능성을 Combination 구현을 통해 탐색하는 '완전 탐색' 알고리즘을 통해 최대 값을 찾을 시, 시간 초과가 발생한다. 여기서, 1가지 규칙을 찾아 greedy로 문제를 해결할 수 있다. 바로 대소 비교의 특성이다. 9111>8999 아무리 다른 자리의 숫자가 커도, 맨 앞자리가 큰 것이 무..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 dfs의 특성을 활용하여 사전순으로 완전 탐색을 진행할 수 있다. 따라서, 탐색 순서에 따라 진행하던 중, 찾고자하는 string이 나오면 해당 string의 순서를 리턴하면 된다. dfs를 통한 사전순 완전탐색으로 순서 계산 #include #include #include using namespace std; string words="AEIOU"; string ans_str..
이번 글에선, 백엔드 개발자로써, 최적화를 수행하기 위해 수행, 고려할 수 있는 것들을 몇가지 정리해보겠다. 캐시 사용하기 반복적으로 실행되는 쿼리 결과를 캐시하여 DB에 쿼리를 보내는 횟수를 줄일 수 있다. Spring Boot에서는 캐시 관련 어노테이션을 사용하여 쉽게 캐시를 적용할 수 있다. 예를 들어 @Cacheable 어노테이션은 메서드의 반환값을 캐시에 저장하고, 이후 동일한 메서드를 호출할 때 캐시된 값을 반환한다. 인덱스 추가하기 쿼리 성능을 높이기 위해 인덱스를 추가할 수 있다. 인덱스는 특정 컬럼을 대상으로 빠른 검색을 가능하게 한다. Spring Boot에서는 JPA 어노테이션을 사용하여 인덱스를 추가할 수 있다. 예를 들어 @Index 어노테이션을 사용하여 엔티티 클래스의 필드에 인..
