알고리즘
-
[프로그래머스] 광고 삽입 / KAKAO BLIND RECRUITMENT / 파이썬알고리즘/프로그래머스 2021. 2. 23. 16:35
문제 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제를 딱 보고 파싱하고 슬라이딩 윈도우로 풀면 되겠다 했는데 logs의 길이가 최대 30만이라서 계속 시간초과가 떴다. 근데 몇시간동안 안풀리고 답답해서 카카오 공식 해설을 보고 풀었다.. 구간합이라는 테크닉을 필요로 했는데 이 부분을 몰라서 문제를 풀지 못했던 것 같다. 뭔가 카카오 문제들은 풀고나면 쉬워보이는데, 풀기전 까지는 진짜 너어어무 어렵다! 풀이 1. 우선 모든 시간,분,..
-
[프로그래머스] 합승 택시 요금 / KAKAO BLIND RECRUITMENT / 파이썬알고리즘/프로그래머스 2021. 2. 22. 12:57
문제 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 1. 택시가 이동할 수 있는 경로 마다 예상 택시 요금이 있는데 a와 b가 s에서 출발하여 가장 적은 요금으로 둘 다 귀가를 하는 것이 목적입니다. 2. 지점 별로 최소 예상..
-
[백준] 1162 도로포장 파이썬알고리즘/백준 2021. 2. 19. 18:41
문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 풀이 1. 서울에서 시작하여 포천까지 최소 시간이 걸리도록 해야합니다. 2. 도시별로 최소 시간을 구하기 위해서 다익스트라 알고리즘을 구현합니다. 3. 주의할 점은 K개를 사용해서 거리를 포장하면 시간이 0이 되기 때문에 이 부분을 구현해야 합니다. 4. 구현하는 방법은 도시별의 최소 시간과 도시별 방문 유무 리스트를 2차원(N * K)으로 늘려주면 됩니다. 포천에서 1 ~ K번 포장했을 때의 최단시간을 구해주고 그중 최..
-
[프로그래머스] 신규 아이디 추천/ KAKAO BLIND RECRUITMENT / 파이썬알고리즘/프로그래머스 2021. 2. 18. 20:28
문제 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr 풀이 1. 파이썬 내장 모듈인 re 모듈을 이용하여 풉니다. 코드 import re def solution(new_id): #1단계: 모든 대문자를 대응되는 소문자로 치환 new_id = new_id.lower() #2단계: 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거 new_id = re.sub('[^\w\.-]', '', new_id) #3단계: 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 ..
-
[백준] 1068번 트리 파이썬알고리즘/백준 2020. 12. 30. 23:57
문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1. 노드 클래스와 트리 클래스를 기본적으로 틀을 짜줍니다. 2. 트리 클래스에 깊이 우선 탐색 알고리즘을 이용하여 현재 노드에서 자식노드가 지워줄 노드가 같다면 해당 자식을 리스트에서 제거합니다. 3. 이때 루트 노드와 지워줄 노드가 같다면 트리의 root를 none으로 바꿔주고 예외 처리로 0을 출력해줍니다. ( 루트 노드부터 지운다면 트리 전체가 없어진다는 뜻) 4. 그후 다시 트리 전체를 깊이 우선 탐색하여 현재의 노드가 자식이 없을 경우..
-
[백준] 14502번 연구소 파이썬알고리즘/백준 2020. 12. 29. 20:22
문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 1. 우선 벽 3개를 무조건 세워야 하기 떄문에 완전탐색으로 케이스마다 벽 3개를 세워줍니다. 2. 그다음에 너비 우선 탐색으로 케이스 마다의 안전 영역 크기를 구합니다. 3. 케이스 마다의 안전 영역 크기중에 가장 큰 수를 리턴합니다. 코드 from copy import deepcopy from collections import deque from itertools import combinations dxy = [[0, 1], [0, -1], [1, 0], [-1..