문제 링크 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 어노테이션을 사용하여 엔티티 클래스의 필드에 인..
Test Environment 3인 유저 채팅방에서 채팅 추가 시, api의 속도를 확인하는 것으로 cache 적용 전 후 의 성능을 비교했습니다. 기본 전략 반복 읽기가 많은 데이터를 캐싱하였기에 lookl aside +write around 전략을 사용하고, 일관성 유지를 위해 데이터 수정 발생시 캐시 데이터를 버린 뒤, 이후 사용시 캐시를 다시 Hit시켜 캐시메모리에 변경사항을 로딩하는 방식을 사용했습니다. caching 적용 전 api 속도 sql 수행 횟수 기본적으로 chatroom, mem ber의 엔티티를 select하는 sql이 각각 수행되고, 해당 채팅을 db에 insert하는 명령어가 수행된다. 추가적으로, 캐싱을 적용하지 않았으므로 채팅 알림을 보내기 위해 채팅 방 내의 모든 멤버들의..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 dp[a][b]를 시작점에서 (a,b) 지점까지 도달하는 경로의 가짓수라고 가정하자. 시작점에 1을 넣고(제자리에 있는 것 ==1개의 경로) dfs or bfs로 완전탐색을 수행한다. ( 이때, 아래 or 오른쪽으로만 이동하기에, 왔던 길을 되돌아올 일은 없다.) 만약 a,b라는 지점에서 두개의 분기점이 만난다면, (a-1,b) 와 (a,b-1) 지점이 만나게 된다. (아래 ..
