본문 바로가기

코딩테스트27

[코딩 테스트] 프로그래머스 - 블록 이동 (2020 Kakao) in Python "0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성! 더 자세한 정보 - programmers.co.kr/learn/courses/30/lessons/60063 풀이 - 2차원 배열에서 '이동'하는 문제는 너비 우선 탐색 (BFS) 방법이 유용할 때가 많다. - 가능한 주변 좌표에 가보고, 안되면 다시 돌아와 다른 곳으로 가는 로직이 FIFO, 선입선출, 큐의 것과 비슷하기 때문이다. - 언제나 중요한 점! 구현이 복잡해지면, 기능 별로 따로 따로 메소드를 구현하는 것이 상당히 유용하다. 코드 구현 def possible(position, board): next_pos = [] positio.. 2021. 3. 10.
[코딩테스트] 프로그래머스 - 기둥과 보 (2020 Kakao) in Python 벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성! 더 상세한 설명↓ programmers.co.kr/learn/courses/30/lessons/60061 문제풀이는 프로그래머스의 강의를 바탕으로 작성하였습니다. 풀이 - 요구사항이 아주 자세하게 문제에 적혀 있다. - 요구사항을 하나 하나 따라하면 되는, "시뮬레이션 - Simulation" 문제로 정의될 수 있다 한다. - 시뮬레이션 문제는 보통 시간복잡도에 있어서 널널하게 주어진다고 한다. ~> 이번 문제 또한 O(N^3)으로도 (배열 활용), O(N^2)으로도 (Set와 Tupl.. 2021. 3. 9.
[코딩테스트] 프로그래머스 - 입국심사 (Lv.3) in Python 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 주어질 때, 모든 사람이 심사를 받는 데 걸리는 최소 시간을 return하세요. programmers.co.kr/learn/courses/30/lessons/43238 풀이 - 입국심사에 드는 시간 중 최댓값 (최악의 경우)은 max(times) * n. - n은 최대 1억, times[i]는 최대 1분, times의 길이는 최대 10만 - 이렇게 변수의 크기가 크기 때문에, 최대한 알고리즘 수행 속도를 줄일 수 있게 이분탐색을 도입한다. - 기존 기본적인 이분탐색 문제와 다른 점은, 원하는 값이 mid와 같은 상황 - "Search 성공" -이, 꼭 우리가 원하는 답이라는 보장은 없다는 것이다. -.. 2021. 3. 9.
[코딩테스트] 프로그래머스 - 가사 검색(2020 Kakao) in Python 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성. ?는 한 글자를 나타내는 와일드카드이다. 예시: words = ["frodo", "front", "frost", "frozen", "frame", "kakao"], queries = ["fro??", "????o", "fr???", "fro???", "pro?"]일때, answer = [3, 2, 4, 1, 0] 잘못된 풀이 - 중첩의 중첩을 이용, 각 query마다 모든 단어의 모든 글자를 탐색하는 방법은, 역시나 효율성 테스트에서 실패했다. - words (100,000 이하), 각 가사.. 2021. 3. 9.

티스토리툴바