코딩 조아 코딩 조아

알고리즘 (코딩테스트)

• 그리디 알고리즘

  알고리즘 (코딩테스트) 2024. 11. 7. 13:25

  1. 백준 회의실배정https://www.acmicpc.net/problem/1931- 주어진 회의 일정들을 회의실 하나에서 최대한 많이 배정하는 것이 목표- 주요 아이디어는 빨리 끝나는 회의를 먼저 선택하는 것빨리 끝나는 회의를 먼저 배정하면 남은 시간 동안 더 많은 회의를 배치할 수 있습니다.따라서 종료 시간이 빠른 회의부터 배정하면, 회의가 겹치지 않으면서 최대한 많은 회의를 배정할 수 있습니다.import sysinput = sys.stdin.readdef max_meetings(meetings): # 종료 시간을 기준으로 오름차순 정렬 (종료 시간이 같으면 시작 시간 기준) meetings.sort(key=lambda x: (x[1], x[0])) count = 0 ..

  Read More
• DFS/BFS

  알고리즘 (코딩테스트) 2024. 10. 24. 15:23

  1. 프로그래머스 네트워크핵심: 컴퓨터가 방문되지 않았다 = 그 컴퓨터가 새로운 네트워크에 속해 있다는 의미  DFS로 그 네트워크를 탐색한 후, 방문되는 컴퓨터가 없으면(독립적인 네트워크임) 네트워크 수를 증가시킨다def dfs(node, visited, computers): visited[node] = True for i in range(len(computers)): if computers[node][i] == 1 and not visited[i]: dfs(i, visited, computers) # 1-2가 연결되었다면, 다시 2컴퓨터로 이동해서 dfs반족def solution(n, computers): visited = [False] * n # 각 ..

  Read More
• 이분탐색

  알고리즘 (코딩테스트) 2024. 10. 22. 22:52

  1. 정렬된 배열 또는 정렬 가능한 값이 주어진다이분 탐색은 기본적으로 오름차순 또는 내림차순으로 정렬된 배열에 대해서만 사용할 수 있습니다.정렬된 배열에서 특정 값을 찾거나, 특정 범위 안에서 값을 찾아야 할 때 이분 탐색을 떠올리면 좋습니다.2. 탐색의 대상이 숫자, 길이, 무게 등의 ‘범위’일 때결과값이 특정 범위 내에 있는지를 판별해야 하거나, 특정 값 이상이거나 이하인 값을 찾는 경우 이분 탐색을 활용할 수 있습니다.예를 들어 "최소 길이" 또는 "최대 무게" 등의 제한이 있다면, 이분 탐색으로 조건에 맞는 최적의 값을 찾을 수 있습니다.3. ‘최대값’ 또는 ‘최소값’을 찾아야 하는 경우예를 들어 특정 작업을 수행하는 데 필요한 최소 시간이나 최대 크기를 찾는 문제는 이분 탐색의 후보가 될 수 ..

  Read More
• 완전탐색(Brute Force)

  알고리즘 (코딩테스트) 2024. 10. 21. 22:51

  특징: 가능한 모든 경우의 수를 탐색하는 방법. 작은 데이터셋에서 유용하며, 시간이 허락되는 한 최적해를 찾는 데 유리함.자주 나오는 문제 유형: 1) 가능한 모든 경우를 시도하여 해를 찾는 문제2) 순열 및 조합 문제 1. 백준 - 부분수열의 합https://www.acmicpc.net/problem/1182 부분수열이란? 배열에서 일부 원소를 선택하여  순서는 유지하되, 연속하지 않아도 되는 수열ex. [-7, -2, 3, 4] 의 부분수열: [-7] [-2] [3] [4] [-7, -2] [-7, 3] [-7, 4] [-2, 3] [-2, 4] [3, 4]  [-7, -2, 3] [-7, -2, 4]  이처럼 연속하지 않아도 순서만 유지하면 됨  아이디어)각 원소는 선택 하거나, 선택하지 않거나 두..

  Read More
• DP 실전문제

  알고리즘 (코딩테스트) 2024. 10. 20. 14:50

  1. 프로그래머스 - N으로 표현https://school.programmers.co.kr/learn/courses/30/lessons/42895  아이디어)dp[i] = N을 i번 사용해서 만들 수 있는 숫자들의 집합i번 사용했을때 가능한 숫자들은, i-1번까지 사용한 숫자들과 사칙연산을 통해 계산ex)- dp[1] = { 5 }  : 5를 한번만 사용- dp[2] = N을 2번 이어붙인  수+ 이전연산과의 사칙연산 조합{ 55, 5+5, 5-5, 5/5, 5*5 } :  55, dp[1]과의 사칙연산조합- dp[3]은 dp[1]과 dp[2]의 조합{ 555, 55+5, 55-5, 55*5, 55/5, 10+5, 10-5, 10*5, 10/5, ..... }- dp[4]는 dp[1]과 dp[3]의 조합..

  Read More
• DP (다이나믹 프로그래밍) 기본개념/기본문제

  알고리즘 (코딩테스트) 2024. 10. 17. 10:18

  [ 1차원DP 기본문제 ] 거스름돈 문제11원을 만들 때 최소한의 동전 개수를 찾고 싶습니다.사용할 수 있는 동전은 [1, 2, 5]입니다.      dp[x] : x원을 만들기 위한 최소 동전 개수     1을 사용하면 dp[10] + 1 (10원을 만드는 방법에 동전1 추가)     2를 사용하면 dp[9] + 2  (9원을 만드는 방법에 동전2 추가)     5를 사용하면 dp[6] + 5      - dp[6] = dp[5] + 1 (5원을 만드는 방법 동전1 추가)          >> 각 경우 중 가장 작은 경우     dp[x] = min(dp[x-1] + 1, dp[x-2] + 1, dp[x-5] + 1)          "x원을 만들기 위해 필요한 최소 동전 개수는, 그보다 작은 금액들을..

  Read More
• 다익스트라와 MST(최소신장트리)

  알고리즘 (코딩테스트) 2024. 10. 16. 15:03

  다익스트라 대표 문제 : https://www.acmicpc.net/problem/1753 (백준 1753 최단경로)def dijkstra(V, graph, start): distance = [float('inf')] * (V + 1) # 모든 노드의 최단 경로를 무한대로 초기화 distance[start] = 0 # 시작 노드의 거리는 0으로 설정 q = [(0, start)] # (거리, 노드)를 우선순위 큐에 삽입 while q: current_distance, current_node = heapq.heappop(q) # 현재 노드까지의 거리가 이미 더 짧다면 무시 if current_distance > distance[current_..

  Read More