본문 바로가기

알고리즘

 (138)
[코드 작성][보호절 숙어] 좋은 분기문 작성법 http://redutan.github.io/2016/04/01/good-if
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 다트 게임 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열 처리 [ 문제 풀이 ] 보너스와 옵션에 맞춰 누적된 숫자에 계산해주면 됩니다. 다만, 이를 문자열을 한 글자씩 처리할 경우 신경써서 처리해야 할 부분이 생깁니다. 두 자리 수입니다. 두 자리 수는 10밖에 없습니다. 따라서 10을 미리 한 자리 문자열로 치환하면 계산을 쉽게 처리할 수 있습니다. [ 정답 코드 ] # S: 1제곱, D: 2제곱, T: 3제곱 # *: 해당 점수와 바로 전에 얻은 점수를 각 2배 # #: 해당 점수를 마이너스 def solution(dartResult): li = [] i = -1 dartResult = dartResult.replace("10", "K") for n in dartResult: if n == "S": cont..
[그래프] 최단 경로 트리 알고리즘 vs 최소 신장 트리 알고리즘 다익스트라, 플로이드: 최단 경로 트리 프림: 최소 신장 트리 최단 경로 트리 알고리즘과 최소 신장 트리 알고리즘은 서로를 보장하지 않음 따라서 위의 사진을 보면 프림 알고리즘이 0->2의 비용이 더 나가는 것을 볼 수 있음 (최단 경로를 보장하지 않기 때문이다.) 최소 신장 트리 알고리즘에는 모든 정점을 연결하는데 의의가 있다. 다익스트라와 플로이드의 차이는 다익스트라 : 시작 정점 to 모든 최단 경로 플로이드 : 모든 정점 to 모든 정점 최단경로
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 방금그곡 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열 처리 [ 문제 풀이 ] ABC는 ABC#안에 들어있지 않지만, ABCD안에는 들어있습니다. C과 C#은 다르기 때문입니다. 그래서 #의 문자열 처리가 이 문제의 핵심입니다. 저는 C#은 c로 치환하여 C#과 C와의 차이를 두었습니다. 다른 '대문자#' 문자열에도 마찬가지로 적용했습니다. [ 정답 코드 ] def solution(m, musicinfos): answer = ["(None)", 0] for info in musicinfos: start, end, title, song = info.split(",") # 악보 변환 ch = {"C#": "c", "D#": "d", "F#": "f", "G#": "g", "A#": "a", "E#": "e"} f..
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 비밀지도 [ 문제 ] 문제 풀러 가기 [출제 의도] 비트 연산자 활용 [ 문제 풀이 ] 지도1과 지도2의 각 정수를 비트 OR 연산자를 이용해 합칩니다. 합친 결과의 길이가 N보다 짧다면 앞 부분에 공백을 넣어 길이를 N으로 맞춥니다. 마지막으로 0은 공백으로 1은 #으로 치환하면 됩니다. [ 정답 코드 ] def solution(n, arr1, arr2): answer = [""] * n for i in range(n): tmp = str(bin(arr1[i] | arr2[i]))[2:] # 비트 OR answer[i] = (n % len(tmp)) * "0" + tmp # 고정길이 N answer[i] = answer[i].replace("0", " ") answer[i] = answer[i].replace(..
[프로그래머스][2019 KAKAO BLIND RECRUITMENT][Python] 오픈채팅방 [ 문제 ] 문제 풀러 가기 [출제 의도] 해시 활용 [ 문제 풀이 ] 먼저, record를 순회하면서 '입장과 변경 기록'을 가지고 딕셔너리를 이용해 유저 아이디마다 최종 닉네임을 구하고, '입장과 퇴장 기록'은 new_record를 만들어서 따로 저장합니다. 그다음, new_record를 순회하면서 채팅방에 출력할 메시지를 생성합니다. 이때 유저 아이디는 최종 닉네임을 사용하면 됩니다. [ 정답 코드 ] # 시간복잡도 O(N)으로 처리 from collections import defaultdict def solution(record): name = defaultdict(str) order = [] new_record = [] # 닉네임 관리 for datas in record: data = data..
[프로그래머스][2019 KAKAO BLIND RECRUITMENT][Python] 매칭 점수 [ 문제 ] 문제 풀러 가기 [출제 의도] 정규표현식 활용 [ 문제 풀이 ] 먼저, 정규표현식으로 HTML 파일에서 현재 URL, 외부 URL 그리고 검색어를 찾습니다. 외부 URL의 수는 외부 링크 수가 되고, 검색어의 개수는 기본 점수가 됩니다. 각 HTML 파일의 기본 점수 / 외부 링크를 저장해 놓았다가, 해당 웹 페이지와 연결된 다른 웹 페이지의 링크 점수를 구할 때 사용합니다. 마지막으로 페이지마다 (기본 점수와 링크 점수를 더한) 매칭점수를 구하고, 최댓값의 Index를 구합니다. 최댓값이 여러 개라면, Index가 가장 작은 것이 정답입니다. [ 정답 코드 ] # 졍규표현식 활용 from collections import defaultdict import re def solution(wor..
[프로그래머스][2020 KAKAO BLIND RECRUITMENT][Python] 괄호 변환 [ 문제 ] 문제 풀러 가기 [출제 의도] 주어진 로직 그대로 구현 문자열 활용 재귀함수 [ 용어의 정의 ] '균형 잡힌 괄호 문자열'은 괄호의 개수가 맞습니다. '올바른 괄호 문자열'은 괄호의 개수도 맞고 짝도 맞습니다. [ 문제 풀이 ] 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4..
[프로그래머스][2020 KAKAO BLIND RECRUITMENT][Python] 문자열 압축 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열을 활용 [ 문제 풀이 ] 문자열 길이가 N일 때, 분절 범위는 1부터 n/2입니다. n/2를 넘어가게 되면 문자열을 줄일 수 없습니다. 문자열의 길이는 최대 1,000입니다. 따라서 완전 탐색을 해도 시간 초과가 나지 않습니다. 그래서 분절 범위마다 줄인 결괏값 중에서, 가장 짧은 길이를 찾았습니다. 주의할 점은 문자열 길이가 1이면 1을 반환합니다. [ 정답 코드 ] def solution(s): result = len(s) + 1 for n in range(1, (len(s) // 2) + 1): # 분절 범위 cnt = 1 tmp = len(s) check = True for i in range(0, len(s) - n + 1, n): # 앞에서부터..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 합승 택시 요금 [ 문제 ] 문제 풀러 가기 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다. [출제 의도] 최단 경로 알고리즘 [ 문제 풀이 ] 먼저, 모든 노드에서 모든 노드로의 최단 경로를 구해야 합니다. Floyd-Warshal 알고리즘을 사용했습니다. cost[i][j] = i에서 j로 가는 최저 택시 요금 그다음, 어느 노드를 A와 B의 분기점으로 정할지 구해야 합니다. K를 분기점이라고 했을 때, S ~ K, K ~ A, K ~ B의 합이 최솟값일 때가 정답입니다. 문제에서 요구하는 답 = min(cost[s-1][k] + cost[k][a-1] + cost[k][b-1]) (단, k = 1 ~ n) Dijkstra 알고리즘을 사용하지 않은 이유는 비효율적이기 때문입니다. [ 정답 코드 ] #..

티스토리툴바