본문 바로가기

전체 글

카테고리 없음 블로그를 이전 합니다. https://velog.io/@seilk
카테고리 없음 트리의 독립집합 트리의 독립집합 문제 2213번: 트리의 독립집합 개요 트리의 최대 독립집합을 구하고 그 구성 노드들을 출력해야 하는 문제이다. 이 때 최대 독립집합은 독립집합의 구성 원소들이 그래프에서 인접하지 않아야 하며 원소들의 가중치의 합이 최대가 되어야 한다. 트리의 독립집합 문제풀이 접근 및 시간복잡도 계산 이 문제는 어떤식으로 접근해야할까? 먼저 모든 노드는 최대 독립집합에 포함될(1) 수도 있고 포함되지 않을(2) 수도 있다. 즉 모든 노드는 총 2가지 경우의 수를 갖는다. 가장 Naive한 풀이는 $O(2^N)$의 풀이를 생각할 수 있다. $N$이 커서 당연히 시간초과가 난다.) 이 상황에서 우리는 시간복잡도를 낮추는 방향을 고려해야한다. 이렇게 생각해보자 $1≤N≤10000$이기 때문에 보편적으로 $O..
자료구조/알고리즘의 정의 (Definition of Data Structure and Algorithms) 및 알고리즘 문제를 해결하는 방법
알고리즘 & 자료구조/정의 자료구조/알고리즘의 정의 (Definition of Data Structure and Algorithms) 및 알고리즘 문제를 해결하는 방법 자료구조 자료를 담고 있으며 사용자가 원하는 연산을 수행할 수 있는 구조. 연산 : 자료삽입, 자료의 최댓값 호출, 자료구조의 마지막 자료 삭제 등등. Abstract Data Type(추상적 자료형)의 연산을 가능하게 해주는 구조. 사용자는 어떤 연산을 할지 정하고 가장 효율적인 자료구조를 선택할 수 있다. Abstract Data Type 추상적 자료형이란? Abstract Data Structure 추상적 자료구조란? 알고리즘 어떠한 문제를 해결하기 위해 정해진 절차나 일련의 방법, 문제를 해결하는 방법 알고리즘 문제를 해결하는 방법 논리적 순서 확정 관련 문제 카테고리 끌어오기 필요한 자료연산 리스트 업 이에 제일 유리한 자료구조 선택 구현
무지의 먹방라이브 (그리디)
알고리즘 & 자료구조/Greedy 무지의 먹방라이브 (그리디) 문제 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 풀이 from heapq import * def solution(ft, k): new_ft = [(val, idx + 1) for idx, val in enumerate(ft)] # food_time을 순서와 함께 새로 정의 heapify(new_ft) # heap 이진 트리 형태로 갱신 spendTime = 0 prev = 0 l = len(ft) # 남아있는 음식의 가짓수 ans = -1 # k초뒤의 방송사고 뒤 음식을 먹는것이 불가능 할 때 == 모든 음식의 합 시간이 k 보다 작을 때 if sum(ft) > k: '''현..
알고리즘 & 자료구조/LCA 최소 공통 조상(LCA) 문제 https://www.acmicpc.net/problem/11438 개요 트리의 최소 공통 조상이란 Lowest Common Ancestor을 의미하며 LCA로 알려져 있다. 예를 들어 위와 같은 트리에서는 LCA(2, 3) = 1 LCA(6, 7) = 1 LCA(15, 11) = 11 이다. 풀이 LCA를 찾는 방법은 Linear하게 \(O(N)\)만에 찾는 방법과 \(O(logN)\)만에 찾는 방법이 있다. 물론 노드의 개수가 많으면 많을 수록 \(O(logN)\)을 쓰는 것이 훨씬 효율적이고 그 방법을 써야만 한다. 이 글은 \(O(logN)\)만에 찾는 방법을 설명하는 것에 중점을 둔 글이므로 Linear하게 찾는 방법은 간단히 설명하고 넘어가겠다. LCA를 찾는 Linear한 방법 : 1...
[kocw] 1강 운영체제 개요
운영체제 [kocw] 1강 운영체제 개요 운영체제 정의 운영체제 설계자 입장에서 운영체제를 공부하는 수업 운영체제는 하드웨어를 관리하면서 사용자나 소프트웨어가 하드웨어를 몰라도 사용할 수 있도록 도와줌 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행 컴퓨터 시스템을 편리하게 사용할 수 있는 환경을 제공 운영체제는 동시 사용자/프로그램들이 각각 독자적 컴퓨터에서 수행되는 것 같은 환상을 제공 컴퓨터 시스템의 자원을 효율적으로 관리 주어진 자원으로 최대한의 성능을 내도록 = 효율성 특정 사용자/프로그램의 지나친 불이익이 발생하지 않도록 = 형평성 운영체제는 실행중인 프로그램들에게 짧은 시간씩 CPU를 번갈아 할당 컴퓨터 시스템의 구조 CPU의 작업공간은 메모리이다. 매 클럭마다 CPU는 메모리의 어딘가에 있는 기계어를 읽고 그것을 연산한다. ..
알고리즘 & 자료구조/백트래킹 [프로그래머스] 불량 사용자 문제 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 개요 입력으로 "*" 처리 된 불량 사용자와 실제 유저들의 아이디 목록을 받는다. 그런 다음 불량 사용자가 될 수 있는 유저들의 아이디를 매칭해서 서로 다른 가능한 조합의 개수를 세는 문제이다. 예를 들면 [a*cd, ab*d], [abcd, abxd, abvd] 이렇게 입력이 들어오면 가능한 조합의 개수는 (abcd, abxd) (abcd, abvd) (abxd, abvd)로 총 3개이다. 문제풀이 처음에는 바로 백트래킹의 풀이 방법이 떠올랐다. (여기까..
알고리즘 & 자료구조/Union-Find(분리집합) [백준] 공항_10775 문제 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 개요 문제에서 눈에 띄는 문장은 \(i\)번째 비행기를 1번부터 \(g_i\)(1 ≤ \(g_i\) ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려하고 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다는 것이다. \(i\)번째 비행기 마다 \(g_i\)값이 입력 되는데 입력값 이하 번호의 게이트에만 도킹을 할 수 있다는 것이다. 그리고 도킹 가능한 최대 비행기 수를 구해야 한다..
알고리즘 & 자료구조/Topology(위상정렬) [백준] 게임 개발_1516 문제 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 개요 문제를 먼저 읽어보면 눈에 띄는 문장은 최소 시간을 계산해야 한다는 것이고 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다는 것이다. 이는 Topology(위상정렬)의 전형적인 문제 스타일이다. 위상정렬 알고리즘을 요약하자면 그래프의 Indegree가 0인 노드를 그래프에서 제외시키는 과정을 반복적으로 수행하면서 결국에는 그래프 전체 노드를 지우게 되는 방식으로 문제를 해결하는 알고리즘이다. 이 때 그래프는 사이클(Cycle..

티스토리툴바