코딩동링딩동

https://www.acmicpc.net/problem/23971 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB113975328475048.489%문제2021년 12월, 네 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 오프라인 대회를 대비하여 강의실을 예약하려고 한다.강의실에서 대회를 치르려면 거리두기 수칙을 지켜야 한다!한 명씩 앉을 수 있는 테이블이 행마다 W개씩 H행에 걸쳐 있을 때, 모든 참가자는 세로로 N칸 또는 가로로 M칸 이상 비우고 앉아야 한다. 즉, 다른 모든 참가자와 세로줄 번호의 차가 N보다 크거나 가로줄 번호의 차가 M보다 큰 곳에만 앉을 수 있다.논문과 과제에 시달리는 성우를 위해 강의실이 거리두기 수칙을 지키면서 최대 몇 명을 수용할 수 있는지 구해보자.입력H..

운영체제- 하드웨어 위에 설치된 하드웨어 계층과 다른 소프트웨어 계층을 연결하는 소프트웨어 계층- 컴퓨터 시스템의 자원을 관리하고, 사용자가 컴퓨터를 활용할 수 있는 환경 제공- 사용자와 컴퓨터 간 인터페이스를 제공해 사용자가 컴퓨터를 편리하게 사용할 수있는 환경 제공   ex) 윈도우, 맥, 리눅스, 유닉스 등 운영체제 목적os : 한정된 컴퓨터 자원을 관리하는 시스템 1. 처리 능력 향상 : OS는 자원 관리를 통해 일정 시간 내에 시스템을 처리하는 일의 양을 향상 시킴2. 반환 시간 : OS는 사용자가 시스템에 요청한 작업을 완료할 때까지 소요되는 시간을 단축시킴3. 사용가능도 향상 : 사용가능도는 시스템 자원을 얼마나 빨리 제공할 수 있는가를 의미.                           ..

https://www.acmicpc.net/problem/1920시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초128 MB296064942866216830.488%문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.출력M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면..

최단 거리 알고리즘정점 간 최단 거리를 구하기 위한 알고리즘다익스트라 알고리즘, 벨만-포드 알고리즘- 특정 정점에서 다른 정점들까지의 최단 거리를 구함플로이드-위셜 알고리즘- 모든 정점 간 최단 거리 구함다익스트라 알고리즘간선의 가중치가 음수가 아닌 경우 특정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘A노드에서 출발하여 F노드로 가는 최단 경로를 구하는 문제를 다익스트라 알고리즘을 활용한다.아래의 각 데이터의 의미를 보며 살펴보자S = 방문한 노드들의 집합d [N] = A → N까지 계산된 최단 거리Q = 방문하지 않은 노드들의 집합확인되지 않은 거리는 전부 초기값을 무한으로 잡는다 ex) INF출발지와 출발지의 거리는 확인해 볼 필요도 없이 당연히 0 값을 가진다는 것을 알 수 있다. 출발지를 ..

신장 트리 : 그래프의 모든 정점을 포함하는 트리 최소 신장 트리(MST, Minimum Spanning Tree)가중치가 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리프림 알고리즘 ( 그리디 알고리즘)그리디 알고리즘탐욕 알고리즘이라고도 함각 단계에서 최선의 선택이 모여 전역으로 최적의 해결 방안을 찾는 방식그리디 알고리즘은 다음 2가지 조건을 만족해야함1. 앞에서 선택한 결과가 나중의 선택에 영향을 주지 않아야 함2. 지역적인 문제에 대한 최선의 선택이 전역적인 문제에 대해서도 최적의 해여야 함 - 임의의 정점을 시작으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식- 현재 트리에 포함된 정점과 연결된 간선 중 가중치가 가장 작은 간선으로 연결된 정점을 선택하는 과정을 반복하며  모든 정점이..

계수 정렬 | O(n+k)데이터의 개수를 정렬하는 방식- 계수 정렬은 데이터의 범위가 0 또는 양의 정수여야함