티스토리

한다 공부

검색하기

블로그 홈

한다 공부

sxyzn.tistory.com/m

컴퓨터공학전공!

구독자: 8

방명록 방문하기

주요 글 목록

[C++] 백준 알고리즘 1517번 버블 소트 문제 이름은 버블 소트지만 머지 소트 (병합 정렬)로 풀어야하는 문제. 왜냐하면 1 ≤ N ≤ 500,000 이기 때문에 n^2 으로 풀 수 없기 때문이다.. 헷갈려서 정리를 해봤는데 병합만 늘 O(N*logN) 이고, 기수 정렬이 O(kN), 삽입, 선택, 버블 등 대부분의 정렬은 최악의 경우 O(N^2) 까지 갈 수 있다. 그래서 안정적으로 빠른 병합 정렬을 잘 알아두는 것이 좋다고 한다. 1초의 시간이 주어졌을 때 대부분 1,000,000 정도의 데이터는 O(kN), O(N*logN) 10,000 정도의 데이터는 O(N^2) 500 이하의 데이터는 O(N^3) 인 알고리즘이 사용 가능하다고 한다. 왜냐하면 1초에 주로 1억회의 연산이 가능한데 10,000의 경우 N^2이면 1억이 되기 때문에 위와 .. 공감수 0 댓글수 1 2023. 2. 6.
[C++] 백준 알고리즘 11268번 절댓값 힙 - Refactoring https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1년 6개월 전(?) 이 문제를 푼 적이 있었다, 예전에는 음수, 양수를 따로 우선순위 큐를 이용해서 작은 수를 기준으로 정렬했는데 (greater 사용) 새로이 풀어보면서 우선순위 큐의 정렬 기준을 직접 변경하는 방법이 있길래 사용해봤다. 구조체와 operator 메소드를 사용하면 된다. (저번에 푼 방식) https://sxyzn.tistory.com/38 [C++] 백준.. 공감수 0 댓글수 0 2023. 1. 25.
[C++] 백준 알고리즘 10815 숫자 카드 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 벡터를 사용하면 시간초과가 나올 것이다. 그래서 셋을 사용했다. 셋은 중복없이 정렬된 상태로 저장이 되고, 셋의 find 함수를 사용할 경우 시간복잡도는 O(logN) 를 가진다. 왜냐하면 셋은 BST(Binary Search Tree, 이진 탐색 트리) 자료구조를 갖고 있기 때문이다. 셋의 find 함수의 경우, 해당 원소가 있으면 해당 위치의 iteratior를 .. 공감수 0 댓글수 0 2022. 11. 7.
[C++] 백준 알고리즘 1235 학생 번호 https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 반례를 찾지 못해서 시간이 오래걸린 문제.. 정작 반례를 찾은 다음에는 금세 구현할 수 있었다.. 잘못된 접근) 처음에는 어떻게 접근을 했냐면, 첫번째 문자열이 12345이고 두번째 문자열이 56789 세번째 문자열이 00000 이라면 첫번째 문자열을 잘라내어 (12345를 1, 또는 12, 또는 123... 과 같이 잘랐었음) 두번째 문자열의 부분 문자열과 같은지.. 세번째 문자열의 부.. 공감수 0 댓글수 0 2022. 10. 26.
[C++] 백준 알고리즘 1152 단어의 개수 https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 아주 단순한 문제. 공백을 포함한 문자열을 받고, 맨처음이 공백인 경우와 맨끝이 공백인 경우를 제외하고 공백 갯수 +1을 하면 된다. cin>> 으로 받으면 공백을 인식하지 못하기 때문에 getline(cin, str) 을 사용하면 된다. #include using namespace std; int main(){ int ans=0; string s; getline(cin,s); for(int.. 공감수 0 댓글수 0 2022. 10. 12.
[C++] 백준 알고리즘 1541 잃어버린 괄호 (그리디) 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 연습을 하고자 1541번을 풀어보았다. 한 번이라도 - 가 나왔을 때 그 뒤의 값을 다 뺄셈 해주면 최솟값이 된다. a + b - c - d + e - f + g 같은 경우에는 a + b - c - (d + e) - (f + g) = a + b - c - d - e - f - g 가 된다. 어쨌거나 그리디 적으로 (?) - 나오면 그 뒤의 연산을 다 뺄셈 처리 하는게 전체의 최솟값이다. 그리디는 뭔.. 공감수 0 댓글수 0 2022. 3. 24.
[C++] 백준 알고리즘 1991 트리 순회 [C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 (tistory.com) [C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서 sxyzn.tistory.com 위 게시글에서 트리의 순회에 대해 알아보았다. C로 풀었던 트리의 순회를 C++에서는 map을 이용하여 풀 수 있다. map은 파이썬에서의 딕셔너리와 비슷한 자료구조이다. key - value 쌍으로 저장이 되며, key 값을 정렬된 상태로 저장한다. pair라는 것도 있는데, 이것은 두 값을 저장할 수 있다. 이 때에는 pair의 .. 공감수 0 댓글수 0 2022. 3. 7.
[C++] 백준 알고리즘 2294 동전 2 (동적 계획법) 2294번: 동전 2 (acmicpc.net) 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동적 계획법 문제는 어렵다..... 이 문제는 아래와 같이 풀었다 가치가 1 3인 동전이 있다고 하자 1~6 까지의 가치합을 만든다고 하면 가치 1인 동전을 쓰면 동전의 갯수가 1 2 3 4 5 6 일 것이다. 가치 3인 동전을 쓰면 동전의 갯수는 0 0 1 2 3 1 일 것이다. 가치 1, 3 모두 쓰면 동전의 갯수는 1 2 1 2 3 1 일 것이다. 이는 어떻게 구한 것 이냐면 , .. 공감수 0 댓글수 0 2022. 2. 28.
[C++] 백준 알고리즘 13549 숨바꼭질 3 (0-1 BFS) 13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 7%, 90%에서 멈추는 사람 .... 🖐 ^^ 나밖에 없을듯,.. 0-1 BFS 우선 0-1 BFS란? 최단경로 문제이면서 가중치가 0,1 만 존재할 때 덱을 이용하여 푸는 문제이다. 다익스트라를 사용했을 때 보다 빠르다. 가중치가 두 개인 상태에서 최단경로를 구해야하므로 가중치가 낮은걸 push_front를 하고 가중치가 높은걸 push_back하면 우선순위(짧은 경로)에 따.. 공감수 0 댓글수 0 2022. 2. 27.
[C++] 백준 알고리즘 10814 나이순 정렬 10814번: 나이순 정렬 (acmicpc.net) 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두가지 값을 저장하는 것이므로 pair를 이용하면 된다. 단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다. #include 안에 있는 sort 함수를 써서 정렬을 했다 계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 .. 공감수 0 댓글수 0 2022. 2. 25.
[C++] 백준 알고리즘 10816 숫자 카드 2 (이분 탐색) 10816번: 숫자 카드 2 (acmicpc.net) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net (이분 탐색) 지난 포스팅 을 통해 이분 탐색을 공부했다. 이번엔 직접 구현을 해보았다. 우선 해당 문제는 내가 원하는 카드가 몇 장 있는지 탐색해야하는 문제인데, 어떻게 구할까? 이 문제에서는 upperBound 와 lowerBound 에 대해 알아야한다. [ 1 2 2 2 3 ] 라는 배열이 있다고 했을 때, 2를 찾는다고 가정해보자. lowerBound는 내가 찾는 카드의.. 공감수 0 댓글수 0 2022. 2. 14.
[C++] 백준 알고리즘 1920 수 찾기 (이분 탐색) 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다. 이 방법이 이분 탐색이다. C++에서는 #include을 통해.. 공감수 0 댓글수 0 2022. 2. 13.
[C++] 백준 알고리즘 1931 회의실 배정 (그리디) 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까? 그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다. 시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!! 그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다. O(N) 시간복잡도를 가지고, 백만 이상의 입력도 받을 수 있다. 주로 정렬과 우선순위 큐를 함께 이용한다. 그리디임을 확인하기 위해서는 많은 수학적 증명이 필요하다고 한다. 그러므로 보통의 경우, 직관적으로 판단하여 그리디를 사용한다고 한다.. 공감수 0 댓글수 0 2022. 2. 7.
[C++] 백준 알고리즘 12865 평범한 배낭 (동적 계획법, 냅색) 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 문제를 풀어보았다. 이 문제에서는, 들 수 있는 배낭의 최대 무게가 주어진다. 그리고 물건의 무게와 물건의 최대 가치가 주어지는데, 배낭에 넣을 수 있는 물건의 최대 가치값을 구하는 문제이다. 동적 계획법을 이용해 냅색 문제를 해결해보자. 우선 dp의 인덱스를 무게로 나타내자 예를 들어 배낭에 넣을 수 있는 최대 무게가 7Kg 이라고 하자. .. 공감수 0 댓글수 0 2022. 1. 30.
[C++] 백준 알고리즘 2579 계단 오르기 (동적 계획법) 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적 계획법 (dynamic programming) 이란 무엇일까? 바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다. 예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자. 왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다. 출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 .. 공감수 0 댓글수 0 2022. 1. 29.
[C++] 백준 알고리즘 15649 N과 M (1) (백트래킹) 15649번: N과 M (1) (acmicpc.net) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이란? 브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다. 백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다. 백트래킹은 주로 N의 값이 20보다 작을 때 이용한다. 위 N과 M (1)의 문제를 예로 들어보자. n=4, m=.. 공감수 0 댓글수 0 2022. 1. 24.
[C++] 백준 알고리즘 16563 어려운 소인수분해 (에라토스테네스의 체) 16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 일반 에라토스테네스의 체는 bool 배열을 만들어서 소수면 true, 아니면 false를 저장한다. 그런데 이 문제에서는 소인수들을 찾아야하므로 bool 배열 대신 int 배열을 만들어서, 어떤 수로 인해 소수가 아니게 되었는지를 저장한다. 예를 들어 8의 경우, 8은 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력 8/prime[k] = 8/2 =4 가 된다. 4는 2의 곱으로 인해 소수가 아니게 되었다.. 공감수 0 댓글수 0 2022. 1. 20.
[C++] 백준 알고리즘 2436 후보 추천하기 (유클리드 호제법) 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 유클리드 호제법을 이용했다. 최대공약수를 G, 최소공배수 L이라 하자 G*L = A*B 이다. (수학적 공식이라고 한다.) A = G*a, B=G*a이라고 하면 (이때 a, b는 서로소이다. 왜냐하면 최대공약수 G로 공통부분을 끄집어 냈으므로) G*L = G*a*G*b가 되고 약분하면 L/G=a*b가 된다. L G가 주어지니 이를 이용해서 A+B, 즉 a+b가 최소가 되는 a b를 찾고 a b에 G를 구해 최종적으로 .. 공감수 0 댓글수 0 2022. 1. 20.
[C++] 백준 알고리즘 5639 이진 검색 트리 5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 예전에 올린 이진 탐색 트리 코드를 일부 수정했다. c언어로 구현했던 것을 c++로 구현하니 신경써야하는 부분이 있었다. 엔터 입력시 입력을 종료해야하는 부분이 까다로웠다. 그래서 getline을 이용해 문자열로 받은 다음, stoi를 이용해 문자열을 정수로 변환했고 엔터 입력시 반복문을 빠져나오게 했다. 4358번 생태학 문제를 풀 때 비슷한 방법을 이용했다. #include #include #.. 공감수 0 댓글수 0 2021. 11. 22.
[C++] 백준 알고리즘 1448 삼각형 만들기 https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 삼각형 만들기 삼각형을 만드는 조건 : 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작으면 된다. a < b < c 일 때 c < a+b 이면 성립한다. 최대 길이의 삼각형을 만들면 되므로 가장 큰 길이인 빨대 3개를 골라주면 된다. 삼각형이 만들어지지 않을 수도 있다. 그러면 가장 큰 길이인 빨대를 버리고 나머지 중에 제일 큰 3개의 빨대를 골라서 비교해보면 된다... 공감수 0 댓글수 2 2021. 10. 7.
[C++] 백준 알고리즘 2108 통계학 2108번: 통계학 (acmicpc.net) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 산술평균의 경우 반올림값을 유의한다 2. 중간값의 경우, 입력 갯수가 홀수이므로 어렵지 않다 3. 최빈값의 경우, pair에 넣어서 빈도수를 비교하고 재정렬한다 4. 범위의 경우 차의 절댓값을 이용한다 최빈값이 까다롭지만 pair를 이용한다면 비교하기 수월하다. 이 문제는 함수를 많이 만드는 바람에 return을 자꾸 깜빡해서 런타임 에러가 많이 났었다 ㅠ #include #include #include #include #in.. 공감수 0 댓글수 0 2021. 9. 27.
[C++] 백준 알고리즘 3077 임진왜란 정답은 map으로 저장하고 학생의 답은 vector로 저장했다. 정답을 o[a]=0 o[b]=1 o[c]=2 으로 저장하고 학생의 답을 x[0]=a, x[1]=c, x[2]=b 로 저장을 했으니 정답의 맵의 key에 vector의 요소를 넣어주고 value의 크기를 비교해주면 된다. #include #include #include using namespace std; int main() { map o; vector x; int n, temp; cin >> n; temp = n; //정답 map으로 저장 string s; while (temp--) { cin >> s; o[s] = n - temp; } //학생의 답 vector로 저장 temp = n; while (temp--) { cin >> s; x... 공감수 0 댓글수 0 2021. 9. 27.
[C++] 백준 알고리즘 2858 기숙사 바닥 1. 테두리가 성립하는 모든 경우의 수를 구한다. 2. 해당 테두리로 사각형을 만들었을 때, 입력한 안쪽 벽돌의 갯수가, 만들어진 사각형의 내부 갯수와 같은지 확인한다. 테두리를 구하는 방법은, 가로길이 * 2 + 세로길이 *2 를 한 다음 겹치는 모서리 4개를 빼줘도 된다. 나는 가로길이 *2 + (세로길이-2) * 2 를 했다. i = 가로 j = 세로 인데, 가로의 범위와 세로의 범위는 주석에 적어뒀다. #include using namespace std; int main() { int r, b; cin >> r >> b; int l, w; //i의 범위 // 세로 길이가 가장 짧은게 3이다. // 이 경우 가로와 겹치지 않은 세로 벽돌은 2개 뿐임. //따라서 2개를 빼주고 위와 아래 2개가 있으.. 공감수 0 댓글수 0 2021. 9. 27.
[C++] 백준 알고리즘 10448 유레카 이론 (브루트 포스) 브루트 포스란 무엇인가? 모든 경우의 수를 다 해보는 것이다. 이런 단순한 방법이 때로는 가장 합리적인 방법일 수도 있다. #include #include using namespace std; vector num; //삼각수를 벡터에 push_back void calc() { int sum = 0; int k = 1; while (sum < 1000) { sum += k; num.push_back(sum); k++; } } //세 삼각수의 합이 입력한 수이면 true 리턴 bool check(int n) { bool c = false; for (int i = 0; i < num.size(); i++) { for (int j = 0; j < num.size(); j++) { for (int k = 0; k.. 공감수 0 댓글수 0 2021. 9. 27.
[C++] 백준 알고리즘 6588 골드바흐의 추측 (에라토스테네스의 체) 에라토스테네스의 체란 무엇일까? 소수를 판단할 때 유용하게 쓰인다. 소수란 1과 자기자신으로만 나누어지는 수이다. 2 3 5 7... 등이 있다. 2부터 생각을 해보자. 2는 소수이다. 2*n배는 소수가 아니다. 그렇다면 2*2, 2*3, 2*4.... 2*(n) 은 모두 소수가 아니므로 제거한다. (코드에서는 bool형 배열을 false함으로써 제거) 그리고 3도 같은 방법으로 3의 배수들을 false한다. 4의 경우 이미 2*2에서 false되었으므로 5를 확인한다. 이런식으로 계산을하면 소수 2 3 5 7..은 남아있고, 소수가 아닌 어떤 수들의 배수들인 4 5 8 9 10... 은 false처리되며 제거된다. 이 방법으로 소수 판정을 하면 O(nlog(log n))만에 가능하다. false로 바꿔.. 공감수 0 댓글수 0 2021. 9. 21.
[C++] 백준 알고리즘 9613 GCD 합 (유클리드 호제법) GCD(Greatest Common Divisor) GCD란 최대공약수를 의미한다. 최대공약수를 구할 땐 유클리드 호제법을 이용하는게 편하다. 유클리드 호제법이란, a b의 최대공약수가 a%b(나머지) b의 최대공약수가 같다는 것을 이용하는 것이다. 예를 들어 15와 10이 있다고 해보자. a=15, b=10이라고 하면 a%b=5, b=10이 된다. 이 a%b값을 a에 대입하자. x%y를 할 때에는 x>y여야하므로 둘의 자리를 바꿔줘야한다 그러면 a=10, b=5가 된다. 나머지가 0이 될 때까지 해보자. a%b=5, b=5가 된다. a%b를 a에 대입하면 a=5, b=5가 되고 a%b = 0이 된다. 0이 되면 작은 값인 b를 리턴한다. 그러면 최대공약수가 b값, 즉 5가 된다 예를 들어 7과 3이 있.. 공감수 0 댓글수 0 2021. 9. 21.
[C++] 백준 알고리즘 11050 이항 계수 1 수학시간에 하던 combination, 조합을 구하면 된다. 재귀함수 등 풀이법은 많은 것 같지만 나는 while문과 for문을 썼다. 어렵지 않게 풀었다. #include using namespace std; int main() { int n, k, temp;; cin >> n >> k; temp = k; int a = 1; while (temp--) { a = a * n; n--; } int b = 1; for (; k > 0; k--) { b = b * k; } cout 공감수 0 댓글수 0 2021. 9. 21.
[C++] 백준 알고리즘 12018 Yonsei TOTO 다른 사람들이 신청한 마일리지를 temp라는 최소 힙으로 담았다. 만약 3명만 수강신청 가능할 때, 5명이 신청을 했다고 해보자 마일리지를 5 10 15 20 25를 담았다고 치면 이를 최소 힙 temp 에 담아서 정렬한다. 그리고 내가 신청을 하기 위해, 오버된 만큼을 힙에서 pop 시킨다. 5-3, 즉 2만큼 pop해보자 15, 20, 25 만 남았다! 같은 마일리지를 할당해도 내가 우선시 되므로 15, 20, 25 할당된 수업에서 내가 수강신청하려면 15만 할당해도 된다. [결론] 1. 인원이 널널하면 마일리지를 1만 할당, 최소힙 q에 1을 담는다. 2. 5명 신청가능한데 5명이 신청한 경우, 최소힙temp에 5명의 마일리지를 넣어서, 최소 마일리지 넣은 애를 구하고, 최소 만큼만 내가 할당한다... 공감수 0 댓글수 0 2021. 9. 20.
[C++] 백준 알고리즘 11268번 절댓값 힙 이 문제를 풀기 위해 음수 힙과 양수 힙, 두개를 선언했다. 최소 힙 두개를 만들었는데, priority_queue p; 를 이용하면 최소 힙으로 만들 수 있다. 이 때 vector 는 include 하지 않아도 되고, push와 pop 같은 연산은 priority_queue p; (최대 힙) 을 이용할 때 처럼 p.pop(); 등 으로 해주면 된다. #include #include using namespace std; int main() { //p에는 양수인 것들을 최소 힙으로 저장 //m에는 음수인 것들의 절댓값을 최소 힙으로 저장 priority_queue p; priority_queue m; int n; cin >> n; int q; int k; while (n--) { cin >> q; if (.. 공감수 0 댓글수 0 2021. 9. 20.
[C++] 백준 알고리즘 3613번 Java vs C++ 문제가 많이 긴데 결론은 문자열을 자바스타일에서 c++스타일로, 혹은 그 반대로 변환하면 되는 문제다 c++ 스타일의 문자열은 소문자와 언더바로 구성되는데 이 언더바가 오류를 많이 발생시킨다. _c도 에러 (시작이 언더바) c_도 에러 (마지막도 언더바) c__c도 에러다. (언더바가 두 번 나와도 에러) #include using namespace std; string ctoj(string name) { string j; for (int i = 0; i < name.length(); i++) { if (name[i] == '_') { j += name[i + 1] - 32; i++; } else j += name[i]; } return j; } string jtoc(string name) { strin.. 공감수 0 댓글수 0 2021. 9. 16.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.