문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 ...

개요 여러 정점과 간선들로 이루어진 양방향 그래프가 있을때 부분 그래프가 최소한의 간선들로 이루어 졌을때 Spanning Tree, 신장트리라고 한다. 즉 Spanning Tree는 내부에 사이클이 없는 그래프를 의미하는것이다. 사이클이 생기는 순간 불필요한 간선이 하

문제 설명 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다...

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지

명진이와 동휘가 숫자 맞추기 게임을 한다.게임 방법은 명진이가 0 에서 9 사이의 숫자를 하나 생각하면, 동휘가 질문을 통해 명진이가 생각한 숫자가 어떤 것인지 맞추는 것이다.동휘는 명진이가 생각한 숫자를 맞추는 데 총 N번의 질문 했다.동휘는 질문을 한 번 할 때,

이번에는 Server프로그램에 맞춰서 Client프로그램을 만들어보자. 이번에도 아래의 5가지 단계를 거쳐서 코드를 짜게 된다. > 윈속초기화 -> 소켓생성 -> 통신 -> 소켓닫기 -> 윈속종료 먼저 필요한 라이브러리를 링크해주자. 또, 서버 프로그래밍에서 했듯이

C++의 windock2헤더파일 이용하여 간단한 채팅 프로그램을 만들어보았다. 가장먼저, 헤더파일과 ws2_32.lib 라는 라이브러리를 링크해주어야한다. 윈도우소켓의 통신 과정은 5가지과정을거친다. > 윈속초기화 -> 소켓생성 -> 통신 -> 소켓닫기 -> 윈속종

이전 포스팅에서 만든 초기버전을 수정하였습니다. 이제는 키 입력간격이 1.5초인 모든 입력을 한줄로 log.txt에 기록하고, 같은키의 여러번 눌림을 기록가능합니다. 아래는 전체 소스코드

이전에 게임을 하다가 문득 든 생각으로, 내가 컴퓨터를 쓰면서 가장 많이 사용하는 키는 무엇일까? 하는 생각으로 찾아보니, PC사용자의 모든 키보드 입력값을 중간에서 가로채는 행위로 소프트웨어방식의 키로거 프로그램이라는게 있었다. 하지만 이는 악용될 우려가있기에 그저

영상 > https://www.youtube.com/watch?v=ZqwfoMjJAO4&list=PLSlpr6o9vURx4vjomFuwrFhvhV1nhJ_Jc&index=23 이전에는 이미지파일을 출력해보았는데 이번에는 특정 모양을 생성해주는 shapes클래스를 작성해보았다. 이때 필요한 개념은 아래와 같다. 먼저 왼쪽과 같은 흰색 사각형은 내부적으로...

수열 arr의 모든 부분수열중 원소가 모두 증가하는 부분수열의 최대길이를 구하려는 문제가 있을때,단순히 전부 그리디방법으로 탐색시, N N회의 연산이 필요하나,DP를 이용하여 N N (1/2)로 절반으로 줄이거나BS(Binary Search)를 이용하여 N log

정렬된 자료를 절반씩 나눠가며 원소k의 위치를 찾는 탐색 알고리즘이다.그리디 방법으로 탐색을 진행하면 O(N)이 걸릴것을 O(log N)에 마칠 수 있기때문에, 이후에 다른 알고리즘등에서 재사용이 많이되는 기본 탐색 알고리즘이다.(정렬된 연속된 자료가 필요하다.)먼저

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 5

개요 수열 arr에서 연속되거나 그렇지않은 부분수열이 증가할때 해당 부분수열의 모든 원소의 합이 최댓값을 구하는 알고리즘이다. 최대 증가 부분수열 알고리즘이라고 한다. 구현 i보다 작은 j들을 하나씩 살펴보며, 현재 dp[i]값을 작성할것인데, 이때 arr[j]

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공

문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드...

문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000...

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 100...

개요 주어지는 2개의 문자열의 서로 공통인 부분수열중 길이가 가장 긴것의 길이를 찾는 알고리즘이다. 이때의 부분수열은 연속되지않은 부분수열도 포함하여 LCS를 찾게된다. 이번에 소개할 LCS알고리즘을 사용하면 두 문자열의 길이 N, M에따른 O(N * M)만에 LCS를 찾을 수 있다. 작동원리 LCS알고리즘을 설명할때 자주쓰이는 두 문자열 'ACAYKP'...