목록대학교/Algorithm (105)
차근차근
0. 제목 백준 1543 문서 검색 BOJ 1543 문서 검색 Python 1543 문서 검색 1. 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한� www.acmicpc.net 2. 풀이 문자열 비교 중 단어가 문서의 범위를 넘어가면 안되므로 문서의 길이에서 시작인덱스를 뺀 값이 단어의 길이보다 크거나 같은 경우 반복문을 수행한다. 검사시작 index에서부터 단어의 길이만큼 문자열과 단어가 같으면 일치개수를 1증가시키고 검사 index를 단어길이만큼 증가시킨다. 단어가 ..
0. 제목 백준 2798 블랙잭 BOJ 2798 블랙잭 C++ 2798 블랙잭 1. 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 2. 풀이 3중 for문을 사용하면 된다. 조건문..
0. 제목 백준 11004 K번째 수 BOJ 11004 K번째 수 C++ 11004 K번째 수 1. 문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 STL의 sort는 quick sort와 같다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include using namespace std; int N, K; int arr[5000001]; int main(int argc, const char * ar..
0. 제목 백준 11652 카드 BOJ 11652 카드 C++ 11652 카드 1. 문제 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. www.acmicpc.net 2. 풀이 적혀있는 수의 범위가 크기 때문에 자료형을 long long으로 사용하는 것이 핵심이다. 처음에 배열을 입력받은 후, sort로 정렬을 한다. 그 후 가장 앞의 원소부터 다음..
0. 제목 백준 10989 수 정렬하기 3 BOJ 10989 수 정렬하기 3 C++ 10989 수 정렬하기 3 1. 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 계수 정렬(Counting Sort)를 사용하는 문제이다. 버블 소트와 같은 것을 사용하면 시간 초과가 난다. 계수 정렬은 수의 범위가 작을 때 사용하기에 적합하다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..
0. 제목 백준10825 국영수 BOJ 10825 국영수 C++ 10825 국영수 1. 문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다. www.acmicpc.net 2. 풀이 이름, 국어성적, 영어성적, 수학성적을 pair를 사용하여 묶어준다. sort함수에서 쓰일 정렬 기준 함수인 comp를 주의해서 구현하면 된다. 3. 코드 1 2 ..
0. 제목 백준 1182 부분수열의 합 BOJ 1182 부분수열의 합 C++ 1182 부분수열의 합 1. 문제 https://www.acmicpc.net/problem/1182 2. 풀이 브루트포스 방식으로 해결하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int arr[20]; int N, S; int cnt; void dfs(int i, int sum){ if(i == N) return; if(sum + arr[i] == S) cnt++; dfs(i + 1, sum); dfs(i + 1, sum + arr[i]); } int mai..
0. 제목 백준 1987 알파벳 BOJ 1987 알파벳 C++ 1987 알파벳 1. 문제 https://www.acmicpc.net/problem/1987 2. 풀이 DFS와 백트래킹을 사용하는 문제이다. 방문 여부를 체크할 때 A~Z, 총 26개의 인덱스를 가진다. 상하좌우 이동하며, 방문하지 않았다면 true로 체크한다. 방문한적이 있다면 무시하고 넘어간다. 가장 깊게 들어간 최댓값이 정답이다. 3. 코드 #include #include #include #include using namespace std; char arr[21][21]; bool visitedAlpha[26];//A~Z int R, C; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; int df..
0. 제목 백준 1759 암호 만들기 BOJ 1759 암호 만들기 C++ 1759 암호 만들기 1. 문제 https://www.acmicpc.net/problem/1759 2. 풀이 브루트포스를 이용하여 푸는 문제이다. 모음과 자음을 따로 입력받고 벡터에 각각 저장한다. visited는 map으로 설정하였고 해당 string에 방문한적이 있으면 true, 없으면 false를 저장한다. 최소 한개의 모음과 최소 두개의 자음이 포함되어야 하므로 그 조건에 맞고 길이가 길이조건인 L과 같다면 해당 문자열을 사전순으로 정렬하고 visited.count(s)가 false이면 즉, 방문한적이 없으면 result에 push 해주고 return 한다. 만약, 요구하는 길이인 L과 길이가 같지만 자음, 모음 조건을 만족..
0. 제목 백준 1525 퍼즐 BOJ 1525 퍼즐 C++ 1525 퍼즐 1. 문제 https://www.acmicpc.net/problem/1525 2. 풀이 이 문제는 브루트포스와 BFS를 사용하는 문제였다. 아홉개의 칸 순서대로 이어지는 숫자로 표현할 것이기 때문에 0을 9로 바꿔주고 시작한다. 정수를 입력받으면서 start라는 변수에 9자리 수를 저장한다. key, value쌍을 가지고 있는 map을 사용하여 dist를 선언한다. dist[x]는 x까지 움직인 횟수를 뜻한다. BFS를 사용하기 위해 큐를 선언하고 큐가 빌때까지 반복한다. 큐의 맨 앞에 있는 정수를 문자열로 만들어준다. 그 후 pop을 하고 9가 저장되어 있는 인덱스를 찾는다. 찾은 인덱스를 이용하여 x좌표와 y좌표를 찾는다. 미로..