알고리즘/programmers(46)
-
[JS] 코딩 테스트 공부 : 공부 팁 X, 카카오 2022 인턴 문제 O
보통 프로그래머스에서 문제 제목이 있으면 "JS PROBLEM_TITLE" 이런식으로 검색하면 쉽게 다른 블로그의 풀이를 볼 수 있는데, 이 문제는 제목이 너무.. 알고리즘에 잡히기 힘들겠더라구요ㅋㅋㅋㅋ 아무튼 가봅시다! 어제에 이은 또 dp문제네요. 문제 요약 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재..
2022.09.06 -
[JS] 가장 긴 팰린드롬 - dp를 잘 써보자!
레벨 3도 앞장을 다 했네요.앞장에서는 우선순위 큐(힙)나 덱과 같은 자료구조나 최소거리 문제, 완전 탐색 같은 주제였는데요.다시 dp를 다뤄볼 때가 온 것 같습니다. 이게 가장 어려운 것 같아요. 같이 한 번 볼까요? 문제 요약 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다. 제한사항 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 테스트케이스 s answer "abcdcba" 7 "ab..
2022.09.05 -
[JS] 경주로 건설 - 코테 인생 최초로 9000ms대를 만나다!
말이 되나요.. 9000ms 미리 보여드립니다~ 아마 제가 이상하게 푼 거 같긴한데.. 더 이상 걸러낼 자신 없습니다. 일단 푼 거나 공유해드리겠습니다. 네.. 걸러냈네요. 큐가 아니라 우선순위 큐를 이용한 다익스트라 알고리즘으로 접근 시 훨씬,, 훠어어얼씬 빠릅니다. 문제 요약 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다. 경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1)..
2022.09.03 -
[JS] 합승 택시 요금: Do you know Floyd-Warshall?
안녕하세요! 이 문제는 플로이드-워셜 알고리즘을 알고 있다면 3분만에 해결할 수 있습니다. 플로이드-워셜 알고리즘이 어떤 상황에서 쓰이는 지 알고 있는가? 를 물어보는 문제네요. 문제 요약 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이..
2022.09.02 -
[JS] 이중우선순위큐: 비겁한 정렬은 이제 그만! 당당히 힙으로 맞서 싸워!
안녕하세요. 어제 공유드린 제가 새로 짠 힙을 응용할 시간이 되었군요. [JS] 힙/우선 순위 큐 새로 짜봤습니다. Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요. 저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요. 특히 pop에서 최상단 노드부터 dev-russel.tistory.com 문제는 되게 쉽습니다. 같이 한 번 볼까요? 문제 요약 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,..
2022.08.31 -
[JS] 불량 사용자: 정규 표현식을 내 맘대로 써보자!
정규 표현식을 물어보는 문제가 가끔씩 있더라구요.매번 검색해서 어떻게 어떻게 해내긴 했는데 한 번 다뤄보는게 좋을 것 같습니다. 이 문제가 딱 그렇게 다루기 좋아보여서 가져와봤습니다. 정규 표현식 Javascript에선 주로 string 형식의 문자열에서 원하는 값이 있는지 찾기 위해서 사용합니다. 일반적으로 웹에서 이메일 형식의 input을 받는다던가, password에 특정 규칙을 만족하는지 등에서 쓰입니다. 다만, 코딩테스트에서 다루는 정규 표현식의 성격은 약간 다를 수 있을 것 같습니다. 보통 이런 식으로 묻는 경우가 많습니다. 어떤 특정 자리에 이 문자가 들어가는지? 이 자리에 모든 문자가 올 수 있을 때 만족하는 문자는? 이스케이프 문자를 다 외우는 건 약간 비효율적인 것 같습니다. 검색하면 ..
2022.08.27