고딩왕 코범석

문제는 여기! 안녕하세요! 이번 시간에는 백준의 미네랄 문제에 대해 풀이해보겠습니다. 항상 시뮬레이션 문제는 많은 경우의 수를 생각해야하기 때문에 푸는 도중에는 머리가 터질 것 같지만 정답 판정을 받았을 때의 기분은 상당히 짜릿합니다.시간 복잡도따위 일단 맞고보자 그럼 바로 풀이 가보시죠! 나의 풀이 전략 일단 골따리 시뮬레이션 문제들은 참으로 까다롭습니다. 제가 풀이했던 문제들이 많지는 않지만, 시뮬레이션 문제들은 가만 보면 시간 복잡도를 고려하기 보다는 문제를 어떻게 푸느냐가 제일 중요한 것 같아요. 문제에서 보면 동굴의 크기, 막대를 던진 횟수 들이 그리 크지 않습니다. 문제의 핵심은 막대기를 던진 이후 미네랄의 군집화 처리, 미네랄 클러스터들 마다 중력에 의해 바닥으로 떨어지는 것을 처리 이 두 ..

문제는 여기! 안녕하세요! 이번 시간에는 프로그래머스 고득점 kit DP파트, 난이도 Level4 문제였던 도둑질 문제를 풀이해보겠습니다. 제한사항 및 주의사항 각 집은 동그랗게 배치되어 있습니다. 인접한 두 집을 털게 되면 경보가 울립니다. 우리는 경보가 울리지 않게 집을 털어야 하고, 최대한 돈을 많이 털어야 합니다. 마을에 있는 집은 3 이상 1,000,000 이하 입니다. money 배열의 각 원소는 0 이상 1,000 이하 정수입니다. 풀이전략 각 집은 동그랗게 배치되어 있기 떄문에, 첫 번째 집을 털게 될 경우 마지막 집은 털 수 없습니다. 그래서 저는 첫 번째 집을 털 경우 dp[0][i]와 첫 번째 집을 털지 않을 경우 dp[1][i]로 나누어서 풀었습니다. 그럼 이제, dp[i]번째는 어..

문제는 여기! 안녕하세요! 이번 포스팅은 2021 카카오 블라인드 채용 문제였던 "순위 검색" 문제를 풀이해보겠습니다. 프로그래머스에서는 레벨 2로 나와있지만 꽤 어려웠습니다. 특히 효율성 테스트를 만족시키는게 까다로웠는데, query에서 -가 있는 경우 어떻게 처리를 할지 좀 고민을 많이했던 문제였습니다. 그럼 바로 풀이해보겠습니다! 제한사항 및 주의사항 info 배열의 크기는 1 이상 50,000 이하 입니다. 점수는 1 이상 100,000 이하의 자연수입니다. query 배열의 크기는 1 이상 100,000 이하 입니다. 풀이전략 info 리스트의 언어, 직군, 경력, 소울푸드를 하나로 묶어서 딕셔너리의 키로 사용합니다. 이때, query에서 -가 포함된 경우도 존재하기에 언어가 있을 경우와 '-'..

문제는 여기! 안녕하세요! 이번 시간에는 프로그래머스의 연습문제인 "여행경로" 문제 풀이에 대해 포스팅하겠습니다. 문제의 설명이 조금 빈약 저의 머리도 빈약 해서 다른 사람들의 포스팅을 보고 풀이 방법에 대해서 조금 참고하면서 풀었습니다. 그럼 시작할게요! 제한사항 및 주의사항 주어진 공항의 수는 3 이상 10,000 이하 입니다. tickets의 각 행 [a, b]의 의미 : a 공항에서 b 공항으로 가는 항공권이 있다. 주어진 항공권을 모두 사용해야 합니다. 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return 합니다. 풀이전략 인트로에서 말씀드렸듯, 처음에 문제 자체를 올바르게 이해하지 못했습니다. 주어진 모든 항공권을 사용해야 한다라는 의미는 모든 공항을 탐색해야 한다는 의미..

문제는 여기! 안녕하세요! 이번 포스팅에서는 프로그래머스의 "월간 코드 챌린지 시즌1" 문제였던 풍선 터트리기 문제를 풀어볼까 합니다. 항상 "이 문제는 어떤 알고리즘으로 풀지?" 라고 생각하다가 신박한 방법이 필요했던 문제라서 이번 포스팅에서 정리해보았습니다. 스스로 완벽하게 해결하지는 못했던 문제였어서 다른 풀이들을 많이 참조했습니다. 바로 가보시죠! 제한사항 및 주의사항 임의의 인접한 두 풍선을 고르고 두 풍선중 하나를 터트릴 경우, 번호가 작은 풍선은 한번만 터트릴 수 있습니다. 이를 제외하면 번호가 큰 풍선만 터트릴 수 있습니다. 작은 풍선을 터트리는 경우를 저는 찬스라고 표현해보겠습니다. 풍선 리스트 a의 크기는 1 ~ 1,000,000 이며, a[i]의 크기는 -10억 이상 ~ 10억 이하인..

문제는 여기! 안녕하세요! 이번 포스팅에서는 2019 카카오 개발자 겨울 인턴십 문제였던 "불량 사용자"를 풀이해보겠습니다. 이 문제는 접근을 어떻게 할지 몰라서 결국 다른 분들의 풀이를 참고했습니다. 사실 봐도 좀 헷갈리는 부분이 있어서 이 기회에 정리할 겸 포스팅하게 되었습니다. 그럼 풀이 시작해보겠습니다! 제한사항 및 주의사항 user_id 배열의 크기는 1 이상 8 이하 입니다. banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하 입니다. user_id, banned_id의 각 원소들은 길이가 1 이상 8 이하인 문자열 입니다. 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다. 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 대항하고 같은 응모자 아이디가 ..

문제는 여기! 안녕하세요! 이번 포스팅에서는 2021 카카오 블라인드 채용 문제인 "합승 택시 요금" 문제를 풀어보겠습니다. 2021년도 Level3 문제들 중에서 체감 상 가장 난이도가 낮은 것 같았습니다. 형냐들 나만그래? 최단 거리 문제를 살짝 응용하면 쉽게 풀 수 있는 문제라서 바로 풀이로 넘어가 보도록 하겠습니다. 제한사항 및 주의사항 지점 간 택시가 이동할 수 있는 경로를 간선이라고 하며, 간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타냅니다. 또한 이동방향에 따라 금액이 달라지지 않습니다. 지점의 갯수 n은 3이상 200 이하입니다. s, a, b는 1 ~ n까지의 범위이며, 서로 겹치지 않습니다. fares의 크기는 2 이상 n * (n - 1) / 2 이하입니다. fares의 ..

문제는 여기! 안녕하세요! 이번 포스팅에서는 2021 카카오 블라인드 채용 알고리즘 문제인 "광고 삽입" 문제를 풀이해보겠습니다. 2021년도 레벨3 문제들을 풀어보면서 느낀점은 확실히 예전 년도들에 비해 문제 난이도가 많이 어려웠습니다. 심지어 나온지 얼마 안된 문제여서 풀이를 해주신 분들이 많이 안계셔서 애를 많이 먹기도 했던 문제입니다. 저도 결국 카카오에서 직접 해주신 해설을 봐도 모르겠어서 다른 분의 코드를 참조하면서 이해했습니다. 그럼 풀이 시작할게요! 제한사항 및 유의사항 play_time, adv_time은 길이 8로 고정된 문자열이며, HH:MM:SS 형식입니다. 그리고 00:00:01 ~ 99:59:59 까지의 범위입니다. 광고 재생 시간은 동영상 재생 시간보다 짧거나 같게 주어집니다...