가면 뒤의 기록

안녕하세요. BlockDMask 입니다.오늘은 codeground 두번째 문제 '하노이 타워'를 풀어보았습니다.0. 제목코드그라운드 하노이 타워CodeGround Hanoi tower1. 문제설명세개의 타워가 있고첫번째 타워에 서로 다른 접시 N개가 쌓여있습니다. 첫번째 타워에 놓여있는 모든 접시를 세번째 타워로 옮기고자 할때, 접시를 옮기는 순서를 출력하라.접시는 한 번에 하나만 옮길 수 있고, 한 타워의 맨 위 접시를 다른 타워의 맨 꼭대기에 올릴 수 있다.큰접시 위에 작은접시가 올라가야만 한다. (작은 접시위에 큰접시 올라오는것 불가능)2. 풀이과정알고리즘 수업을 들었던 사람은 재귀 함수 파트에서 꼭 한번은 배웠던 하노이 타워(Hanoi Tower) 문제입니다.유명한 만큼 설명은 생략하겠습니다. 3..

안녕하세요. BlockDMask 입니다. 오늘은 간단한 정렬 알고리즘 중에 삽입 정렬 (Insertion Sort) 에 대해서 알아보겠습니다. 이상한 곳이 있으면, 댓글로 말해주시기 바라겠습니다.댓글을 보고 고치도록하겠습니다. 따끔한 지적 부탁드리겠습니다. 0. 원리Insertion Sort 는 말 그대로 '삽입' 꽂아 넣는 정렬입니다. 자신보다 앞의 원소가 큰지 작은지 비교를 하여서 자신의 위치를 찾아서 '삽입' 하는 정렬입니다. 앞의 원소를 비교해야 하기 때문에 arr[1]~arr[n] 까지 진행합니다. (두번째 원소인 arr[1] 부터 시작.) 삽입을 하면 데이터가 하나씩 밀려야 하기 때문에 배열이 길어질수록 효율이 떨어집니다. 그림을 통해서 과정을 살펴 보겠습니다. (오름차순을 기본으로 하겠습니다..

안녕하세요. BlockDMask 입니다.오늘은 새로운 알고리즘 문제 사이트 코드 그라운드(codeground)를 발견하여서 여기 문제를 풀어 보았습니다. 0. 제목코드그라운드 극단적인 수.codeground 극단적인 수.1. 문제설명4와 7로만 이루어진 숫자셋이 있다고 생각.K가 들어오면 K 번째 숫자를 출력.첫쨰줄에 1 4,7 법칙으로 바꾸어 주는 겁니다.2의 배수이면 7이 되고, 그렇지 않으면 4가 됩니다.여기서 중요한게 있습니다.표를 보게되면2번째 표를 보면1, 3, 7 일때 4, 44, 444 가 됩니다. (7 - 1 ) /2 = 3 (3 - 1) /2 = 1 이런식으로 단위가 증가하는 것을 볼수 있으며10진수에서 2진수로 변환하는 것 처럼 나머지를 이용하여 각 자리의 숫자를 구하고 역순으로 출력..

안녕하세요 BlockDMask 입니다.오늘은 Container Adapter (stack, queue, priority_queue) 중 마지막 priority_queue 에 대해 정리해보겠습니다. 0. priority_queue container우선순위 큐를 구현한 것 입니다. priority_queue container 는 vector, deque container 와 붙어서 사용이 가능합니다. (list 불가능) 내부적으로는 에 있는 힙 관련 함수들을 사용하여 구현되어있습니다. 내부구조 default 는 vector container 기반으로 설정되어 있습니다. 정렬기준 default는 내림차순(less) 기반으로 설정 되어있습니다.1. priority_queue container 사용법 헤더파일 안..

안녕하세요. BlockDMask 입니다.오늘의 문제를 포스팅 해보겠습니다. 클라이밍 하고와서 손이 부들부들 떨리는데;; 24시가 되기전에 올려야하니, 샤워도 안하고 폭풍 포스팅을 해보겠습니다.소수를 구하는 문제인데;; 에라토스테네스의 체 (소수 구하는 방법) 방법을 이용하여 풀어야하는 문제입니다.0. 제목백준 1929 소수 구하기BOJ 1929 소수 구하기1. 문제설명 1 그러면 2의 배수는 소수가 아니다. -> 지운다. [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20] 3) [3]는 소수이다. -> 그러면 3의 배수는 소수가 아니다. -> 지운다. [1], ..

안녕하세요! BlockDMask 입니다.오늘은 Container Adapter (stack, queue, priority queue)중 두번째인 queue container adapter에 대해 정리해보겠습니다. 0. queue containerFIFO (First in, First out) 방식으로 동작 됩니다. queue container는 deque와 list container 에 붙어서 사용 가능합니다. (vector container 불가능.) vector container가 불가능한 이유 : queue 자료구조 특성상 뒤에서 삽입하고 앞에서 빼야하는데(FIFO) vector는 앞에서 빼는 동작을 지원해 주지 않기 때문입니다. 내부적으로 deque, list container 로 구현이 되어있습..

안녕하세요. BlockDMask 입니다.오늘은 Container Adapter (stack, queue, priority_queue) 중에 stack container 에 대해 알아보겠습니다.다들 stack의 동작 원리나 구조는 아신다고 생각하고 포스팅 하곘습니다.0. stack containerLIFO(Last in First out) 방식. stack container adapter는 vector, deque, list container에 붙어서(기반으로) 사용이 가능합니다. 내부적으로는 vector, deque, list container의 구조로 구현이 되어있되, stack이라는 포장지로 잘 감싸서 stack과 같이 작동하도록 멤버 함수 등을 지원해 주는 것 입니다. default는 deque c..

안녕하세요!! BlockDMask 입니다.오늘의 문제 포스팅 하겠습니다.0. 제목백준 1181 단어정렬BOJ 1181 단어정렬1. 문제 설명 N개의 단어가 들어오면 1) 길이가 짧은순2) 길이가 같으면 사전순으로 정렬하여 출력하는 문제입니다.(단어는 소문자만 들어옵니다)(중복 제거 해야합니다.) 2. 풀이 과정 처음에는 vector container를 이용하여서,sort 알고리즘을 이용하여 정렬을하고unique 알고리즘을 이용하여 중복을 제거한 후 iterator(반복자)를 이용하여 출력하는것으로 문제를 풀었습니다. 그런데 다른사람과 비교했을때, 걸린 시간과 메모리량이 큰 것을 보고.어떻게 줄인걸까 생각을 해봤습니다. 그래서.총 4가지 방법으로 문제를 풀어봤습니다.T1) 방식이 제가 처음에 문제를 푼 방..

안녕하세요. BlockDMask 입니다.이번 포스트는 7월 20일짜 커버입니다.0. 제목 백준 1475 방 번호BOJ 1475 방 번호1. 문제설명 숫자가 1,000,000보다 작은 자연수가 입력이 되면,그것을 인식하기위한0~9가지의 열가지 숫자가 있는 플라스틱 숫자 셋트가 몇개가 필요한지.9는 뒤집어서 6으로 사용 가능하다. 2. 풀이과정 총 3가지 방법으로 풀어봤습니다. T1) 입력을 int 타입의 변수로 받고 배열을 이용하여 계산 한 경우 T2) 입력을 int 타입의 변수로 받고 STL map 컨테이너를 이용하여 계산 한 경우 T3) 입력을 string 타입으로 받고 계산 한 경우 3. 코드 T1) 입력을 int 타입의 변수로 받고 배열을 이용하여 계산 한 경우123456789101112131415..

안녕하세요. BlockDMask 입니다. 오늘의 포스팅을 시작하도록하겠습니다.오늘은 기본 스택을 구현하는 문제입니다.C, C++ 두가지를 이용하여 풀었습니다.0. 제목백준 10828 스택BOJ 10828 스택1. 문제설명 정수를 저장하는 스택을 구현하는 문제입니다. push N : 정수 N을 스택에 넣습니다.pop : 스택의 맨 위의 정수를 빼고, 출력. 없는경우 -1 출력.size : 스택의 정수의 개수 출력.empty : 스택이 비어있으면 1, 아니면 0 출력.top : 스택의 가장 위의 정수를 출력, 없는경우 -1 출력 2. 풀이과정 C++ 은 STL 에서 stack이 구현 되어있기 때문에 구현되어있는 stack을 이용하였고, C는 직접 구현을 했습니다. 3. 함수설명 C++의 stack 의 멤버인..

안녕하세요. BlockDMask 입니다.비가 추적추적 내리는 월요일이네요. 오늘의 문제를 포스팅 해보겠습니다.0. 제목BOJ 11050 이항계수 1백준 11050 이항계수 1 C++ 이용해서 풀었습니다.1. 문제 설명 자연수 N과 정수 K가 주어졌을때, 이항계수 를 구하는 문제입니다. 2. 풀이 과정 이항계수( binomial coefficient ) 는 경우의 수를 계산할때 사용하는 것으로 알고있습니다.n개의 서로다른 것 들 중에서 k 개를 선택하는 것의 조합(combination)의 경우의 수를 구하는 것입니다. 는 로 나타내고 이는 으로 나타낼 수 있습니다. 팩토리얼(Factorial)은 반복문과 재귀 두가지 방법으로 표현 할 수 있기 때문에 두가지 방법 모두를 사용하여 풀어보았습니다. 3. 함수 ..

안녕하세요, BlockDMask 입니다. 오늘은 정렬 알고리즘 중에 버블 소트 (Bubble Sort)에 대해서 알아보도록 하겠습니다. 앞으로 제가 아는 sort들을 포스팅 해볼 예정입니다 버블 정렬 - bubble sort 삽입 정렬 - insertion sort 선택 정렬 - selection sort 퀵 정렬 - quick sort 병합 정렬 - merge sort 기수 정렬 - radix sort 이 순서대로 정렬 포스트를 진행 해 보도록 하겠습니다. 0. 원리Bubble Sort는 말 그대로 거품처럼 동글동글 하면서 sorting을 합니다. 거품을 연상하시면 쉬울 겁니다. 두 인접한 원소를 비교하는 정렬입니다. 오름차순으로 정렬을 한다고 했을때, 처음 한 바퀴를 돌게 되면 맨 뒤에 있는 인자가 ..

안녕하세요, BlockDMask 입니다.오늘은 연관 컨테이너(Associative container) 중 multimap 에 대해서 알아보도록 하겠습니다.multimap은 map과 거의 동일하지만 딱 한부분 만 다릅니다.key값이 중복 가능하다.map에 대한 자세한 정보는 [바로가기] 에 있습니다. 1) multimap containerAssociative : 노드 기반으로 구현된 Associative Container 에 속합니다. Ordered : Key, Value 값이 삽입될때 정렬이 되면서 삽입됩니다. (항상 정렬되어있는 상태 입니다) Map : 각각의 Key는 하나의 Value 에 mapping 됩니다. (pair 객체를 이용하여 key, value를 묶습니다.) Multiple equival..

안녕하세요 BlockDMask 입니다.문자와 아스키 코드를 이용하는 문제입니다.최근 공부중인 STL을 사용해보았습니다.0) 제목BOJ 백준 1157번 "단어 공부" 문제입니다.C++ 을 이용하여 풀었습니다.1) 문제설명 알파벳이 대소문자 구분없이 쭉~~~! 주어지면그중, 가장 많이 쓰인 알파벳이 무엇인지 알아내는 문제.단, 대소문자 구분 없음.가장 많이 쓰인 알파벳을 대문자로 출력.만약 가장 많이 쓰인 알파벳이 여러개 라면 "?" 출력. 2) 풀이과정 STL에서 container를 요즘 공부하고있기 때문에, 이 문제를 보자마자 알파벳 및 횟수를 map의 로 만들면 되겠다라는 생각이 들었습니다. map을 이용하여 알파벳, 횟수를 map로 묶었습니다.대문자를 출력하기 위해서 소문자가 들어왔을때, 아스키 코드..

안녕하세요! BlockDMask 입니다. 오늘 푼문제는 버블정렬(Bubble Sort)과 삽입정렬(Insertion Sort)를 복습하는 마음으로 푼 문제였습니다. 버블정렬과 삽입정렬 두 방법 으로 문제를 풀었습니다. 0) 제목 BOJ 2577 번 문제 " 수 정렬하기 " 입니다. C++ 을 이용해서 풀었습니다. 1) 문제 설명 숫자 n 이 입력되면 그 n 개의 갯수만큼 숫자를 입력 받습니다. 그 숫자들을 오름차순 순으로 정렬하여 출력합니다. 2) 풀이과정 bubble sort 와 insertion sort 두가지 다 이용해서 풀어보았습니다. 3) 함수설명 null 4) 코드 -> Bubble Sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..