본문 바로가기

프로그래머스8

[알고리즘] 순위 (프로그래머스 Level3) 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 그래프 탐색 문제이다. 순위라고 했으므로 현재 그래프 내에서의 각 노드들의 위치를 알아내야 하는 문제이다. 즉, 각 선수마다 해당 선수보다 강한 선수 + 약한 선수의 수를 구해서 합쳐서 n이 된다면 랭킹을 정확하게 구할 수 있는 선수이다. 예전에도 비슷한 문제를 풀어본 기억이 있는데 'DFS + 역그래프 + DP + Set'을 적절히 활용하면 쉽게 풀 수 있다. Solution 예시 input을 단방향 그래프로 그린 모습이다. 보다시피 2번 선수 뒤에는 1, 3, 4번, 앞에는 5번 선수가 있으므로 다른 모든 선수와의 관계를 명확히 할 수 있다. 5번 또한 본인 뒤에 .. 2020. 9. 7.
[알고리즘] 등굣길 (프로그래머스 Level3) 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 그림만 봐도 느껴지겠지만 탐색 문제이다. 다만 문제에서 최단 경로라고 언급을 했으니 BFS를 이용하기로 했다. 하지만 Level3 문제답게 단순한 BFS 문제는 아니다. 단순히 '최단 경로' 만 구하라고 한 것이 아니라 '최단 경로의 개수'를 구하라고 했다. 즉 특정 노드를 기준으로 그곳에 도착한 경로들의 개수들을 세어야 하고 이것은 동적 프로그래밍을 이용해서 메모이제이션해야한다. 즉 BFS + DP 문제이다. (추후에 알게된 사실인데 BFS도 .. 2020. 9. 7.
[알고리즘] 보석쇼핑 투포인터 (2020 카카오 인턴십) 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이것 또한 결국 못 풀었던 문제였다. 특정 조건을 만족하는 '구간'을 찾아야하는 문제이므로 투포인터기법을 활용해야한다. 만약 투포인터 기법을 활용하지 않고 찾게 된다면 O(N ^ 2)의 시간이 걸리게 된다. 투포인터 기법 활용 시 O(N) 시간 만에 찾을 수 있다. Solution 우선 HashMap을 만들어서 보석의 이름을 키값으로 count라는 객체를 만든다. 이 때 count의 사이즈는 총 보석 종류의 수가 된다. 반복문을 돌린다. 현재 구간에 포함된 보석 종류의 수를 나타내는 gem_count가 총 보석.. 2020. 8. 30.
[알고리즘] 수식 최대화 (2020 카카오 인턴십) 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 상반기 카카오 인턴십 때 나온 문제이다. 해당 코딩 테스트에 참가했었기에 기억이 난다. (통과는 못했다.) 이 문제도 결국 못 풀었던 걸로 기억한다. 지금와서 다시 찬찬히 살펴보니 결국 문자열 처리 문제이다. 정확히 말하자면 '브루트 포스 + 문자열 처리' 문제라고 할 수 있겠다. 브루트 포스 문제인만큼 재귀 함수 사용은 필수적이다. 모듈은 크게 2개로 나누었는데 첫 번째는 '연산자 우선순위 결정' 메서드이고 나머지 하나는 '수식 계산' 메서드이다. 연산자.. 2020. 8. 29.

티스토리툴바