Huilife

Priority Queue는 heap의 대중적인 응용 중 하나이다. Priority Queue에도 heap과 같이 max-priority-queue와 min-priority-queue 두 가지가 있다. 이 글에서는 max-heap을 기반으로 하여 max-priority-queue를 구현하는 프로시저에 대해 초점을 맞춘다. Priority Queue의 정의 Priority Queue는 key라는 값을 가진 원소들의 집합 S를 다루기 위한 자료구조이다. Priority Queue의 응용 Priority Queue는 다양하게 응용될 수 있다. max-priority-queue 공유 컴퓨터에서 작업 순서를 계획하는 것 min-priority-queue 사건 반응형 시뮬레이터 Priority Queue의 기본 프..

Quick Sort의 특징 내부 정렬을 이용한 방법이다. 분할 정복을 이용한다. 분할 배열 $A[p, ..., r]$ 을 두 개의 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 로 분할한다. 부분 배열 $A[p, ..., q-1]$ 에는 $A[q]$ 보다 작거나 같은 원소를, $A[q+1, ..., r]$ 에는 $A[q]$ 보다 크거나 같은 원소를 배치한다. 정복 quick sort를 재귀 호출해서 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 를 정렬한다. 결합 1, 2의 과정을 통해 부분 배열이 이미 정렬되어 있으므로 따로 합치는 작업이 필요하지 않다. quick sort는 기본적인 quick sort 방법과 랜덤화 기법을 사용하여 모든 입력에..

아마도 소프트웨어 혹은 컴과 전공생이라면 아직 찌들지 않은 푸릇한 1~2학년 시절 자료구조나 이산수학을 배우면서 행렬(배열)의 row-major, col-major를 눈 깜짝할 새 배우고 지나갔을 것이다. 그것이 어언 몇 년이 지나 지금이 되면.. 그게 뭔지는 대충 아는데 왜 배웠는지 기억이 나는 새럼 손 드세요. 손 드신 분들은 그대로 가슴에 손을 얹고 양심에게 여쭈어보시면 됩니다. 정녕 잘 기억이 나는가! 암튼 이번 포스트에서는 행렬(배열)의 row-major, col-major의 차이점과 중요성에 대해서 알아보도록 하자. row-major, column-major가 뭔데? 얘네들은 2차원 이상의 배열을 저장할 때 적용이 되는 것들이다. 어떤 배열을 2차원으로 한정하여 생각해 보자. 아무리 배열이 2..

부제: Custom sort의 늪에 빠진 꼬부기... 이제 탈출 각 보이나? 이전에도 한번 custom sort의 늪에 빠져서 @mttw2820에게 궁금증을 쏟아낸 적이 있었다. 그때 해결한 궁금증은 맽튜가 정리한 이곳에서 확인하실 수 있음. 아무튼, 지난번에는 functional 함수 객체 (less 이런 애들), bool compare 함수 정의, operator < 오버로딩 등에 대해서 알아보았다. 오늘의 문제는 priority_queue에서 발생하였다. 나는 보통 문제를 풀 때, 구조체를 만들어서 사용하는 것을 선호한다. 뭔가 깔꼼쓰한 모양새랄까. 그래서 sort 등을 할 때도 compare 함수를 만들어서 사용할 수 밖에 없는 경우가 많은데, 오늘은 priority queue를 정렬하는데 문제가..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1차 시도- 맞았습니다 #include #include using namespace std; int compare(const void* a,const void *b) { int num1 = *(int *)a; int num2 = *(int *)b; if(num1num2) return 1; return 0; } int main() { int n; cin >> n; int num[n]; for (int i..

https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 1차시도 - 틀렸습니다 #include using namespace std; int main() { int a, b; cin >> a >> b; cout > a >> b; cout

https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문 www.acmicpc.net 2019-03-30 1차시도 맞았습니다. #include using namespace std; int main() { int N,..

VSCode를 사용하다가 기억해야할 만한 것들을 (내가 보기 위해) 적어둔 글이다. 1. VSCode안에서 Terminal 사용하기 VSCode는 기본적으로 PowerShell을 사용한다. 하지만 사용자에 맞춰 어떤 것을 사용할지 고를 수 있다. 파일>기본설정 에서 terminal을 검색하고, 스크롤을 좀 내리면 이런 애가 나온다. 나는 cmd가 편해서 cmd로 바꿨다. 어떤 애를 사용할건지 해당 파일의 경로를 넣으면 되는데, 이건 다음의 VSCode 공식 문서를 참고하라. https://code.visualstudio.com/docs/editor/integrated-terminal#_configuration Integrated Terminal in Visual Studio Code Visual Stud..

^^... 고난의 길 시작이다. 작년에 C/C++ 설정하다가 진짜 화딱지가 엄청 났었는데... 그걸 기록을 안해놔서 다시 그 길을 걸을 수도 있다. 젭알 한번에 되도록 해주십쇼 선생님. 시작해 보도록 하자. 먼저 C/C++ 설정을 하다 보면 잘 되는지 안되는지 테스트를 해야 하므로 작업을 할 폴더를 하나 열도록 하겠다. 현재 아무 폴더가 안열려있다면 폴더 열기 버튼을 누르면 된다. 폴더가 열려있는데 새로 열고 싶다면 위의 메뉴를 이용하라. 이제 폴더를 열었다면 우리가 할 일은 코드를 작성하는 것이 아니라! 컴파일러부터 설치하는 것이다. 편집기는 기본적으로 디버깅이나 컴파일, 실행 기능을 제공하지 않는다. 확장을 설치하여 해당 기능을 하도록 설정하지 않으면 그냥 좀 예쁘고 깔쌈한 메모장이랑 다름 없다는 말..

한 학기에 한 번씩 하는 것 같은 노트북 초기화.. 이번 학기도 어김없이 초기화를 했다. 초기화 하고 나서 가장 두려운 것은 Visual Studio Code의 모든 설정을 복원하는 것이다. 아직 VSCode에 익숙하지 않아서 다 너무 어렵다 주륵주륵 그래서 이번 초기화부터는 나중에 초기화를 하더라도 이 방법 그대로 설정을 복원할 수 있도록!!!!!!! 기록을 남기려고 한다. 나같이 vscode 설정에 허덕이는 쪼렙 사용자들이 보고 도움을 받을 수 있도록...ㅎ....그냥 사실 나한테 도움이 되도록..ㅎ... 그럼 이제 시작해 보자 (1) VSCode 다운로드 https://code.visualstudio.com/download Download Visual Studio Code - Mac, Linux, ..