옌의 로그

문제 [프로그래머스] 게임 맵 최단거리 사용 알고리즘 - 너비우선탐색 (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] -, /의 ..

문제 [프로그래머스] 정수 삼각형 사용 알고리즘 - 동적계획법(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..

문제 [프로그래머스] 주차 요금 계산 (2022 KAKAO BLIND RECRUITMENT) 사용 알고리즘 - HASH MAP 해결방법 입-출차 시간을 기록하는 carMap, 주차 시간을 기록하는 parkTime 두개의 map을 사용하여 해결 records 맵을 돌며 입차인 경우 (IN) carMap에 저장해주고, 출차인 경우 (OUT) carMap 에 저장된 입차 시간을 꺼내 몇 분간 주차했는지 계산하여 parkTime에 저장한다. 이때 계산에 사용된 입차기록은 carMap 에서 삭제 records 확인 후 carMap 에 입차 기록이 남아있는 경우 23:59에 출차한 것으로 가정 후 주차 시간 계산 여기서 포인트는. . 'HH:mm' 형식으로 들어오는 시간 데이터를 H에 60을 곱해 분단위로 바꾸어 ..

문제 [프로그래머스] 압축 (2018 KAKAO BLIND RECRUITMENT) 사용 알고리즘 - HASH MAP 해결방법 알파벳을 key로 index를 value로 가지는 alphaMap 생성 Argument로 입력받은 msg를 이중 for문을 돌면서 탐색하는데, 이 때 alphaMap에 없던 코드면 추가해주고 answer 배열에 값을 인풋해준다. 바깥 for 문을 통해 msg의 첫번째 알파벳부터 LZW 압축 과정을 진행한다. 안쪽 for 문은 현재 시점의 알파벳을 시작으로 다음 알파벳을 하나씩 붙여가며 alphaMap에 해당 key값이 존재하는지 확인한다. 존재하는 가장 긴 key 값을 발견하게 되면, 그보다 더 긴 key값은 맵에 저장해주고, 해당 키에 대한 value값을 통해 압축한다. 더보기 ..