코딩코양이코리

알고리즘으로 생각하기 - 양성봉 참고 백준 문제를 풀다가 알고리즘 풀이가 잘 기억이 나지 않아서교과서에 있는 알고리즘 코드를 외우기 위해 작성 작은 것부터 풀어보기설명문제를 작은 것부터 풀어본다 → 작은 문제들을 먼저 풀어서 그 해를 이용하여 문제 해결→ 동적 계획 작은 문제: 원래 주어진 문제와 같은 문제, 작은 문제를 부분 문제라고 함 가장 긴 증가 순서설명숫자가 일렬로 나열되었을 때 가장 긴 증가 순서를 찾아보자.증가 순서는 숫자들이 반드시 이웃해야만 할 필요 X[5, 2, 8, 6, 4, 6, 1, 9, 3]에서 [5, 8, 9], [5, 6, 9], [2, 4, 6, 9] 등 전부 증가 순서가장 긴 증가 순서는 [2, 4, 6, 9]이다. 문제를 다른 형태의 문제로 바꾸어 생각하기 → 그래프 만..

알고리즘으로 생각하기 - 양성봉 참고 백준 문제를 풀다가 알고리즘 풀이가 잘 기억이 나지 않아서교과서에 있는 알고리즘 코드를 외우기 위해 작성 태스크 스케줄링1. 구간 스케줄링 설명n개의 태스크와 1개의 프로세스가 있을 때, 수행 시간이 겹치지 않게가장 많은 태스크들을 수행하는 방법단, 각 태스크는 시작과 종료 시각을 가진다. 시간 복잡도정렬 O(nlogn) + task검사 O(1) = O(nlogn) 알고리즘[1] 종료시각으로 정렬한다.[2] 가장 일찍 종료하는 동아리를 선택한다.[3] 다음 동아리의 시작 시각이 직전에 선택된 동아리의 종료 시각 이전이면     다음 동아리를 포기하고, 이후이면 다음 동아리를 선택한다. 코드a = [['지역봉사회', 8, 13], ['서예회', 9, 11], ['토론회..

풀이https://devum.tistory.com/83 이 분 사진을 참고했다. while문은 x를 m씩 계속 증가시키는데, 그 값은 m*n보다 커질 수 없으니 while x이 문제는 두 가지만 이해하면 된다.1. x값을 고정시켜두고 M값을 증가시키며 해를 찾음.2. x를 10씩 올려가며 찾은 answer(x +=m)값%N - y%N == 0이 되는 값이 해다. 예를들어 M = 10, N = 12일 때, 를 찾는 문제라면,m = 10, n = 12, x = 3, y = 9x가 3이면 정답은 3, 13, 23, 33, ... 113중 있다. 그래서 x값을 고정시키고, M값을 증가시키면서 해를 찾는데y값은 증가시킨 x값들을 살펴봤을 때, answer(증가시킨 x)%n == y 값이 있다면 그게 해가 된다.-..

문제  첫 번째 풀이import sysinput = sys.stdin.readlinecomputer = int(input().strip())n = int(input().strip())connect = []for _ in range(n):    connect.append(list(map(int, input().strip().split())))virus = [0] * (computer + 1)virus[1] = 1def spread_virus(start):    queue = [start]        while queue:        current = queue.pop(0)        for a, b in connect:            if a == current and virus[b] == 0:..

문제 코드import sysinput = sys.stdin.readlinen = int(input())lst = [int(input()) for _ in range(n)]dp = [0]*nif len(lst) 2:    print(sum(lst))else:    dp[0] = lst[0]    dp[1] = lst[0] + lst[1]    for i in range(2, n):        # dp[i-3]+lst[i-1]과 dp[i-2]의 최댓값        # 즉 0, 2 -> 3으로 간 것과 0, 1 -> 3 간 것의 최댓값을 구함        dp[i] = max(dp[i-3]+lst[i-1]+lst[i], dp[i-2]+lst[i])    # 마지막 계단까지 최대 점수 출력    print(..

문제 코드import sysfrom collections import dequeinput = sys.stdin.readlinen, m  = map(int, input().split())graph = []for _ in range(n):    graph.append(list(map(int, input().rstrip())))dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def BFS(x, y):    queue = deque()    queue.append((x, y))    while queue:        x, y = queue.popleft()        for i in range(4):            nx = x + dx[i]            ny = y + dy[i]..

풀이import sysinput = sys.stdin.readlinen = int(input())lst = []for _ in range(n):    start_time, end_time = map(int, input().split())    lst.append([start_time, end_time])lst.sort(key=lambda x: (x[1], x[0]))solution = [lst[0]]i = 0for j in range(1, len(lst)):    if lst[j][0] >= lst[i][1]:        solution.append(lst[j])        i = jprint(len(solution))회의실 배정 문제는 수업시간에 풀어봤던 문제라 쉽게 풀었다. 알고리즘그리디 알고리즘..

풀이import sysimport heapqinput = sys.stdin.readlinen = int(input().rstrip())heap = []for _ in range(n):    x = int(input().rstrip())    if x == 0:        if len(heap) > 0:            # 가장 작은 값 출력            m = heapq.heappop(heap)            print(m)        else:            print(0)    else:        heapq.heappush(heap, x) heap 기초 문제

첫 번째 풀이import sysinput = sys.stdin.readlinen, m = map(int, input().split())a_lst = []b_lst = []for _ in range(n):    a = input().strip()    a_lst.append(a)for _ in range(m):    b = input().strip()    b_lst.append(b)a_lst.sort()b_lst.sort()set_a_lst = set(a_lst)set_b_lst = set(b_lst)print(len(set_a_lst.intersection(set_b_lst)))for i in set_a_lst.intersection(set_b_lst):    print(i)풀어서 정답이 나왔다.하지만..

문제 알고리즘BFS 탐색을 사용해 풀 수 있다.코드import sysfrom collections import dequedef bfs(v):    q = deque([v]) # 시작점 v를 q에 추가    while q:        v = q.popleft() # 덱의 왼쪽에서 요소 제거하고 반환        if v == k: # 현 위치가 동생과 같을 때            return array[v]        # 다음 위치로 이동할 수 있는 경우의 수 확인        for next_v in (v-1, v+1, 2*v):            # 위치가 범위 내에 있고, 아직 방문하지 않은 위치라면            if 0 next_v MAX and not array[next_v]:  ..