https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr해결방법사용한 알고리즘: 구현접근 방법:배달과 수거 위치를 가리키는 두 개의 포인터를 두어서 풀이하였습니다. idx1(배달), idx2(수거)만약 i번째에 배달할 물건이 있거나 수거할 물건이 있다면 i 만큼 이동해야 합니다. 1. idx1에 배달을 하고, idx1에 배달할 물건이 더 이상 없다면 idx1을 1 감소 시킵니다.2. 마찬가지로 idx2에 수거를 하고, idx2에 수거할 물건이 더 이상 ..
https://school.programmers.co.kr/learn/courses/30/lessons/258707해결방법사용한 알고리즘: 그리디, 구현접근 방법:현재 들고 있는 카드를 관리할 Set과 뽑은 카드를 관리할 Set을 사용합니다.3가지 경우를 순서대로 확인합니다. 오래 라운드를 진행할 수 있는 유리한 순서입니다.1. 코인을 쓰지 않고 n+1을 만족하는 카드가 2장 존재하는 경우 (카드를 안뽑아도 되는 경우)2. 코인을 하나만 쓰고 n+1을 만족하는 경우 (카드를 1장만 뽑아도 되는 경우)3. 코인 두 개를 써야 n+1을 만족하는 경우 (카드를 2장 뽑아야 하는 경우)3가지 모두 만족하지 않을 경우, 라운드는 종료됩니다.이렇게 구현하면 coin의 개수 또는 card 뭉치의 길이에 시간 복잡도가..
https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr해결방법사용한 알고리즘: 그리디, 투포인터접근 방법:queue1의 합을 sum1, queue2의 합을 sum2라고 했을 때, sum1과 sum2는 다음과 같이 greedy하게 풀 수 있습니다.sum1 > sum2 이면, queue1의 원소를 queue2에 넘겨줍니다.sum2 이 방식이 통하는 이유는 다음과 같습니다.sum1 > sum2인 상황에서 sum1을 증가시키고 R을 감..
https://www.acmicpc.net/problem/14002해결 방법사용한 알고리즘: DP접근 방법:테이블 정의: d[i]: 첫 시작 원소부터 i번째 원소까지 고려했을 때, 가장 긴 증가하는 수열의 길이점화식:i번째 원소를 포함하지 않을 경우: d[i] = d[i-1]i번째 원소를 포함하는 경우(if 조건을 만족할 경우): for j if(aj d[i] = d[j]+1i번째 원소를 포함할 경우, i보다 작은 j에 대해 가장 긴 증가하는 수열의 길이 + 1을 하여 현재 i번째 가장 긴 증가하는 수열의 길이(d[i])와 비교하여 최대값으로 업데이트 한다.추가적으로 길이뿐만 아니라, 가장 긴 증가하는 부분 수열을 출력해야 한다. 이를 위해 역추적 배열을 썼다.for j if(aj 이 과정에서 if..
https://www.acmicpc.net/problem/3108해결 방법사용한 알고리즘: 유니온 파인드 + 구현접근 방법:모든 직사각형 중 2개를 뽑는 조합을 구해서, 서로 교점이 있으면 union모두 확인한 후, 유일한 부모의 수 세기. (분리 집합의 수 세기)문제를 보고 제 생각의 흐름은 다음과 같습니다.두 직사각형이 연결되어 있는가? => 공유하는 점이 있는가? => 공유하는 점이 존재하면 하나의 집합에 포함 => union-find?두 직사각형이 만나는지 어떻게 판단? => 고려할게 많음.. => 만나지 않는 조건을 구하자코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
풀이그래프 문제로 저는 풀이 방법이 잘 떠오르지 않아서 어려웠습니다.처음 생각한 풀이로는 "집과 회사 각각을 시작점으로 완전 탐색을 진행하고, 겹치게 방문한 노드의 수를 세면 되겠다"라고 생각했습니다.정리하면 다음과 같습니다.visA: S -> T 과정에서 방문한 노드 표시visB: T -> S 과정에서 방문한 노드 표시visA ∩ visB를 만족하는 개수 = ans (오답) 문제의 조건에 출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다. 이 조건을 만족하지 못해서 틀렸습니다. DFS로 완전 탐색을 진행하였는데, 노드를 방문한 뒤 방문 체크를 하므로, S에서 출발 했다면 다시 S로 돌아올 수 없습니다. (예를 들면 문제 예시 1에서 1->4->1->2->3이 가능..
[Softeer] 7회 기출 순서대로 방문하기 Java
풀이문제를 제대로 안읽어서 순서대로 방문하기 문제인데, 순서대로 방문하지 않고 풀어서 틀렸습니다.. 처음 생각했을 때는 n=4이므로 전체 가능한 칸의 수는 16이 되고, DFS로 백트래킹 할 경우, 맥시멈 4 * 3^15 재귀 호출되고, 각 재귀 호출에서 4방향 탐색을 위해 for문을 도니까 4 * 3^15 * 4 ~= 2.3억이 나와서 시간 안에 부족하지 않나 생각했습니다. n이 작아서 예시를 들어서 해보니, 대부분 각 칸에서 다음으로 진행 가능한 경우가 3가지가 되지 않고 pruning 되어서 통과 될 것이라 판단하였습니다. 또 BFS로 풀이한다면, 풀이가 조금 더 복잡해질 것이라고 판단했습니다. 현재까지 이동한 경로에 따라, 다음 이동 할 수 있는 칸이 달라지기 때문입니다. 위 부분을 유의하여 순서..
[Street Coding Fighter] Kafka를 도입한 이유
랭킹 서비스를 설계하면서.. 게임이 끝나면 발생하는 프로세스를 추적해보았습니다. 게임이 종료될 때마다 게임 서비스(멀티 모드, 배틀 모드)에서 참여한 모든 유저에 대한 게임 결과를 유저 서버에 전송한다.유저 서버가 게임 결과를 받아서 경험치를 업데이트 한다.유저 서버에서 게임 결과를 통해 경험치를 업데이트하고, 랭킹 서버로 업데이트한 경험치를 보낸다.저희가 걱정한 부분은 게임 기록에 대한 손실이었습니다. 만약 유저 서버가 일시적으로 다운되거나 응답이 늦어질 경우 게임 기록이 손실될 위험이 있다고 판단하였습니다.유저 입장에서 게임 기록이 손실되는 일은 있어서는 안된다고 생각했습니다. 따라서 저희는 메시지 큐를 도입하여 이 문제를 해결하고자 하였습니다. 메시지큐 중에서 RabbitMQ와 Kafka를 비교하고..