본문 바로가기
반응형

전체 글1306

[BOJ] 백준 1193 분수찾기 출처: https://www.acmicpc.net/problem/1193 Input 14 Output 2/4 배열에 지그재그로 분수가 주어집니다. X가 주어질 때, X번째 분수를 구하는 문제입니다. * 10,000,000 숫자를 입력받기 위해 long타입 처리 구현 지그재그 순서는 다음과 같습니다. 대각선 한 줄에 위치한 칸의 개수는 등차수열 형태를 가집니다. ▷ 1 + 2 + 3 + 4 + 5 + ... + (n-1) + n [등차수열 공식] 등차 수열 공식을 이용해 x는 몇 번째 대각선에 위치한지 알 수 있습니다. 14 → 5 Line 15 → 5 Line 16 → 6 Line 21 → 6 Line 22 → 7 Line 28 → 7 Line 29 → 8 Line n-th Line이 홀수일 때, → 분.. 2021. 2. 24.
[BOJ] 백준 1021 회전하는 큐 출처: https://www.acmicpc.net/problem/1021 Input 10 3 2 9 5 Output 8 덱 = { 1 2 3 4 5 6 7 8 9 10 }이 주어져있고 『2』, 『9』, 『5』를 뽑고자 합니다. ②번 연산 1번 수행 후 『2』를 뽑습니다. → 덱 = { 3 4 5 6 7 8 9 10 1 } ③번 연산 3번 수행 후 『9』를 뽑습니다. → 덱 = { 10 1 3 4 5 6 7 8 } ③번 연산 4번 수행 후 『5』를 뽑습니다. → 덱 = { 6 7 8 10 1 3 4 } ▶ ②, ③ 연산이 총 8번 수행. [구현] 원형 큐를 이용하거나 덱(Dequeue)을 이용. → ①번 연산은 덱에서 front 부분 삭제 → ②, ③번은 한쪽에서 pop()한 다음, 다른 쪽에 push().. 2021. 2. 24.
[BOJ] 백준 5430 AC 출처: https://www.acmicpc.net/problem/5430 Input 4 RDD 4 [1,2,3,4] DD 1 [42] RRD 6 [1,1,2,3,5,8] D 0 [] Output [2,1] error [1,2,3,5,8] error 덱(Dequeue) 활용 이 문제의 경우 덱을 구현하여 원소 순서를 뒤집을 때 실제 배열의 원소를 뒤집으면 시간제한에 걸립니다. 따라서, R(뒤집기) 함수의 경우 원소의 순서는 유지하되 바라보는 방향을 반대쪽으로 해서 처리합니다. → D(버리기) 함수일 때, 앞단(front)에서 제거할지, 뒷단(rear)에서 제거할지 결정 * 배열이 비어있는 상태에서 R(뒤집기) 하는 것은 『error』가 아닙니다. Input 1 R 0 [] Output [] * 매 Test.. 2021. 2. 24.
[BOJ] 백준 2579 계단 오르기 출처: https://www.acmicpc.net/problem/2579 Input 6 10 20 15 25 10 20 Output 75 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 계단은 아래와 같습니다. ▶ 10 + 20 + 25 + 20 = 75 게임 진행 방식 ① 계단은 한 번에 1계단씩 또는 2계단씩 오를 수 있다. ex) 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라갈 수 없다. .. 2021. 2. 24.
[VS Code] Git 관련 Extension GitLens VS Code 내에서 Git과 관련해서 여러 사항을 보여준다. ex) 해당 Code를 최근 Commit한 사람이 누구이며 언제인지 등 [Git 깃] git blame 기능을 제공해주는 셈인데 커서가 올려도 간략한 정보를 알 수 있다. [Git 깃] git blame git blame 특정 코드가 누가, 언제, 어떤 Commit으로 변경했는지 확인할 수 있는 명령어 git blame {파일명} author와 timestamp 출력 X git blame -s {파일명} 특정 라인[start, end] 까지만 확인 git blame -L {start},{end} zoosso.tistory.com Git History VS Code 내에서 Git 기록을 볼 수 있다. 커맷내용, 브랜치, 작성자 이.. 2021. 2. 23.
[MySQL] MySQL 다운 및 설정 MySQL을 GUI 환경에서 실습할 수 있는 WorkBench 설치 내용 사전 설치 Visual Studio 2013용 Visual C++ 재배포 가능 패키지 다운로드(링크) 운영체제에 맞는 32 bit / 64bit 패키지 다운 MySQL 설치 사이트에서 MySQL 다운 (Bit는 크게 상관 X) 굳이 로그인/회원가입 과정없이 다운 받을 수 있기에 [ No thanks, just start my download. ] 선택 설치과정 (* 기본값으로 설치) [Execute]를 시도해도 계속 반복해서 [Execute] 해야 하는 경우가 있다. 어느정도 다 받고 동일한 과정이 반복된다면 무시하고 [Next]하여 다음 단계 진행 [Standalone MySQL Server / Classic MySQL Repli.. 2021. 2. 23.
[예제] 합병 정렬 (Merge Sort) ▶ 시간 복잡도 O(N × log2N) ▶ 참고: 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com #include const int N = 7; int arr[N] = {5, 9, 7, 1, 3, 8, 2}, temp[N]; void mergeSort(int start, int end) { // 0. base condition if (start >= end) return; // 1. divide in.. 2021. 2. 23.
[BOJ] 백준 1463 1로 만들기 출처: https://www.acmicpc.net/problem/1463 Input 10 Output 3 ▶ 10 → 9 → 3 → 1 로 연산 3번 사용 [구현] dp[i] = 숫자 i에 연산 횟수 최소 비용 = 1 + Min(dp[i / 3] + dp[i / 2] + dp[i-1]) [x = 1] → result = 0 [x = 2] 2 / 2 = 1 2 - 1 = 1 → result = 1 [x = 3] 3 / 3 = 1 3 - 1 = 2 / 2= 1 = 2 - 1 = 1 → result = 1 [x = 4] 4 - 1 = 3/ 3 = 2 4 / 2 = 2 / 2 = 1 = 2 - 1 = 1 → result = 2 [x = 9] ※9는 2로 나누어 떨어지지 않습니다. dp[9] = 1 + Min(d.. 2021. 2. 23.
[Java] 오버로딩(Overloading) 메소드 오버로딩은 메소드명은 동일하면서 매개변수의 개수, 타입이 다릅니다. 즉, 매개변수가 다르면 메소드명이 같아도 서로 다른 메소드가 되는 것입니다. → 다형성 (객체지향 특성) 아래의 계산기는 2개의 값(left, right)에 대한 연산(sum) 만을 수행 할 수 있습니다. class Calculator{ int left, right; public Calculator( int left, int right ){ this.left = left; this.right = right; } public String sum(){ return "" + this.left+this.right; } } public class Main { public static void main(String[] args) { Calc.. 2021. 2. 23.
기수 정렬(Radix Sort) 기수 정렬 - O(N + K) - 원소들의 자릿수에 따라서 정렬 ① 1의 자릿수를 기준으로 정렬 ② 10의 자릿수를 기준으로 정렬 ③ 100의 자릿수를 기준으로 정렬 ④ ... 최대 자릿수의 길이만큼 반복 작은 자리수부터 비교하는 방식을 LSD 큰 자리수부터 비교하는 방식을 MSD 시간복잡도는 O(N + K)로, K는 최대 자릿수의 길이. 구현 일반적으로는 각 자릿수 오름차순으로 담기위해 Queue를 이용합니다. ① 1의 자릿수를 기준으로 정렬 - 자릿수에 따른 큐에 원소를 집어넣는다. (N번) - 큐에 있는 원소를 pop() 하여 원소를 재배열 합니다. (N번) ② 10의 자릿수를 기준으로 정렬 ③ 100의 자릿수를 기준으로 정렬 - 최대 자릿수의 길이 = 3이므로 총 3번 진행 - (십진수의 경우) .. 2021. 2. 23.
반응형

티스토리툴바