패스트터틀

2812번: 크게 만들기 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 예제 입력 1 복사 4 2 1924 예제 출력 1 복사 94... www.acmicpc.net 쉬운것 같으면서도 복잡해보이는 문제이다. 푸는법은 깨달았으나 머라고 해야할까 하나하나 따지는게 복잡한 문제다. 스택을 사용하여도 되고 사용하지 않아도 되지만 스택 라이브러리를 끌어다쓸경우 값을 다시 꺼내와서 뒤집어야 한다. 그러므로 그냥 ..

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호 www.acmicpc.net 오름차순으로 정렬하고 따져보니 너무 복잡하다고 생각이들어서 답이 안나오길래 결국 해답을 찾아보았다. 우선 개념에 대한설명은 아래 긴글을 참고 두번째 블로그는 해당개념을 사용하여 코딩한것이다. https://..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - 개관 - 반복문 - 선형 시간 알고리즘(이동평균) 4.11 개관 시간과 공간은 반비례적인 관계이다. 알고리즘은 속도가 빠른것이 중요하다. 4.12 반복문 알고리즘의 수행시간을 지배하는 것은 바로 반복문이다. 4.2 선형시간 알고리즘(이동평균) 말이 어렵다. 단순히 다음과 같이 설명할수있다. 이 간단한걸 뭐그리 복잡하게 설명해놓는 사람들이 많은지 모르겠다 ㅡㅡ M이 3일경우라면 위와같이 앞의 3개의 평균이다. 최소 3개는 있어야 평균을 구할수있으니 3번째부터 시작하는것이다. 책에 나온것을 요약해서 설명하자면 본래 코드 4.3 에 구현된것은 무식하게 계산한거지..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 www.acmicpc.net 1. N개의 책이 번호로 매겨져있다. 2. 학생은 a,b 사이의 책중 하나를 책에 준다. 3. 첫재줄 = 테스트케이스 둘째줄 = N,..

https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 1. 1열에서 시작해서 마지막열까지 간다. 2. 대각선 위, 오른쪽, 대각선 아래로 이동가능하다. 3. 최대한 여러개를 설치해야한다. 4. ..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 www.acmicpc.net 생각의 흐름 : 우선 다음과 같은 가정을 해보고 문제를 풀이해본다. 보석의 가치를 최대한 높이려면 다음의 조건을 만족해야 된다라고 가정..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - 힙 - 우선순위큐 - Comparable - 힙 heap은 트리이다. 가장 큰 원소를 찾는데 최적화된 형태의 이진트리이다.(minheap,maxheap은 연산자 차이밖에없음) 추가와 꺼내는 연산 모두 O(logN) 에 수행한다. 힙은 대부분의 프로그래밍 언어의 표준 라이브러이에 포함되어 있기 떄문에, 직접 구현할 일은 거의 없다. 힙은 다음과 같은 특징은 지녔다. - 부모노드와 자식관계만 적용되며 부모노드는 자식보다 커야하며 자식간의 관계는 생각하지 않는다. - 마지막 레벨을 제외한 모든 레벨이 노드가 꽉 차 있어야 한다. - 마지막 레벨에 노드가 있을 때..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - 책의 개관 - 우리나라 개발의 문제점 - 프로그래밍 대회에서 배울수 있는것 - 대회 - 대회준비 - 문제 해결 개관 - 문제 해결 전략 - 코딩의 중요성을 간과하지 말라 - 자주 하는 실수 - 디버깅과 테스팅 - 변수 범위의 이해 - 실수 자료형의 이해 - 더 읽을거리 - 책의 개관 현대의 컴퓨터 과학 교육이 실제 학문이 발전하는 방향의 반대 순서로 이루어져 있기 때문에 응용능력을 기를수 없다. 그래서 '잘하는 사람과 못하는 사람의 생산성이 스무 배'라는 말이 나온다. 결국 이 문제는 직관의 의존하는 문제로 이어지게 된다. 말이 좋아서 직관이지 실제로는 때..