본문 바로가기

분류 전체보기

 (171)
[프로그래머스][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 알고리즘을 사용하지 않은 이유는 비효율적이기 때문입니다. [ 정답 코드 ] #..
[BOJ] [Python] 1914: 하노이 탑 전형적인 하노이 탑 구현 문제이다. def honoi_tower(n, start, tmp, end): if n == 1: print(start, end) else: honoi_tower(n-1, start, end, tmp) print(start, end) honoi_tower(n-1, tmp, start, end) num = int(input()) print(2 ** num - 1) if num
[복잡도] 시간 복잡도와 공간 복잡도 시간 복잡도 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 알고리즘을 위해 필요한 메모리의 양
[최단 경로 트리] 플로이드-워셜 알고리즘[Floyd-Warshall] 플로이드-워셜 알고리즘에 대해 알아보자. 플로이드-워셜 알고리즘은 '거쳐 가는 기점'를 기준으로 최단 거리를 구한다. 예를 들어보자. 아래와 같은 그래프가 있다. 이차원 배열의 형태로 출력하면 다음과 같다. 위 상태의 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이제 이 배열을 '거쳐 가는 기점'을 기준으로 반복적으로 갱신할 것이다. 그렇게 한다면 결국엔 모든 A에서 B의 최소 비용을 구해진다. 거쳐 가는 기점이 1인 경우 이렇게 거쳐 가는 기점이 1, 2, ... N인 경우를 모두 확인한다. 다익스트라 알고리즘 vs 플로이드-워셜 알고리즘 공통점 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 차이점 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구한다. 플로이드-워..
[그래프] 인접 행렬과 인접 리스트 전체 정점 개수: N 젠체 간선 개수: E 1. 인접 행렬 그래프의 연결 관계를 이차원 배열로 표현하는 방법이다. graph라는 이차원 배열이 있다고 하자. 이에 인접 행렬을 다음과 같이 정의할 수 있다. 1) 가중치가 없을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 1, 없다면 0. 1) 가중치가 있을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 가중치, 없다면 INF. 장점 두 정점을 연결하는 간선을 조회할 때 시간복잡도가 O(1)이다. 단점 1. 간선 수에 상관없이 N^2크기의 이차원 배열이 필요하다. 메모리 낭비이다. 2. 모든 간선 수를 알아내기 위한 시간복잡도가 O(N^2)이다. 2. 인접 리스트 그래프의 각 정점에 인접한 정점들을 연결리스트..

티스토리툴바