Dionysus

📌 문제 요약사과를 먹으면 몸 길이가 늘어나는 뱀이 N x N 보드 위에서 이동할 때, 벽이나 자기자신의 몸과 부딪히면 게임이 종료된다. 게임 시작 시 뱀은 맨위 맨좌측에 위치하며 몸 길이는 1이다. 또한 보드의 상하좌우 끝에 벽이 있다고 한다. 뱀은 처음에 오른쪽을 향하며, 몸 길이가 늘어날 땐 꼬리는 그대로 있고 머리가 한 칸 자라나 앞으로 이동한다. 사과의 위치와 뱀의 이동경로가 주어질 때, 이 게임이 몇 초에 끝나는지 계산하라. 😖 내가 생각한 로직 + 알고리즘파이썬의 deque를 사용하여 꼬리 위치를 저장해뒀다가 사과를 먹으면 그대로 두고, 사과를 먹지 못하면 popleft()를 통해 꼬리를 이동시키는 방식으로 구현하였다.  🤗 제출 후 pass한 코드from collections impo..

📌 문제 요약강 위의 다리를 n개의 트럭이 지나가려고 한다. 다리 위에는 w대의 트럭만이 동시에 올라갈 수 있다고 할 때, 모든 트럭들이 다리를 건너는 최단 시간을 출력하라. (단, 트럭의 순서는 변경할 수 없으며 트럭의 무게는 서로 같지 않을 수 있다. 또한 트럭들은 하나의 단위 시간에 하나의 단위 길이만큼만 이동할 수 있다고 가정한다.) 😖 내가 생각한 로직 + 알고리즘현재 다리 위에 있는 트럭의 무게를 group 변수에 저장하고, 현재 다리 위에 있는 트럭들의 첫 번째 트럭 순서 정보를 startTruck 변수에 저장한다. 또한 다리 위에 올라가지 못한 트럭들 중 가장 순서가 빠른 트럭의 순서 정보를 nextTruck 변수에 저장한다. 그리고 nextTruck 변수의 값이 n과 같거나 작은 동안..

목차✅ 다이나믹 프로그래밍(DP) 기법이란?✅ DP로 해결 가능한 대표 문제: 피보나치 수열✅ DP 구현 방식 (Top-Down / Bottom-Up)✅ 예제 문제 ✅ 다이나믹 프로그래밍(DP) 기법이란?💡 다이나믹 프로그래밍 (DP, Dynamic Programming) 기법  큰 문제를 작게 나누고 같은 문제라면 한 번씩만 연산하여 문제를 효율적으로 해결하는 알고리즘 기법으로, '동적 계획법'이라고도 한다. 컴퓨터의 제약 사항(연산 속도의 한계, 한정된 메모리 공간)을 극복하기 위해 메모리 공간을 조금 더 사용하여 연산 속도를 비약적으로 증가시킴으로써 문제를 해결하는 방법이다.▷ 프로그래밍에서 '다이나믹(Dynamic)'은 '프로그램이 실행되는 도중에'를 의미한다. 따라서 자료구조의 동적 할당(Dy..

가볍게 알아보는 CS 지식!아래 순서로 진행해볼게요!🧐 ☝🏻프로세스프로세스(Process)와 스레드(Thread)의 개념프로세스 상태 전이PCB (Process Control Block, 프로세스 제어 블록)문맥 교환(Context Switching)✌🏻프로세스 스케줄링스케줄링의 개념과 목적스케줄링 기법👌🏻스케줄링 알고리즘선점형 기법비 선점형 기법✌🏻프로세스 스케줄링✅ 스케줄링(Scheduling)의 개념과 목적✔️ CPU 스케줄링(CPU Scheduling)메모리에 올라온 프로세스(process)들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것으로, 준비 큐(Ready Queue)에 있는 프로세스들 중 CPU를 할당받을 프로세스를 결정하는 과정을 의미한다. CPU 스케줄링이 발생하는 상..

목차💬 최소 비용 신장 트리 (Minimum Spanning Tree, MST) 💬 Prim 알고리즘💬 Kruskal 알고리즘💬 최단 경로 알고리즘 (Dijkstra)💬 최소 비용 신장 트리 (Minimum Spanning Tree, MST)더보기무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리를 의미한다.Prim 알고리즘 또는 Kruskal 알고리즘을 활용한다.💡 신장 트리란?n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리📌 대표적인 그래프에서의 최소 비용 문제- 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리- 두 정점 사이의 최소 비용 경로 찾기 ✅ MST 표현 예시  💬 Prim 알고리즘더..

목차💬 서로소 집합 (Disjoint-sets) 💬 서로소 집합(Disjoint-sets)더보기💡 서로소 집합(Disjoint-sets)서로소 또는 상호배타 집합들로, 교집합이 없는 집합들을 의미한다.집합에 속한 하나의 특정 멤버를 통해 집합들을 구분하는데, 이를 대표자(representative)라고 한다. 상호배타 집합 표현 방법연결 리스트트리상호배타 집합 연산Make - Set(x)유일한 멤버 x를 포함하는 새로운 집합을 연산하는 연산Find - Set(x)        return {representative}x를 포함하는 집합을 찾는 연산Union(x, y)x와 y를 포함하는 두 집합을 통합하는 연산📌 상호배타 집합의 예  ✅ 상호 배타 집합 표현 - 연결리스트같은 집합의 원소들을 하나의..