boj, 백준) 10217. KCM travel ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 2. 문제 개요 M원 이하로 사용하면서 도착지까지 갈 수 있는 최단 경로를 찾는 문제. 1원이든, M원이든 M원 이내에만 들면 되고 그중에서 최단 시간으로 갈 수 있는 경로를 찾자. 3. 문제 힌트 DP를 사용해야 한다. 경로를 찾을 때는 다익스트라 알고리즘(logn)으로 구현해서 사용해야 한다. 어떻게 DP를 적용할까? 점화식을 찾기에 앞서 왜 DP를 써야..
boj, 백준) 2931. 가스관 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/2931 2931번: 가스관 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. www.acmicpc.net 2. 문제 개요 가스를 M에서 Z로 옮기려고 파이프라인을 디자인하고 있다. 파이프의 종류는 다음과 같다. 파이프 라인의 설계를 마친 두 사람은 저녁을 먹으러 갔는데 그 사이 해커가 침입해 블록 하나를 지웠다. 지운 블록은 빈칸이 되어있다. 해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오. 3. 문제 힌트 맵의 총 크기는 25*25로 그렇게 크지는 않다. 어떤 파이프를..
boj,백준) 1039. 교환(C / C++)
1. 문제 링크 www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 개요 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1≤ i < j ≤ M 인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 그리디로 접근하려고 했으나..... 안 될 것 같다. 문제 유형을 보니 BFS..
[C++] 압축 프로그램 개발 (코드 O, 허프만 코딩, Huffman coding, 허프만 코드)
학부 저학년 때 개발했던 프로그램입니다. 그때는 성능보다는 개발을 우선으로 해서, 과제용으로는 충분할지 모르겠으나 어디 보여주기엔 좀 그래서... 외장하드에 묻어두다가 그래도 그때 개발했던 내용을 공유하고자 글을 씁니다. 그리고 그때 부족하다고 생각했던 부분들을 수정해서 성능도 훨씬 끌어 올렸습니다. 처음엔 C로 구현을 했으나, heap 같은 라이브러리를 사용하기 위해 C++로 구현했습니다. ( C에서 직접 구현해서 사용해도 괜찮습니다) 0. 주저리주저리 허프만코드를 사용해서 압축을 한 프로그램입니다. 결국엔 파일을 읽어서 빈도수를 구한 뒤 허프만 코드를 만들고, 1byte에 1bit씩 채워나가면서 프로그램을 압축하는 형식입니다. 프로그램은 압축, 압축해제 2개의 큰 부분으로 나뉩니다. 압축은 허프만트리..
boj, 백준) 20055. 컨베이어 벨트 위의 로봇 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 문제 개요 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 1번 칸이 '올라가는 위치' N번칸이 있는 위치를 '내려가는 위치'라고 하자. 로봇은 '올라가는 위치'에서만 올라가고 '내려가는 위치'에서만 내려간다. 로봇이 올라가는 곳은(놓거나 걸어서) 내구도가 1 감소한다. 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮..
boj, 백준) 20061. 모노미노도미노2 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 2. 문제 개요 및 풀이 kibbomi.tistory.com/172 boj, 백준) 19235. 모노미노도미노 ( C / C++ ) 1. 문제 링크 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙 kibbomi.tistory..