난이도 : Level 3유형 : 구현 / 시뮬레이션구현 시간 : 1시간링크: https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr       문제풀이위 문제는 2차원 배열에 대한 높은 이해도가 필요하다. 제한사항을 자세히 보면, Key와 Lock의 크기가 3에서 최대 20으로 작은 것을 보니 완전탐색을 이용해서 풀 수 있다. 나는 (Lock 배열 길이 + Key 배열의 길이 * 2)의 크기의 2차원 배열을 새로 선언하여, 정사각형의 중앙에 Lock 배열을 삽입하고, 모든 경우를 전부 탐색하도록 구..

난이도 : Level 2유형 : 문자열 / 구현구현 시간 : 1시간링크: https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr        문제풀이주어진 문자열을 1 ~ 문자열의 절반 길이까지 잘라가며 압축된 문자열의 길이를 비교한다.문자열을 자를 땐, 잘라진 앞부분(target) 을 설정하고 그 뒤로 남은 문자열을 자르며 비교한다.만약 target 과 다음으로 자른 문자열(compare)이 같다면 cnt 를 1 증가시키고, 다음 문자열로 넘어간다.target 과 compare 이 같지 않은 경우..

들어가며야구 직관 서비스 캐치미 프로젝트에서 실시간 채팅 서비스를 구현한 내용을 기록 및 복습의 목적으로 본 글을 포스팅합니다. 이번 포스팅에서는 소켓과 웹소켓, STOMP 프로토콜에 대한 개념, HTTP 통신과의 차이점을 알아보려고 합니다. 채팅에 관련된 채팅방, 채팅 데이터 테이블의 ERD 설계부터 실제 코드 구현, MongoDB로 마이그레이션을 통한 성능 개선까지 실제 프로젝트를 참여하며 겪었던 고민들에 대해 이야기해 보겠습니다.이미 웹소켓에 대한 기본 개념이 있으시다면 다음 글로 넘어가셔도 좋습니다. 😄    웹소켓(WebSocket) 이란 ❓서버와 클라이언트 간의 메시지를 교환하기 위한 통신 방법입니다. 일반적으로 서버와 클라이언트는 HTTP 통신을 통해 메시지를 주고받지만, 아래와 같은 웹..

난이도 : 골드 3유형 : 위상 정렬 / 동적 계획법링크 : https://www.acmicpc.net/problem/1005구현 시간 : 1시간 (못품)        문제풀이위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노..

난이도 : 골드 3유형 : 최단 경로 / 다익스트라링크 : https://www.acmicpc.net/problem/11779 구현 시간 : 30분    문제풀이해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다. 이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다. 핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 pr..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2156구현 시간 : 1시간     문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 9465번 스티커 문제와 같이 이전 선택에 따라 다음 선택이 제한된다.연속 세 잔의 포도주를 마실 수 없기 때문에 마지막 잔의 앞 잔, 앞앞 잔의 값이 크다면 마지막 잔을 마시지 않을 수도 있다는 점도 고려해야 한다. 따라서 N 번째 잔의 최대값을 구하려면 아래와 같은 경우를 고려해야 한다.N 번째 잔을 마시지 않는다. N 번째 잔을 마신다.N - 3 -> N - 1 -> N 번째 잔을 마신다.N - 2 -> N 번째 잔을 마신다. 위 경우를 고려해서 표현한 점화식은 아래와 같다.DP[i]..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/9465구현 시간 : 30분       문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 문제 해결의 핵심은 이전 선택에 따라 다음 선택이 제한된다는 점이다.특정 행의 스티커를 선택할 때, 바로 이전 행의 대각선 방향 스티커만 선택 가능하고, 따라서 N 번째 행의 스티커를 선택할 경우, 이전 선택 결과를 고려해야 최대값을 얻을 수 있다. 나는 이차원 배열을 선언하여 N번째 행의 스티커를 선택했을 때 최대값을 DP 테이블로 저장해서 구현하는 방식을 선택했다. 점화식은 아래와 같다.DP[i][0] = max(DP[i-1][1], DP[i-2][1]) + sticker[i][0]..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2193구현 시간 : 30분      문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였다. 이 문제를 해결하기 위해서는 이친수의 규칙을 파악해야 한다.이진수가 0으로 끝나는 수는 다음 자리 숫자일 때, 0과 1로 생성되고, 1로 끝나는 수는 0으로 생성된다. 예를 들면, 10010 이라는 이진수는 다음 6자리수에서 10010 + 0, 10010 + 1 로 생성된다.또한, 10001 이라는 이진수는 다음 6자리수에서 10001 + 0 으로 생성된다. 따라서 N 번째 자리수에서 0으로 끝나는 이친수와, 1로 끝나는 이친수의 점화식은 다음과 같..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/7569구현 시간 : 30분     문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였고, Top-Down 방식은 다른 분들의 코드를 참조하여 작성했다. 우선 위 문제를 풀기 위해서는 점화식을 정의해야한다. DP[i] 번째의 최대 점수를 구하기 위해서는 DP[i-2] (두 개의 계단 전의 최대 점수) 와 DP[i-3] + stair[i-1] (세 개의 계단 전의 최대 점수 + 직전 계단의 점수) 간의 최대 값과 stair[i] (i 번째 계단의 점수) 를 더하면 구할 수 있다. A(i) = max(A(i-2), A(i-3) + K(i-1))..

난이도 : Level 4유형 : BFS / 우선순위 큐구현 시간 : 1시간 20분 (못품)링크: https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr       문제풀이위 문제는 Summer/Winter Coding(2019) 기출 문제로 처음으로 풀어보는 레벨 4의 문제였다. 확실히 비슷한 BFS 문제인 경주로 건설보다는 어렵게 느껴졌다. 1시간동안 고민하며 구현한 결과 Node에 좌표 정보와 비용을 저장하고 우선순위 큐를 사용하여 BFS를 구현하는 것에는 성공했지만, 우선순위 큐에 추가할 No..