🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법lose_list[i] → i번 선수에게 진 선수들의 리스트와 win_list[i] → i번 선수에게 이긴 선수들의 리스트를 각각 구한다.즉, 단방향 그래프 형식으로 이긴 선수들의 그래프와 진 선수들의 그래프 관계를 나타냈다. i번 선수에게 이긴 선수들과 i번 선수에게 진 선수들을 모두 구한다.만약 순위를 매길 수 있다면, lose_list[i]의 수 + win_list[i]의 수는 n-1일 것이다. 이를 구하기 ..
전체 글
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법모든 노드의 가중치가 동일했기 때문에 BFS를 사용하여 최단 거리를 구했다.1번 노드에서 모든 노드까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구한 뒤, 거리 배열에서 가징 긴 거리의 개수를 구했다. 😎 내 코드from collections import dequedef BFS(v, graph, visited): distances = [0 for _ in range(len(visited))] ..
🗂️ 문제링크: https://www.acmicpc.net/problem/1874 💡 접근법제시하는 입력값의 수열을 만들기 위해 1~N까지 차례로 숫자가 입력될 때 스택에서 어떤 순서로 push와 pop을 해야할 지를 결정해야 하는 문제이다. 풀이는 다음과 같다. 1부터 N까지 숫자를 차례대로 입력한다.스택의 top이 현재 비교하는 수열보다 작다면 현재 숫자를 스택에 push한다.스택의 top이 현재 비교하는 수열과 같다면 스택에서 pop하고, 반복 수행한다.위 과정을 while 문을 통해 반복 수행하는 이유는, pop한 뒤 수열의 top과 다음 수열이 같을 수 있기 때문이다.모든 숫자를 입력한 뒤 만약 스택이 비어있다면 만들 수 있는 수열이 되고, 스택이 비어있지 않다면 만들 수 없는 수열에 해당한..
프로세스는 운영체제(OS)에서 실행 중인 프로그램을 의미하고, 스레드는 프로세스 내에서 실행되는 작은 작업 단위이다.프로세스는 각각 독립적인 메모리 공간을 가지는 반면, 스레드는 같은 프로세스 내에서 메모리를 공유하여 빠르게 실행한다. 1. PCB컨텍스트 스위칭운영체제(OS)가 현재 실행 중인 프로세스(또는 스레드)의 상태(Context)를 저장하고, 새로운 프로세스를 실행하기 위해 기존 상태를 복원하는 과정이다. 이때 PCB에 저장하고 불러온다.멀티태스킹 환경에서 CPU가 여러 프로세스를 빠르게 전환하기 위해 필요하다. 캐시 미스컨텍스트 스위칭이 발생하면 CPU 캐시에 저장된 기존 프로세스의 데이터가 새로운 프로세스의 데이터로 교체된다. 기존 캐시 데이터가 무효화되므로 새로운 프로세스의 데이터를 캐시에..
🗂️ 문제문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.예를 들어..
🗂️ 문제링크: https://www.acmicpc.net/problem/1904 💡 접근법00과 1을 조합하여 N자리의 수를 만드는 문제이다.문제에서는 제시하는 자릿수에 따라 만들 수 있는 수의 개수가 달라진다. 규칙을 찾아보기 위해 다음과 같이 N에 따라 가능한 경우를 나열해보았다. N=1일 때, 1 ⇒ 1개 N=2일 때, 11, 00 ⇒ 2개 N=3일 때, 001, 100, 111 ⇒ 3개 N=4일 때, 1111, 0011, 1001, 1100, 0000 ⇒ 5개 N=5일 때, 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 ⇒ 8개 규칙을 보니 DP인 걸 단숨에 알아낼 수 있었다. 하지만 왜 DP인가를 생각해보면, 그 이유는 다음과 같다. 2진..
🗂️ 문제링크: https://www.acmicpc.net/problem/14002 💡 접근법DP를 통해 LIS를 푸는 문제의 응용편이다. i번째까지 순열에 대해 증가하는 순열인 경우이면서 부분 순열의 길이가 더 길어질 때, dp에 현재까지의 부분 순열을 저장한다.이후, 가장 길이가 큰 부분 순열에 대해 부분 순열의 길이와 부분 순열을 출력한다. 😎 내 코드import sysN = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))dp = [[arr[i]] for i in range(N)]for i in range(1, N): for j in range(i): if arr[i] > arr[j] an..
🗂️ 문제링크: https://www.acmicpc.net/problem/2579 💡 접근법i번째 계단까지 오르는 데 최댓값을 구해야한다는 DP 관점은 이해했으나, 점화식을 제대로 세우지 못했다. 계단에 오를 수 있는 경우는 1. i-1번째 계단에서 오르는 경우, 2. i-2번째 계단에서 오르는 경우이다.하지만 i-1번째 계단에서 오르는 경우가 연속된다면, 최종적으로는 i-2 → i-1 → i번째 순으로 계단에 오르게 된다.이를 처리하기 위해 i-1번째 계단에서 오르는 경우에 대해서는 무조건 그 이전에는 i-3번째 계단을 거쳐야 한다. 따라서 이를 고려한 최종적인 점화식은 다음과 같다.dp[i] = max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[1] (i ≥ 2) ..