공부하고 기록하는, 경제학과 출신 개발자의 노트
반응형

프로그래밍/코딩테스트 문제풀이 190

[Python] 프로그래머스. 디스크 컨트롤러 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 programmers.co.kr heapq 라이브러리를 사용하고, 프로세스가 queue에 들어올 수..

[Python] 백준 10775. 공항

https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 www.acmicpc.net Union Find 문제. 문제를 Union find 형태로 풀어내는 방법은 https://mygumi.tistory.com/245 백준..

[Python] 프로그래머스. 2020 카카오 recruit - 가사 검색 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 | 프로그래머스 programmers.co.kr 트라이 자료구조를 안 쓰고 푸는 법 / 트라이 사용해서 푸는 법 두 가지 다 시도해 봤다. 트라이를 안 쓰는 경우는 python string의 startswith, endswith 방법을 사용해서 풀 수 있지만, 효율성에서 통과를 못 한다. 트라이를 사용할 경우 이 문제에서 가장 어려웠던 건 '문자열 개수'를 반영하는 것이었다. fro??일 경우 fro로 시작하면서 length가 5인, fro???는 length가 6인 걸 반환해야 하는데 fro까지 도착한 뒤, 아래 노드를 전부 순회하면 시간초과가 났다. 아마 노드를 순회하는..

[Python] 프로그래머스. 2018 카카오 recruit - 자동완성 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 | 프로그래머스 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하 programmers.co.kr 트라이 자료구조의 활용을 의도한 문제. 트라이 자료구조의 의미와 ..

[Python] 백준 14503. 로봇 청소기

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 삼성SW역량평가 A형 기출문제로, 엄청 어려운 문제라기보다는 신중하게 생각해서 코드를 짜야 하다보니 시간이 부족했을 법한 문제. ..

[Python] 프로그래머스. 기지국 설치 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 | 프로그래머스 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g programmers.co.kr N 크기가 크길래 이분탐색으로 풀어야 하나 고민했지만, 문제를 푸는 데..

[Python] 프로그래머스. 2019 카카오 recruit - 후보 키

https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 | 프로그래머스 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 데이터베이스의 Key 설명이 복잡하게 느껴질 수 있지만, 결국에는 '모든 row를 unique하게 식별할 수 있는 조합을 찾는다'가 된다. key의 조합을 하나하나 만들고, 해당 key가 table row의 개수를 동일하게 ..

[Python] 프로그래머스. 게임 맵 최단거리 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 프로그래머스 Level 4에 해당하지만, 단순 BFS로 충분히 해결할 수 있는 유형이다. BFS의 전형적인 문제형태. BFS로 맵을 순회하다가 목표지점인 오른쪽 하단에 도착하면 그곳까지 도달하는 데 걸린 횟수를 count하면 된다.

반응형