✔ 정수 삼각형 [프로그래머스 43105] 문제 분석하기 사용할 수 있는 3가지 연산 점화식으로 구현 (맨 왼쪽, 중간, 맨 오른쪽) 예) 7 + 3 + 8 + 7 + 5 = 30 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i][j]은 i번째 줄의 j번째까지 거쳐간 숫자의 합이 가장 큰 경우 점화식을 구함 D[0][0] = triangle[0][0] 맨 왼쪽은 대각선 한 방향만 가능하므로 이전 합 + 자신의 수 = D[i][0] = D[i - 1][0] + triangle[i][0] 중간은 대각선 두 방향이 가능하므로 이전 합 + 자신의 수 = D[i][j] = Math.max(D[i - 1][j - 1] , D[i - 1][j]) + triangle[i][j] 맨 오른쪽은 대각선 한 방향만 가능하..
✔ 조이스틱 [프로그래머스 42860] 문제 분석하기 알파벳을 변경할 때 다음 알파벳으로 이동하는 것을 반복해서 완성할지, 이전 알파벳으로 이동하는 것을 반복해서 완성할지 비교 (다음 알파벳, 이전 알파벳 조이스틱 조작 횟수) 또한 위치를 변경할 때도 왼쪽으로 이동하는 것을 반복할지, 오른쪽으로 이동하는 것을 반복할지 비교 (커서 왼쪽 이동, 커서 오른쪽 이동 조이스틱 조작 횟수) 손으로 풀어보기 커서를 이동하면서 알파벳을 완성하기 위한 조이스틱 횟수를 증가 다음 알파벳으로 이동하는 것을 반복해서 완성할지, 이전 알파벳으로 이동하는 것을 반복할지 횟수 비교 예) B 다음 알파벳으로 이동할 경우 'B' - 'A' = 1 이전 알파벳으로 이동할 경우 26 - 'B' - 'A' = 25 커서를 이동하면서 변경..
✔ 모의고사 [프로그래머스 42840] 문제 분석하기 1번 수포자는 1에서 5를 순서대로 반복해서 찍는 방식 (1, 2, 3, 4, 5) 2번 수포자는 2를 제외한 1, 3, 4, 5를 2 다음에 반복해서 찍는 방식 (2, 1, 2, 3, 2, 4, 2, 5) 3번 수포자는 3-1-2-4-5 순서대로 2번씩 반복해서 찍는 방식 (3, 3, 1, 1, 2, 2, 4, 4, 5, 5) 각 수포자가 찍는 방식의 최소 단위에 대해 반복하며 answer와 비교하여 점수를 매기도록 완전 탐색 손으로 풀어보기 세 명의 수포자들 찍는 방식의 최소 단위에 대한 배열 작성 각 수포자들마다 완전 탐색하며 점수를 매김 최고 점수 찾기 최고 점수를 가지는 수포자들을 반환 슈도코드 작성하기 answers(1번 문제부터 마지막 문..
✔ 가장 큰 수 [프로그래머스 42746] 문제 분석하기 숫자의 앞자리가 가장 큰 숫자가 앞으로 와야 큰 수를 만들 수 있으므로 숫자를 문자로 변경한 후 앞뒤로 붙여가며 더 큰 순서대로 정렬 예) [6, 10, 2] 610 > 106 (6과 10) 62 > 26 (6과 2) 102 < 201 (10과 2) 정렬한 후 : [6, 2, 10]이므로 6210 손으로 풀어보기 정수 배열을 문자열 배열로 변경 앞뒤로 이어붙여 가며 가장 큰 순서대로 정렬 배열의 가장 앞이 0인지 확인 0이라면 0 반환 배열의 가장 앞이 0이 아니라면 배열 내 숫자들 이어 붙이기 가장 큰 수 반환 슈도코드 작성하기 numbers(0 또는 양의 정수가 담긴 배열) arr(numbers를 담을 문자열 배열) arr에 numbers 저장..
✔ 디스크 컨트롤러 [프로그래머스 42627] 문제 분석하기 각 작업에 대해서 작업이 요청되는 시점으로 배열을 오름차순 정렬, 작업의 소요시간으로 우선순위 큐를 오름차순 정렬할 수 있도록 한 후 작업이 요청되는 시점이 가장 빠른 작업을 먼저 수행한 후, 작업이 끝나는 시간에 수행될 수 있는 작업 중에서 작업의 소요시간이 가장 짧은 작업부터 실행하도록 함 만약 작업이 끝나는 시간에 수행될 수 있는 작업이 없다면 요청되는 작업 중 다음 작업을 넣도록 함 (스케줄링 알고리즘 중 SJF) 이때 가장 작은 값을 알아야 하므로 힙을 사용해 우선순위 큐 구현 손으로 풀어보기 각 작업에 대해서 작업이 요청되는 시점으로 배열을 오름차순 정렬 작업의 소요시간으로 우선순위 큐를 오름차순 정렬하도록 커스텀 작업이 요청되는 시..
✔ 올바른 괄호 [프로그래머스 12909] 문제 분석하기 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 하므로 스택/큐를 사용하여 괄호를 집어 넣은 후, 짝이 맞을 경우 함께 꺼내면서 모든 문자열을 실행한 후 남은 괄호가 있는지 확인함 손으로 풀어보기 스택/큐에 괄호를 집어 넣음 괄호가 짝을 이루는 경우 스택/큐에서 제거 스택/큐의 크기가 0이라면 true, 0이 아니라면 false 반환 슈도코드 작성하기 s('(' 또는 ')'로만 이루어진 문자열) stack(괄호를 담을 stack) for(s의 길이만큼) { if('('라면) { stack에 저장 } if(')'라면) { if(stack의 크기가 0이라면) { return false; } stack에서 짝이 맞는 '(' 제거 } } if..
✔ 완주하지 못한 선수 [프로그래머스 42576] 문제 분석하기 해시를 사용해 참가자들을 저장한 후, 완주한 선수들의 이름에 대해 완주 표시를 한 후 완주 표시가 없는 선수를 반환 해시는 값을 삽입하고 검색하는 평균 시간 복잡도가 O(1) 손으로 풀어보기 HashMap에 마라톤에 참가한 선수들의 이름과 +1을 저장 동명이인이 존재할 경우를 위해 기존 값에 +1이 됨 동명이인이 존재하지 않는다면 1이 됨 HashMap에서 완주한 선수들의 이름에 대해 1에서 -1을 해주며 완주 표시 동명이인이 존재할 경우 한 명의 사람이 완주했다면 2 - 1 = 1이 되게 됨 동명이인이 존재하지 않을 경우 한 명의 사람이 완주했다면 1 - 1 = 0이 되게 됨 HashMap에 완주 표시인 0이 아닌 선수 이름 반환 슈도코드..
✔ 가장 먼 노드 [프로그래머스 49189] 문제 분석하기 가중치가 없는 인접 리스트로 그래프를 표현한 후, BFS 탐색을 수행하며 가장 먼 거리를 저장 이후 가장 먼 거리를 가지고 노드의 개수를 찾음 손으로 풀어보기 인접 리스트로 노드와 간선의 그래프를 표현 BFS 탐색 알고리즘으로 탐색을 수행하면서 각 노드로 가는 거리값을 방문 배열에 저장 이때 가장 먼 거리를 저장 탐색 종료 후 방문 배열에 값이 가장 먼 거리와 같다면 갯수 증가 노드의 개수 반환 슈도코드 작성하기 n(노드의 개수) edge(간선의 정보가 담긴 2차원 배열) answer(가장 멀리 떨어진 노드의 개수) A(그래프 데이터 저장 인접 리스트) visited(방문 거리 저장 배열) depth(가장 먼 거리) for(n만큼 반복하기) { ..
