옌의 로그

문제 [백준] IF문 좀 대신 써줘 사용 알고리즘 - 이분 탐색 (Binary Search) 해결방법 입력받은 전투력 배열(level_num)을 이분탐색으로 탐색한다. 예제 2에서 살펴보면 다음과 같은 흐름으로 계산된다 더보기 99가 입력되었을 때 lv : 99 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) right => 0 (mid - 1) left : 0, right : 0 mid : 0 level_num[mid] : 100 (B) right => -1 (mid - 1) level_name[mid] : B . . . lv : 101 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) left => 2 (mi..

문제 [백준] 크림 파스타 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 dp[A배열 원소 개수] = (최대값 - 최소값)의 최대값 A배열에 값이 들어올 때 마다 A의 원소중 최소값과 비교해 최소값을 체크해준다. 들어온 값 - 최소값 과 dp[i-1]을 비교해 더 큰 값을 dp[i]에 기록해준다. A 배열에 원소가 들어올 때마다의 상황을 표로 나타낸 것 50이 들어왔을 때 원소 중 최소값 : 50 input 값과 최솟값의 차 : 0 50이 들어오기 전까지 가장 (최대값-최소값)의 최대값 : 0 dp[1] = 0 100이 들어왔을 때 원소 중 최소값 : 50 input 값과 최소값의 차 : 50 (100-50) 100이 들어오기 전까지 가장 (최대값-최소값)의 최대값 (= d..

문제 [백준] 설탕 배달 (Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번) 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 동전으로 금액을 만드는 문제와 같다고 보면 된다. > 3과 5를 가지고 N키로 만들기 $dp[N] = 사용한 최소 동전(설탕 봉지) 수 $dp 배열을 0으로 초기화 해준 뒤 반복문을 돌면서 채워주면 되는데, 이 때 3, 5 번째는 각 각 1개의 봉지 만으로 만들 수 있기 때문에 1로 갱신, 4의 경우 만들 수 없는 숫자기 때문에 0으로 갱신해준다. $dp[$i-3], $dp[$i-5] 의 값이 모두 있는 경우 (0보다 큰 경우) 최소 값에 1을 더해주면..

문제 [프로그래머스] 호텔 대실 사용 알고리즘 - 그리디 (Greedy) 해결방법 키 포인트는 다음 2가지 시간 데이터를 분으로 변경 입실 시간을 기준으로 정렬 퇴실 시간을 담는 배열을 통해 필요한 방의 개수를 count 입실 시간을 기준으로 정렬한 배열 sortedT를 가지고 반복문을 돌며, 해당 순서 사람의 끝나는 시간을 finishT 배열에 담는다. finishT 배열은 항상 빠른 시간이 앞에 오도록 오름차순 정렬을 해주고, 반복문이 돌때마다 현재 순서 사람의 입실 시간과 finishT 배열의 가장 빠른 퇴실 시간을 비교해, 퇴실시간이 더 빠른 경우 그 방에 사람을 받을 수 있다는 뜻이므로 finishT 배열에서 해당 시간을 제거한다. finishT에 담기는 데이터를 순서대로 보면 다음과 같다. f..

문제 [프로그래머스] 게임 맵 최단거리 사용 알고리즘 - 너비우선탐색 (Breath-First Search) 해결방법 BFS사용해서 풀면 되는데, 결국 문제에서 구해야 하는 것은 최단 경로로 이동했을 때의 길이이므로, 방문을 체크하는 visited 배열에 길이를 저장해주도록 한다 그래프에서 상,하,좌,우 로 이동이 가능하므로 4방향 이동을 간단하게 표현하기 위해 dir 배열을 만들어 사용 needVisit배열이 BFS의 큐로 보면 되고, 이때 FIFO이므로 while 루프에서 꺼낼 때 shift() 메소드를 사용해 먼저 들어온 것 부터 체크 방문하지 않은 지점 (visited배열의 값이 0) 혹은, 이미 방문한 지점이지만 현재 위치에서 한 칸 이동한 것의 길이가 더 최단일 경우 큐(needVisit)에 ..

문제 [프로그래머스] N으로 표현 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 dp 즉, 메모이제이션을 사용한다 N = 5 일 때, dp[N의 개수] = 만들 수 있는 정수의 집합 dp[1] = 5 dp[2] = 10, 0, 25, 1, 55 5+5, 5-5, 5*5, 5/5, 55 dp[3] = 3개의 5로 만들 수 있는 정수 집합 = dp[1] 과 dp[2]의 연산 결과 집합 = [5] (+, -, *, / ) [10, 0, 25, 1, 55] dp[4] = 4개의 5로 만들 수 있는 정수 집합 = dp[1] X dp[3] + dp[2] X dp[2] dp[5] = 5개의 5로 만들 수 있는 정수 집합 = dp[1] X dp[4] + dp[2] X d[3] -, /의 ..

문제 [프로그래머스] 표 편집 (2021 카카오 채용연계형 인턴쉽) 사용 알고리즘 - 연결리스트 (Linked List) 해결방법 표의 각 행 정보를 저장하는 Node를 만들고, 해당 노드들을 가지고 linked list를 생성한다 Node는 행의 index, 해당 행 이전 행의 index(prev), 다음 행의 index(next)를 갖는다. moveSelectedNode (count, direction) : 명령어 U, D 사용 direction (prev, next) 방향으로 count 만큼 이동하여 select 된 Node를 변경 deleteNode : 명령어 C 사용 현재 select된 Node를 cStack에 따로 저장 후 해당 Node의 prevNode의 next, 해당 Node의 nextN..

문제 [프로그래머스] 정수 삼각형 사용 알고리즘 - 동적계획법(Dynamic Programming) 해결방법 2차원 db배열을 만들어 구한다. dp[i][j] == (i, j) 지점까지 가는데 발생한 최대 경비 꼭대기에서 바닥까지 이어지는 경로를 구하는데, 이 때 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[2][1] = max(dp[1][0], dp[1][1]) + triangle[2][1] 각 층의 첫 번째 자리는 위 층에서만 갈 수 있다 dp[i][0] = dp[i-1][0] + triangle[i][0] dp[3][0] = dp[2][0] + trian..

문제 [프로그래머스] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP) 사용 알고리즘 - 다익스트라 해결방법 (출발지 - 산봉우리 - 출발지) 해당 등산 루트에서 intensity 가 가장 작은 경로를 구해야 하는데 해당 문제는 양방향 그래프이므로 (출발지 - 산봉우리) 편도만 확인해도 된다. intensity == 휴식 없이 이동해야 하는 시간 중 가장 긴 시간 모든 출발지들을 우선순위 queue에 넣고 탐색을 시작한다. 탈출 조건 해당 지점에서의 intensity가 이미 구해진 경우 산봉우리에 도착한 경우 temp 큐에 산봉우리 번호와 비용(intensity)를 저장한다. 더보기 더보기 now: 1 to: 2 cost: 0 weight: 3 pq.push(3, 2) now: 3 to..

문제 [프로그래머스] 셔틀버스 (2018 KAKAO BLIND RECRUITMENT) 사용 알고리즘 - X (구현 문제) 해결방법 콘은 출근하기 위해 셔틀버스 줄을 서는데 가장 늦게 줄을 스고자 한다. 마지막으로 탄 애보다 일찍와야 됨. answerMin = arrivedMin - 1; } } else { // 배차 시켜주기 startMin = startMin + t; } } let answerHours = parseInt(answerMin / 60); let answerMinutes = answerMin % 60; if (answerHours < 10) answerHours = "0" + answerHours; if (answerMinutes < 10) answerMinutes = "0" + answ..