IT 방랑기

1. Convex hull Convex Hull이란, 점들로 구성된 Set을 모두 포함하는 외각 점들의 집합이다. 아래의 그림을 보자. 출처 : 위키피디아 검은 점들로 구성된 집합 `S`에서 어느 점을 선택하더라도, 파란색 선안에 포함되는 것을 알 수 있다. 이 파란색 선을 어떻게 찾아야 할까? 2. How to find convex hull Convex Hull을 찾는 가장 간단한 방법은 각 점마다 모든 점들을 순회해서 가장 외각의 것을 선택하는 것이다. 하지만 이렇게 접근한다면, 결국 `O(n^2)`이 되어서 원하는 작업을 원할히 할 수 없다. 사실 모든 점을 순회한다는 것은 가장 외각의 점을 찾기 위함이다. 따라서 이 부분을 더욱 쉽게 만들어 준어야 한다. 그런 방법들 중에서도, 외적을 이용한 `C..

1. Convex Set Convex Set이란, 집합 `S`에 포함된 어느 두 점 `p`, `q`를 선택하여 점들을 연결하는 직선을 모두 포함하는 덩어리를 의미한다. 즉, 특정 점들의 집합이 아닌, 이를 감싸고 있는 공간이라고 생각하면 된다. 아래의 그림 3개를 보자 . 그림 1, 출처 : 위키피디아 그림 2, 출처 : 위키피디아 첫번째 그림은 어느 두점 `x`,` y`를 선택하더라도 포함된다. 따라서 convex set이다. 반면 그림 2는 직선중 일부가 Set에 포함되지 않는다. 따라서 Convex Set이 아니다. 2. Convex Set의 Intersection Convex Set `A`와 `B`가 있고, 이 둘 사이의 교집합은 Convex Set일까? Yes, `A`와 `B`의 교집합이라더라도..

1. Visual Studio 2015와 OpenGL 사용 아래 글 참조 https://jcdgods.tistory.com/374 [C/C++] 간단하게 Visual Studio 2015에 C++ OpenGL 설치하기 1. OpenGL 다운로드 OpenGL Windows 압축 파일 다운로드 OpenGL 홈페이지에서 윈도우 C++용 GLUT을 다운 받아서 원하는 위치에 압축을 푼다. 그냥 D드라이브가 편하니까 D:\glut에 저장하였다. 2. Visual Studio.. jcdgods.tistory.com 2. 코드 https://github.com/ChangdaeJeong/triangluation-openGL 위의 깃허브 참조 ChangdaeJeong/triangluation-openGL trianglu..

1. OpenGL 다운로드 OpenGL Windows 압축 파일 다운로드 OpenGL 홈페이지에서 윈도우 C++용 GLUT을 다운 받아서 원하는 위치에 압축을 푼다. 그냥 D드라이브가 편하니까 D:\glut에 저장하였다. 2. Visual Studio 프로젝트 만들기 비주얼 스튜디오를 켜고, Windows 32 console 프로젝트를 하나 생성한다. 그런 다음 솔루션 탐색기에서 해당 프로젝트를 우클릭하여, 속성으로 들어간다. 그런 다음 속성 페이지에서 우측 상단에 위치한 구성 관리자를 연다. 그런 다음 활성 솔루션 구성을 클릭하여, 새로 만들기를 한다. 새로 만들 솔루션 구성 이름은 아무거나, OpenGL_debug로 만들었다. C/C++ 수정 C/C++ 일반탭 또는 VC++ 디렉터리에 들어가서 포함 ..

컴퓨터 알고리즘에서 플로이드 혹은 플로이드 와샬 알고리즘은 임의의 시작점과 종료점간의 최단 경로를 구하는 알고리즘이다. [다익스트라]와는 다르게 모든 정점에 대하여 한번에 경로를 구할 수 있는 장점이 있다. 하지만 최단 경로를 구하기 위해서는 정점의 개수 N에 대하여 O(N^3)의 시간 복잡도를 가지게 되므로, 실제 문제에 적용할 수 있는 N의 크기는 1초 1억(1e8) 대비하여 N이 100정도이다. 만약 N j 경로중 가까운 것을 최단 경로로 저장한다. 코드의 경우 아래와 같이 나타나게 된다. for(int k = 1; k

1. 문제 문제 n(1≤n≤100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최소값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비..

이번 포스트에서는 파이썬과 PILLOW 라이브러리를 이용하여, 백그라운드 이미지에 글자 추가하여 저장하는 프로그램을 담아볼 예정이다. 예전에 로또 당첨 정보를 이미지화하여 출력하는 프로그램을 작성한 적이 있었는데, 이번에는 내 블로그의 BOJ 위키 포스트에 대표 이미지를 문제 번호를 포함하여 출력하여 사용하려고 작성한다. 전체적인 흐름은 1) 백그라운드 이미지 읽기, 2) 이미지에 포함될 글자 생성, 3) 글자 위치 지정, 4) 백그라운드 이미지 + 글자를 파일로 저장하는 과정을 거친다. 이를 위해서는 PIL 라이브러리가 필요하다. 해당 라이브러리는 아래의 명령을 통하여 설치할 수 있다. sudo apt-get install pillow 정상적으로 Pillow 라이브러리를 설치하였다면, 아래의 코드를 P..

1. 문제 문제 두 개의 바구니에 사과와 오렌지가 있다. 첫 번째 바구니에는 사과 A개와 오렌지 B개가 있으며 두 번째 바구니에는 사과 C개와 오렌지 D개가 있다. 당신은 한 바구니에 있는 과일 하나를 집어서 다른 바구니로 옮길 수 있다. 이런 식으로 과일을 옮길 때, 한 바구니에는 사과만 있게 하고 다른 쪽에는 오렌지만 있게 하려고 한다. 앞서 말한 조건을 만족하도록 과일을 옮길 때, 과일을 옮기는 최소 횟수를 구하는 프로그램을 작성하여라. 입력 첫 번째 줄에는 첫 번째 바구니에 있는 사과와 오렌지의 수 A, B가 주어진다. (0 ≤ A, B ≤ 1,000) 두 번째 줄에는 두 번째 바구니에 있는 사과와 오렌지의 수 C, D가 주어진다. (0 ≤ C, D ≤ 1,000) 출력 사과와 오렌지를 옮기는 최..

1. 문제 문제 문제는 매우 간단하다. N을 N번 출력하는 프로그램을 작성하여라. 다만, 답이 길어지는 경우 답의 앞 M자리만 출력한다. 입력 첫 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 2016) 출력 N을 N번 출력한다. 만약 답이 길어지면 답의 앞 M자리를 출력한다. 예제 입력 복사 20 16 예제 출력 복사 2020202020202020 힌트 [출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음] 2. 해답 이 문제는 기본적인 언어 활용 능력을 묻는 문제로, 입력 받은 숫자 n을 n번 출력하되, 최대 m개의 글자만 출력하는 것이다. 이때 숫자 n을 문자열로 받게되면, m개의 글자까지만 출력하는 것을 손쉽게 제어할 수 있다. #inclu..

1. 문제 문제 고려대학교에 입학한 새내기 호돌이는 안암역을 지나다가 한 붕어빵 장수를 만났어요. “안녕, 안녕, 안녕하십니까, 아저씨! 붕어빵 두 개 주세요.” “안녕을 세 번 외쳤으니 붕어빵 세 개!” 붕어빵 두 개의 값을 내고 세 개를 받은 호돌이는 기분이 좋았어요. 호돌이가 붕어빵 하나를 꺼내어 한 입 물었는데…. 너무 뜨거워서 그만 붕어빵을 떨어뜨리고 말았어요ㅠㅠ 붕어빵은 자유 낙하운동을 하면서 땅에 떨어졌는데 신기하게도 좌우가 뒤집힌 모양으로 착지했답니다. 호돌이가 붕어빵을 한 입 물기 전의 모양이 입력으로 주어지면, 땅에 떨어졌을 때에는 어떤 모양일지 출력하세요. 입력 첫째 줄에는 두 개의 정수 N과 M(0≤N,M≤10)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 붕어빵의 모양이 주어집니다..