개발 노트

속도가 O(N * log N)이 나오는 퀵 정렬, 병합 정렬, 힙 정렬보다 빠르게 정렬하는 방법. 단 범위조건이 있어야 한다. 시간복잡도는 O(N)으로 매우 빠르다. 크기를 기준으로 갯수를 센 후 그 수 만큼 출력하면 된다. 크기가 한정되어 있는 배열만이 계수정렬을 사용할 수 있다는 특징이 있다. #include int main(void) { int temp; int count[6]; int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1}; for(int i = 1; i

힙 정렬은 빠른 알고리즘을 가지고 있다. 힙 정렬은 이진트리구조를 사용한다. 이진트리 구조(자식 노드가 2개 이하인 트리 구조) 완전 이진 트리는 루트부터 자식노드가 왼쪽부터 오른쪽으로 차례대로 데이터가 들어가는 구조이다. 힙 생성 알고리즘은 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 위치를 바꾼 뒤에도 자식이 존재하는 경우 계속해서 반복한다. 이 힙 생성 알고리즘의 시간복잡도는 높이와 같기 때문에 O(log N) 이다. 1. 배열에 그대로 삽입한다. 2. 앞의 1/2개만 확인한다.(소수점은 버림) 위의 그림에서는 7, 6, 5, 8까지만 본다. 3. 밑에서부터 자식과 확인하며 정렬한다. 1) 8은 1, 6보다 크므로 그대로 2) 5는 9보다 작으므로 9와 자리 바꿈. 해..

pair와 vector 라이브러리 사용해서 정렬하는 방법이다. pair는 한 쌍의 데이터를 사용할 수 있는 라이브러리이다. 아무런 조건 없이 단순 정렬을 하는 경우 처음에 있는 항목 기준으로 정렬된다. (ex 하단 코드에서는 int 기준으로 정렬된다.) 문제 1. #include #include #include using namespace std; int main(void) { vector v; //v.push_back : 리스트 마지막에 삽입 v.push_back(pair(90, "박한울")); v.push_back(pair(85, "이태일")); v.push_back(pair(82, "나동빈")); v.push_back(pair(98, "강종구")); v.push_back(pair(79, "이상욱")..

정렬 라이브러리가 있기 때문에 정렬 문제에서 굳이 코드를 만들 필요 없이 정렬 라이브러리를 쓰면 된다. c++에서 다양한 stl 라이브러리를 제공하기 때문에 c++를 사용한다. #include #include using namespace std; //비교함수 bool compare(int a, int b) { return a b이면 내림차순 정렬이 됨. } int main(void) { int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2}; //정렬할 기준을 직접 설정. //두 번째에는 a+10처럼 변수의 개수를 더한 값을 작성 //세 번째에 직접 만든 함수를 집어넣으면, 해당 함수의 반환값에 맞게 정렬 동작 sort(a, a + 10, compare);..

- 지난번의 퀵 정렬은 편향되게 분할될 가능성이 있기 때문에 최악의 시간복잡도가 O(N*N)이다. 하지만 병합 정렬은 정확히 반씩 나누기 때문에 최악의 경우에도 O(N*logN) 시간복잡도를 보장한다. - 정확히 반으로 쪼갠 후 나중에 합친다. 피벗값은 없다. - 실행 순서 : 1) 처음엔 각각 전부 한 개씩 나눈다. 2) 2개씩 정렬을 하며 합친다. (합칠땐 2의 배수만큼 합친다.) 3) 또 정렬을 하며 이번엔 4개가 합쳐진다 4) ... - 계산 속도는 상단 그림상 너비는 N(8)이고 높이는 logN(로그 2의 8=3)이기 때문에 총 시간복잡도는 O(N*logN)가 된다. 퀵 정렬보다 빠르진 않지만 O(N*logN) 를 보장할 수 있기 때문에 좋다. - 인덱스는 총 3개를 사용한다. 1) i와 j를 ..

[줄 이동 단축키] 줄 이동 : alt 누르고 화살표 줄 복사 후 이동 : ctrl + alt 누르고 화살표 [디버그하는법] : 오른쪽 위 -> 디버그창 엶, 디버그 토글 선택, 디버그 실행 [메소드(함수) 선언] public static 리턴타입(자료형or void) 메소드명() { return (void면 return 없음) } 메소드는 main문 밖에 선언한다. [while 문] while은 조건식이 true일 경우 하단 실행문을 실행. false이면 실행문을 실행하지 않고 종료. [ArrayIndexOutOfBoundsException] 배열의 크기가 맞지 않는 경우 생기는 예외. 배열의 크기가 작은 줄 알고 오류부분이 어딘지 계속 찾았는데, 배열의 기존 크기가 클 때도 생기는 오류였다. 백준 문..

1. 선택 정렬 - 개념 : 가장 작은 걸 선택해서 가장 앞으로 보낸다. - 코드 내용 : 모든 자리의 최소값을 스캔해서 가장 앞에 있는 숫자와 위치 바꿈. - 시간복잡도 : O(N*N) 2. 버블 정렬 - 개념 : 당장 옆에 있는 것과 비교 - 코드 내용 : 당장 옆에 있는 것과 서로 비교해서 순서에 맞게 서로 위치 바꿈. - 시간복잡도 : O(N*N), O(N*N)인 정렬 중 가장 느림 3. 삽입 정렬 - 개념 : 앞 숫자들이 정렬돼 있다고 가정하고 다음 숫자를 사이에 삽입. - 코드 내용 : 정렬돼 있는 숫자를 기준으로 바로 오른쪽에 있는 숫자의 크기와 비교하여 (정렬숫자)>(정렬안된 오른쪽숫자) 이면 둘의 위치를 바꾼다. 정렬될 때 까지 반복한다. - 시간복잡도 : O(N*N), O(N*N)인 정..

백준알고리즘에서 컴파일 에러가 하단과 같이 난 경우. class HelloWorld is public, should be declared in a file named HelloWorld.java 해결 방법 : 백준 알고리즘에서는 JAVA를 제출할 때 class이름을 Main으로 설정을 해야 한다.

https://chrome.google.com/webstore/detail/%EB%B0%B1%EC%A4%80%ED%97%88%EB%B8%8Cbaekjoonhub/ccammcjdkpgjmcpijpahlehmapgmphmk/related 백준허브(BaekjoonHub) Automatically integrate your BOJ submissions to GitHub chrome.google.com 상단 링크에서 확장프로그램 설치 > Authenticate > 깃허브 로그인 Create a new Private Repository : 새로운 이름의 레포지토리를 생성 Link an Existing Repository : 이미 존재하는 레포지토리와 연결 Repository 생성 완료 이제 확장프로그램을 설치한 환..

백준 사이트 https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net - 처음이면 이 두 카테고리 중 풀기! 문제 > 단계별로 풀어보기 문제 > 알고리즘 분류 - 1초에 1억번 연산 가능하다고 생각하면 된다. - 웬만한 알고리즘 문제를 풀 때 배열은 +1의 크기로 해놓는 것이 좋다. 만약에 N이 1000이라면 하단처럼 배열의 크기는 1001로 해놓는다. - 소스코드 비공개, 언어는 c++ 11로 설정. - 백준 내 프로필 : https://solved.ac/profile/1010hy --- 1. 단순정렬 : https://www.acmicpc.net..