하미의 기술 블로그

코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 👩🏻‍💻 코드 def solution(phone_book): phone_book.sort() for i in range(len(phone_book) - 1): if len(phone_book[i + 1]) >= len(phone_book[i]): if phone_book[i + 1].find(phone_book[i]) == 0: return False return True 📝 정리 오름차순으로 phone_book 정렬 두 개씩 비교하며 앞의 전화번호가 뒤의 ..

코딩테스트 연습 - 스킬트리 programmers.co.kr 👩🏻‍💻 코드 def solution(skill, skill_trees): answer = 0 for st in skill_trees: idx = 0 flag = True for s in st: if s == skill[idx]: idx += 1 if idx == len(skill): break elif s not in skill: continue else: flag = False break if flag: answer += 1 return answer 📝 정리 효율성 테스트가 존재하지 않기 때문에 일일이 비교하는 방법으로 해결했다. skill_trees 내에 있는 스킬 트리와 skill을 동시에 확인하였다. skill에 존재하는 철자인 경우 ..

코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 👩🏻‍💻 코드 import java.awt.*; import java.util.*; public class Solution { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, -1, 0, 1}; static int[][] map; static boolean[][] visited; public int[] solution(int m, int n, int[][] picture) { int numberOfArea = 0;..

코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 👩🏻‍💻 코드 import math def solution(w,h): return w * h - (w + h - math.gcd(w,h)) 📝 정리 직사각형에서 잘리는 부분의 크기가 (가로 + 세로 - 가로와 세로의 최대공약수) 라는 것을 생각하는 것이 다소 어려웠다. 반면 코드는 매우 짧음.. 규칙 찾기란 항상 어려운 것..😅

코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 👩🏻‍💻 코드 import heapq def solution(N, road, K): answer = 0 graph = [[] for _ in range(N + 1)] distance = [1e9] * (N + 1) for i in range(len(road)): start, end, time = road[i] graph[start].append((end, time)) graph[end].append((start, time)) q = []..

코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 👩🏻‍💻 코드 def solution(land): dp = [[0] * 4 for _ in range(len(land))] for i in range(len(land)): for j in range(4): if i == 0: dp[i][j] = land[i][j] else: max_list = dp[i - 1].copy() del max_list[j] dp[i][j] = max(max_list) + land[i][j] return max(dp..

💡 '서로 다른 개체가 연결되어 있다' or '여러 개의 도시가 연결되어 있다' ⇒ 그래프 알고리즘 그래프와 트리 속성 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 부모와 자식 관계 X 부모와 자식 관계 O 모델의 종류 네트워크 모델 계층 모델 서로소 집합 union: 하나의 집합으로 합치는 연산 find: 특정한 원소가 속한 집합을 알려주는 연산 서로소 집합 알고리즘 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b):..

다익스트라 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 음의 간선이 없을 때 ex) GPS 그리디 알고리즘 매번 '가장 비용이 적은 노드'를 선택하기 때문 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 → 최단 거리 테이블 갱신 5. 위 과정에서 3,4번 반복 방법1: 간단한 다익스트라 시간복잡도: O(V^2) import sys input = sys.stdin.readline INF = int(1e9) # 10억 n, m = map(int, input().split()) # 노드 개수, 간선 개수 start = int(input()) # 시작..

DP 사용 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 탑다운(Top-Down) 방식 # 피보나치 수열 with 재귀 함수 d = [0] * 100 def pibo(x): if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = pibo(x-1) + pibo(x-2) return d[x] 보텀업(Bottom-Up) 방식 # 피보나치 수열 with 반복문 d = [0] * 100 d[1] = 1 d[2] = 1 for i in range(3, 99): d[i] = d[i-1] + d[i-2] 파이썬 재귀 제한 완화 import sys sys.setrecursionlimit(10**6)..

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 시간복잡도:O(N) 이진 탐색 배열 내부 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 방법 시간복잡도:O(logN) 재귀 함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target, start, mid - 1) els..