본문 바로가기

Programming

 (92)
백준 10989번 _ counting sort (c++) 문제: https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 우리가 아는 정렬알고리즘들로는 웬만하면 모두 메모리초과가 날 것이라고 감히 확신해본다. 10000이하의 수라고 했으니 short로 배열을 만든다해도 주어진 10,000,000개를 저장할 수 있는 배열만 만들어도, 대략 20Mb가 되어버린다. 애초에 메모리제한이 8Mb라는 건, 우리가 아는 배열에 저장해서 nlogn의 시간복잡도로 계산하는 그런 문제가 아니란 뜻! 그렇다면 해결책은 바로 counti..
[C++] 상속(Inheritance) 이 포스팅은 윤성우님의 열혈 C++ 프로그래밍 책을 기반으로 작성되었습니다. 이번에는 포스팅을 시작하기 전에 하나의 문제점을 제안하고 그에 대한 답안을 찾아가보고자 한다. Class Student가 있다. 이 Student 클래스의 멤버변수로는 이름, 나이, 학번, 전화번호 등 다양한 정보가 저장되어 있다. 그런데 문제가 생겼다. 교육과정의 문제로 이 Student 클래스를 학부생과 대학원생으로 나눠서 정의를 해야하는 것이다. 그리고 그 학부생과 대학원생에 따라 추가해야하는 멤버변수들이 꽤 생겨난 것이다. 그러면 우리는 여기서 학부생, 즉 Undergraduate 클래스와 대학원생, Graduate 클래스를 재정의해야할 것이다. 하지만 이 두 클래스는 분명 Student라는 공통분모의 멤버변수들이 많이 ..
[C++] Static 정적 변수. 이 포스팅은 윤성우님의 열혈 C++ 프로그래밍 책을 기반으로 작성되었습니다. 오늘은 static에 대해서 한 번 얘기해볼까 합니다. static은 크게는 다음의 용도로 사용됩니다. 1. 전역변수에서 static 선언된 경우. (c/c++) 2. 함수 내에서 static 선언된 경우. (c/c++) 3. 멤버 변수로 static 선언된 경우. (c++) 4. 멤버 함수로 static 선언된 경우. (c++) 5. const static 멤버 먼저 첫 번째의 경우부터 볼게요. 이 경우에는 static이 외부 파일의 접근을 막는 정보은닉의 역할을 합니다. 좀 더 자세하게 말하자면, 전역변수에서 static으로 선언이 되면, 해당 파일 내에서는 자유롭게 참조가 가능하지만 외부 파일에서 해당 파일을 불러와서 사용..
[C++] 복사생성자 / 깊은복사와 얕은복사 이 포스팅은 윤성우님의 열혈 C++ 프로그래밍 책을 기반으로 작성되었습니다. 디폴트 복사생성자의 생성 Polygon이라는 클래스가 있고 Square라는 객체를 생성한 뒤 Square1에 복사하려한다면 어떻게 하면될까? 직관적으로는 Square1 = Square이라고 하면 될 것 같은데.. 실제로 된다. class Polygon { private: int NumOfLine; int NumOfDot; public: Polygon(int line, int dot); ... }; int main(){ Polygon Square(4,4); Polygon Square1=Square; Polygon Square2(Square1); return 0; } 위의 코드는 실제로 대입연산을 하는 것처럼 멤버대멤버 복사가 일어..
백준 2798번 _ BlackJack 블랙잭 / Brute Force 브루트포스 (C++) 문제: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 필자는 호주워홀시절 카지노에서 블랙잭으로 꽤나 큰 돈을 잃어본 적이 있다... 또르륵.. 여튼 오늘도 각설하고, 또 백준이 블랙잭을..
백준 11729번 _ Hanoi / recursion 재귀 문제 (C++) 문제: https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 어제 새벽에 꽤나 기싸움 끝에 풀어냈던 문제이다. 하노이탑 문제는 재귀 관련된 문제 중에서 매우 유명하고 대표적인..
백준 1152번 string _ while문/cin EOF 연습 (C++) 문제: https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. www.acmicpc.net 이 문제는 c++에서 string을 어떻게 입력받는지를 아는지 모르는지에 따라 그 체감난이도가 매우 다를 것이다. 파이썬이용자라면 그냥 문자를 다 읽은 다음에 공백을 기준으로 split을 해야지! 라는 생각이 먼저 들 것 같다. 하지만 C++에서의 string은 문자열을 공백을 기준으로 입력받기 때문에, 단순히 몇번 입력받았는지만 count..
백준 1065 한수_ 함수(function)사용! (C++) 문제: https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 사실 굉장히 간단한 문제이면서, 동시에 함수를 연습해보기 좋은 문제이다. 문제의 핵심은 간단하다. 99까지는 모든 숫자들이 각 자릿수끼리 등차수열을 이룬다. (비교군이 없기 때문이다.) 1의 자리나 10의 자리까지 구현하려다보면 복잡해질 수 있지만 1-99면 그냥 그 숫자를 리턴하게 만들어준다. (편-----안) 하지만 100, 즉 ..

티스토리툴바