전체 글
![[알고리즘 예제][정렬]Q_sort.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbHUD9p%2Fbtq8W7qX7PD%2FsK6JozKTWDKAkNB5BKnHok%2Fimg.png)
[알고리즘 예제][정렬]Q_sort.
#include #include using namespace std; void quickSort(vector &v, int i, int j) { // 벡터의 크기가 0이나 1. if(i>=j) return; int pivot = v[(i+j)/2]; int left = i; int right = j; while(left
![[C++][백준 BOJ]1182_부분수열의 합.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fo6V6O%2Fbtq8U1xjkfO%2FRJpLU27kae0S1pDwZArjZk%2Fimg.png)
[C++][백준 BOJ]1182_부분수열의 합.
문제 번호 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 알고리즘 분류 부르트포스, 백트래킹. 문제 풀이 문제에서 주어진 수열의 모든 부분수열의 합을 구해보고 그중에서 조건에 맞는 답의 개수를 구하는 문제이다. 우선 몇개의 수로 이루어진 부분수열을 구할것인지 정해야한다. // 몇개를 고를건지. for (int i = 1; i arry[i]; } void Check() { int sum=0; for(int i..
![[C++][백준 BOJ]14502_연구소.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbkQSrm%2Fbtq8W7RzPek%2FqaAvpn4p7KGe6KMzGY3d50%2Fimg.png)
[C++][백준 BOJ]14502_연구소.
문제 번호 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 분류 그래프 탐색(BFS, DFS), 브루트포스(전체탐색). 문제 풀이 그래프 탐색(BFS 혹은 DFS)과 브루트포스(전체 탐색/완전 탐색)를 모두 사용할 줄 알아야 수월한 문제였다. 처음에는 그래프 탐색에 한해서만 생각해보느라 어떤 식으로 탐색을 진행해야 하는지에만 초점을 맞추어 고민했는데 그냥 다 해보아야 한다. 문제에서 주어진 크기가 별로 크지 않고 모든 경우의 수를 다 고려해보아도 ..
![[C++][백준 BOJ]4963_섬의 개수.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbKrJOV%2Fbtq8RTMUhbu%2F7MkKEnSrwNWxi2z6QoqtAk%2Fimg.png)
[C++][백준 BOJ]4963_섬의 개수.
문제 번호 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 알고리즘 분류 그래프 탐색(BFS) 문제 풀이 BFS를 사용하여 이어진 부분을 모두 탐색하면 된다. 문제에서 최대 높이와 넓이는 각각 50이라고 하여 52*52 크기의 2차원 배열 Graph와 Visited를 사용하였다. 가장 왼쪽 위(1,1)에서 시작하여 (h, w)까지 탐색한다. 탐색 도중 땅(1)을 발견하면 BFS를 실행하여 Visited배열에 하나의 섬을 방문하였다(true..
[C++][프로그래머스]연습문제_N개의 최소공배수
문제 번호 https://programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 알고리즘 분류 수학 문제 풀이 예전에 풀어보았던 문제랑 비슷하다. 이 문제를 해결하기 위해서는 최대 공배수를 구하는 유클리드 호제법(GCD)을 알 필요가 있다. 간단하게 GCD는 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘이다. GCD : int gcd(int a, int ..
[JS][프로그래머스]연습문제_직사각형 별찍기.
문제 번호 https://programmers.co.kr/learn/courses/30/lessons/12969?language=javascript 코딩테스트 연습 - 직사각형 별찍기 이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다. 별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요. 제한 조건 n과 m은 각각 1000 이하인 자연수 programmers.co.kr 알고리즘 분류 입출력. 문제 풀이 특별한 알고리즘은 없다. 문제에서 주어지는 n과 m을 받아서 직사각형 모양으로 별을 출력하면 된다. process.stdin.setEncoding('utf8'); process.stdin.on('data', data => { const n = data.s..
![[C++][백준 BOJ]1449_수리공 항승.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbIi9Fm%2Fbtq8QqbNBdu%2FLcfAakYHafGVhAh40AJepK%2Fimg.png)
[C++][백준 BOJ]1449_수리공 항승.
문제 번호 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 알고리즘 분류 그리디(greedy), 정렬(sort) 문제 풀이 구멍난 위치가 가까운 곳부터 먼곳순서로 정렬한다. 문제에서 구멍난곳 양쪽으로 0.5씩 간격이 있어야 한다고 했다. 그래서 (i 번째) + L >= (i+N)번째 +1 의 조건에 만족한다면 i번째에서 시작해서 i+N 번째 까지 같은 테이프로 막을 수 있다고 생각했다. 소수점 계산을 피하기 위해서 0.5씩 필요..
![[C++][백준 BOJ]1202_보석 도둑.](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FmzHNg%2Fbtq8RurRIJ9%2Fkq4VeIzsOEqoEqtDRbKHH0%2Fimg.png)
[C++][백준 BOJ]1202_보석 도둑.
문제 번호 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 알고리즘 분류 그리디(greedy), 우선순위 큐(priority_queue) 문제 풀이 문제에서 주어진 가방의 크기들을 오름차순으로 정렬한다. 문제에서 주어진 보석들 또한 무게를 기준으로 오름차순으로 정렬한다. 우리는 가방에 1개의 보석만 넣을 수 있기 때문에 넣을 수 있는 보석들중 가장 비싼 보석을 넣어야한다. 그래서 Ma..