알고리즘/programmers(46)
-
[JS] 광고 삽입 - 누적합의 활용 2
저번에 2차원 배열의 누적합을 다뤄봤었는데, 이미 카카오는 작년부터 누적합을 엄청 물어보고 있었네요.이 문제도 역시 누적합에 관한 문제입니다. 문제 요약 "죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다. [제한사항] play_time, adv_time은 길이 8로 고정된 문자..
2022.09.22 -
[JS] 길찾기 게임 - 하발자 특(나): 힙 씀, 상발자 특: 트리 씀
길 찾기 게임 문제는 트리를 이용해야 합니다. 조금 아는 지식이 무섭다고.. 이런 문제 있으면 자꾸 힙을 쓰게 되서 구현이 너무 험난했는데요.. 트리를 쓰면 꽤나 쉬운 문제였습니다. 원래 알고리즘 올린 다음날엔 그거 쓰는 코테 문제 푸는게 국룰인거 아시죠? 2022.09.18 - [알고리즘] - [JS] 트리와 힙의 차이는 뭘까? 문제 요약 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 ..
2022.09.19 -
[JS] 섬 연결하기: 크루스칼 알고리즘과 union-find.
새로운 알고리즘이네요.그리디(Greedy) 알고리즘의 일종인 크루스칼(Kruskal) 알고리즘 입니다. 크루스칼 알고리즘 목적: 최소 신장 트리 구하기 주요 기능: Union - Find를 통한 최소 비용외의 간선 삭제 이런 노드들이 있다고 가정하면, 간선 [3 - 4]를 제외한 경로가 비용이 최소가 되는 경로입니다. 이런 경로를 구하는 방법은 다음과 같습니다. 1. 비용의 순서대로 정렬. 2. 해당 노드의 부모를 갱신. 3. 비용 계산으로 진행됩니다. union - find 연산은 node의 부모가 다를때 각 노드의 부모를 갱신해주는 알고리즘입니다. 부모가 같다면 해당 간선으로 사이클이 발생할 수 있기 때문에 부모가 같은 경우는 제외하게 됩니다. 종종 union 연산 시 갱신하는 parent가 최상단의..
2022.09.17 -
[JS] 숫자 게임 - 비겼을 때 처리를 해주자!
옛날 문제를 자꾸 풀게 되는데,뭔가 창의력을 요구한달까.. 요즘은 유형이 어느정도 나뉘잖아요. 오히려 접근이 편한데 옛날 문제는 약간 창의력을 보네요.이 문제는 엣지 케이스 처리만 잘해주면 크게 어려운 건 없습니다. (17, 18번이 문제이신 분들은 비겼을 때만 처리해주면 되거든요...!) 문제 요약 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀..
2022.09.14 -
[JS] 최고의 집합: 산술-기하 평균으로 접근해보자!
프로그래머스 UI가 개편되면서 꼭 leetcode 처럼 바뀌었네요.저번 정렬 기준으로 1페이지를 다 풀었었는디.. 이제 다시 채워야죠! 자 그럼 레벨 3 - 1번 문제인 최고의 집합을 같이 보시죠! 문제 요약 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다. 집합의 원소의 개수..
2022.09.12 -
[JS] 성격 유형 검사하기: 난 해시맵이 좋아!
레벨 1 처음 다루는 거 같습니다. 근데 생각보다 어려워요(레벨 1치고는) 같이 보죠! 문제 요약 나만의 카카오 성격 유형 검사지를 만들려고 합니다. 성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다. 지표 번호성격 유형 1번 지표 라이언형(R), 튜브형(T) 2번 지표 콘형(C), 프로도형(F) 3번 지표 제이지형(J), 무지형(M) 4번 지표 어피치형(A), 네오형(N) 4개의 지표가 있으므로 성격 유형은 총 16(=2 x 2 x 2 x 2)가지가 나올 수 있습니다. 예를 들어, "RFMN"이나 "TCMA"와 같은 성격 유형이 있습니다. 검사지에는 총 n개의 질문이 있고, 각 질문에는 아래와 같은 7개의 선택지가 있습니다. 매우 비동..
2022.09.08