본문 바로가기
반응형

분류 전체보기1306

[Jungol] 정올 1148 최종 울트라-퀵 소트 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=428&sca=60 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 문제 내용에서 "인접한 두 수를 서로 바꿔서 주어진 수열을 오름차순으로 정렬" 한다고 해서 단순하게 버블 정렬의 원소 교환횟수를 묻는 문제로 생각해서 안됩니다. arr = {1, 3, 4, 5, 2}를 선택.. 2021. 2. 23.
[예제] srand()를 이용한 1~10까지의 난수 생성 해당 게시글에서는 10개의 숫자를 랜덤하게 생성할 때, 1~10까지의 숫자 중 랜덤하게 가지는 방법과 1~10까지 숫자를 중복없이 랜덤하게 배치하는 방법을 소개합니다. ([C / C++] 난수 생성 (rand, srand, time) 보고 오시면 좋습니다.) srand()와 rand()를 통해서 0 ~ 32767을 랜덤하게 추출할 수 있었습니다. 1~10까지의 숫자를 랜덤하게 추출하는 방법은 나머지 연산을 이용하는 것입니다. → rand() % MOD #include #include #include const int SIZE = 10; int idx, list[SIZE]; int main() { srand(time(NULL)); while (idx < SIZE) { int val = rand() % SI.. 2021. 2. 23.
[Jungol] 정올 3519 Tutorial : 합병(병합)정렬(Merge Sort) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2859&sca=3010 Approach ▶ 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com #include #define LM 500005 int N, arr[LM], copyArr[LM]; void input() { scanf("%d", &N); for (int i = 0; i < N;.. 2021. 2. 23.
가벼운 개발 툴 [Dev C++] 설치 알고리즘 문제 풀 때, 간단하게 사용할 수 있는 가벼운 도구. (+ 『Visual Studio IDE』과 같은 다른 도구를 이용하고 있다면 그대로 사용해도 무방) (+ 실제 C 기반으로 규모가 큰 프로젝트를 작업할 때는 추천하지 않는다.) 『DEV C++』 검색하여 다운로드 (* 기본 설정으로 설치) (프로그램 실행 후) 소스 생성 [파일] → [새로 만들기] → [소스 파일] (+ 단축키: 『Ctrl + N』) 소스 입력 #include int main(void){ printf("안녕 세상아!"); return 0; } 소스 저장 컴파일 후 실행 ※ (단축키 『 F11 』 결과 확인 2021. 2. 23.
[BOJ] 백준 11051 이항 계수 2 출처: https://www.acmicpc.net/problem/11051 Input 5 2 Output 10 [BOJ] 11050 이항 계수 1 문제처럼 재귀방식으로 접근하면 시간제한이 걸립니다. [BOJ] 백준 11050 이항 계수 1 출처: https://www.acmicpc.net/problem/11050 Input 5 2 Output ※ 이항 계수(binomial coefficient)는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수 다음과 같은 점화식이 존재.. zoosso.tistory.com 불필요하게 재귀호출되는 bino(n, k)를 DP 방식으로 처리 [Bottom-up 방식] import java.util.Scanner; public class Main{ s.. 2021. 2. 23.
[BOJ] 백준 11050 이항 계수 1 출처: https://www.acmicpc.net/problem/11050 Input 5 2 Output ※ 이항 계수(binomial coefficient)는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수 다음과 같은 점화식이 존재합니다. * n == r 이거나 r == 0 이며 1을 반환한다! ▶ 재귀 방식 이용 DP 방식 풀이: [BOJ] 11051 이항 계수 2 [BOJ] 백준 11051 이항 계수 2 출처: https://www.acmicpc.net/problem/11051 Input 5 2 Output 10 [BOJ] 11050 이항 계수 1 문제처럼 재귀방식으로 접근하면 시간제한이 걸립니다. [BOJ] 백준 11050 이항 계수 1 출처: https://www.ac.. 2021. 2. 23.
[BOJ] 백준 1932 정수 삼각형 출처: https://www.acmicpc.net/problem/1932 Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Output 30 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com ※ 아래층 이동은 현재 층에서 선택된 수에서 대각선 왼쪽 혹은 대각선 오른쪽 입니다. arr[i][j] → arr[i+1][j] or arr[i+1][j+1] [n = 1] → result = .. 2021. 2. 23.
[Java] main 함수 [Java] main 함수 public static void main(String[] args){ ... } 1. main() 메서드는 public 속성이다. 이는 다른 클래스에서 호출 가능함을 표시한다. 자바 응용프로그램이 실행을 시작할 때 자바 가상 기계(JVM)에 의해 호출되어야 하므로 public 속성으로 선언되어야 한다. 2. static 속성이다. main() 메소드가 포함된 클래스의 객체가 생성되기 전에 자바 가상기계에 의해 호출되므로 static 속성으로 선언되어야 한다. 3. 리턴 타입은 void 이다. 아무 값도 리턴하지 않기 때문에 void 리턴 타입이다. 4. 인자는 문자열 배열(String [])이 전달된다. 명령행에 주어진 모든 인자를 문자열로 처리하여 main() 메서드에 전달.. 2021. 2. 23.
정렬 알고리즘 비교 시간 복잡도 비교 ▶ O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ) 정렬 알고리즘 시간 복잡도 특징 안전성은 주어진 배열 원소의 배치와 상관없이 구현 속도에 변함이 없는가를 의미합니다. 즉, Worst, Best, Average의 시간복잡도가 동일한 경루를 의미합니다. - 힙 정렬은 추가 메모리 따로 필요없을 뿐더러, 주어진 배열의 원소 배치와 상관없이 O(N log N) 지님 - 병합정렬도 마찬가지로 O(N log N) 입니다. - 퀵 정렬은 Pivot 변화에 따라서 시간 복잡도가 달라집니다. 즉, 원소가 편향적으로 배치된 경우에는 최악의 시간복잡도가 생김 O(N2) Q. 추가적인 메모리를 할당할 수 없을 경우, 데이터의 배치가.. 2021. 2. 23.
[BOJ] 백준 2947 나무 조각 출처: https://www.acmicpc.net/problem/2947 5개 숫자를 정렬하는데 교환이 발생할 때마다 현재 배열 상태를 출력해야 한다. 버블 정렬(Bubble Sort)을 구현하는 것에서 버블 정렬(Bubble Sort) 특징 - O(N2) - 서로 인접한 두 원소를 비교하여 정렬 - 한 번의 탐색으로 가장 큰 원소가 맨 뒤에 위치하게 됩니다. (오름차순 기준) 시뮬레이션 구현 코드 (오름차순 기준) #include int swap(int* a, int* b zoosso.tistory.com 출력하는 시점을 잘 고려하면 된다. 구현 ① 5개 숫자 입력 받기 ② 위치 교환 발생 여부 처리 ③ 배열 위치 교환 swap() ④ 배열 상태 출력 #include const int SIZE = 5;.. 2021. 2. 23.
반응형

티스토리툴바