본문 바로가기

자료구조와 알고리즘/알고리즘31

농구 경기(1159) 문제 요약 성의 첫 글자가 같은 선수 5명을 선발. 만약 성의 첫 글자가 같은 선수가 5명보다 적다면, 기권. 뽑을 수 있는 성의 첫 글자를 모두 구하기. 입력 선수의 수 : N (1 n; vector names(26, 0); vector result; for(int i=0; i > name; char lastName = name[0]; names[lastName - 'a']++; } for(int i=0; i= 5){ result.push_back(i + 'a'); } } if(result.empty()){ cout name; names[name[0] - 'a']++; } for(int i=0; i= 5){ result += (i + 'a'); } }.. 2023. 7. 2.
Palindrome Palindrome, 한국어로 회문이라는 뜻으로 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 물자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. 입력받은 단어가 팰린드롬인지 아닌지 확인하려면 어떻게 해야 할까? 문자열을 뒤집으면 된다. 이는 실제 구현된 함수를 이용하면 매우 간단하게 구현할 수 있다. #include using namespace std; string str; int main() { cin >> str; auto tmp = str; reverse(tmp.begin(), tmp.end()); if(str == tmp){ cout 2023. 7. 2.
트럭 주차 문제를 해석해 보자. 트럭을 총 세 대 가지고 있고, 한 대 주차 시 분당 A원, 두 대 주차 시 분당 B원, 세 대 주차 시 분당 C원이다. 세 대의 트럭이 고유한 도착 시간과 떠난 시간을 가지고 있다. 트럭이 겹치는 구간에 적용할 비용과 그렇지 않고 독자적으로 주차했을 때 비용들을 구해 합쳐야 한다. 입력의 시간은 1과 100 사이다. 이를 어떻게 효율적으로 저장하고 계산하는 알고리즘을 만들 수 있을까? 1. 주차한 트럭 수만큼 적용될 비용을 저장해야 한다. 분당 요금을 계산하는 과정에서 지속적으로 호출될 가능성이 높다. 이를 체크하고 몇 대면 얼마를 특정 요금을 나타내는 자료구조에 추가하도록 해야 하지 않을까? 2. 분당 요금을 계산하는 경우 해당 시간에 몇 대가 주차되었는지 확인하고 요금을 부과해.. 2023. 7. 1.
문자열 카운팅. 문자열 및 숫자가 입력 값에 대해 몇 개가 존재하는지 검사해야하는 경우 추천하는 자료구조와 선택의 이유는 다음과 같다. 1. 배열 배열은 int 형으로 변환이 가능한 경우 추천한다. 다만 문자열이더라도 아스키 코드로 변환이 가능한 경우에는 배열을 사용하는 것이 유리할 수 있다. 2. Map map 자료구조는 쌍을 이루는 자료구조이다. 이는 String 혹은 입력의 크기가 1000만을 넘어가거나, 각 입력이 10만, 100만 과 같이 순차적으로 분리되어 들어오는 경우 추천한다. 이에 대한 연습 문제로 백준 10808번 문제를 풀어본다. 문제 해석. 문제 : 각 알파벳이 단어에 몇 개 포함되어 있는지 구하는 프로그램 입력은 알파벳 소문자 단어 ( 100을 넘지 않음) 출력은 알파벳 단어에 포함되어 있는 알파.. 2023. 7. 1.
2309 백준의 2309 문제를 읽었을 때 조합이 생각났다. 9명 중 7명을 뽑아 키의 합이 100인 경우 통과이며, 가능한 정답이 여러 개인 경우가 있다고 했기 때문에 정답 시 프로그램을 종료 시켜야한다. 이를 기반으로 코드를 작성해보자. #include using namespace std; int k = 7; int n = 9; int a[9]; void combi(int start, vector b){ if(b.size() == k){ int sum = 0; for(int height : b) sum += height; if(sum == 100){ sort(b.begin(), b.end()); for(int height : b) cout a[i]; vector b; combi(-1, b); return 0;.. 2023. 6. 26.
prefix sum 누적합에 대한 공부를 진행했다. 이를 다른 말로 구간 쿼리, 여기선 구간 sum 쿼리라고 한다고 한다. 이러한 문제를 푸는 방법은 prefix sum, 펜윅트리 방식들이 있다고 한다. 내가 연습한 예제는 static 배열이여서 prefix sum이 적합하다고 하셨고, 동적 배열, 즉 배열의 각 요소가 동적으로 변경되는 경우는 펜윅트리를 사용해야 한다고 한다. 우선 다음과 같은 문제가 발생한다고 생각해보자. N개의 자연수이고, M개의 질문을 한다고 가정하자. 예를 들면 10개의 자연수를 주고 3개의 질문을 하는데, 이 질문에는 범위가 포함되어 있다. 2부터 5까지 제공된 수의 합을 구하라, 1~10까지의 제공된 수의 합을 구하라. 등등의 질문이 연속적으로 나온다. 단순하게 접근했을 때 n개의 입력을 받고,.. 2023. 6. 25.
c++ split split 함수를 만들어본다. 다음과 같은 상황을 고려해야 한다. 1. 함수는 입력 문자열과 구분자를 매개변수로 받아야 합니다. 구분자는 문자열을 분리할 때 사용될 문자 또는 문자열입니다. vector split(string input, string delimiter) 2. 함수는 vector 을 반환해야 합니다. 각 분리된 문자열은 벡터의 요소로 저장되어야 합니다. vector split(string input, string delimiter){ vector ret; return ret; } 3. 입력 문자열을 구분자를 기준으로 분리해야 합니다. 문자열을 구분할 때 구분자가 나타나는 위치를 찾는 방법이 필요합니다. 문자열에서 구분자를 찾는 방법으로는 일치하는 문자열 또는 일치하는 문자열의 위치를 찾는 .. 2023. 6. 23.
순열 순서가 필요한 경우 다음 참고하여 빠르게 구현하도록 한다. next_permutation 함수: C++ 표준 라이브러리의 헤더에 있는 next_permutation 함수는 순열(Permutation)을 생성하기 위해 사용됩니다. next_permutation 함수는 현재 순열을 기준으로 다음 순열을 생성하고, 순열이 더 이상 존재하지 않을 때는 false를 반환합니다. int main() { int a[] = {1,2,3}; do{ for(int i : a) cout 2023. 6. 23.
Recursion #Recursion 재귀함수는 자신을 재참조하는 함수를 일컫는다. 예를 들면 Top - Bottom으로 진행되는 경우 이를 split 할 때 사용하기도 한다. 재귀함수에는 반드시 종료조건(기저사례)를 작성해야 한다. 그렇지 않으면 무한 루프가 발생한다. 또한 재귀함수는 사이클이 발생하는 경우에는 사용하면 안 된다. 이 경우도 동일한 이유다. 매개변수의 상태를 변경시켜 기저사례까지 도달하여 문제를 해결하는 경우 보통 사용한다. # DP DP 문제를 푸는 경우 함수의 참조가 적은 경우 재귀 함수로 문제를 해결하는 것이 더 효율적일 수 있다. 이러한 경우가 아니라면 반복문을 사용하는 것이 더 효율적이다. #예시 1. 팩토리얼 팩토리얼 n! 의미는 그 이전의 항을 모두 곱하는 것이다. int factorial(.. 2023. 6. 23.
1. 선택정렬 다음 숫자를 오름차순으로 나열하고 싶다면? 10 9 8 7 6 5 4 3 2 1 첫 번째로 가장 직관적인 생각은 가장 작은 것을 선택해서 앞으로 보내는 방법은 어떨까? 이 방법을 바로 "선택 정렬" 알고리즘이라고 합니다. package algorithm; public class algorithm01 { public static void main(String[] args) { int min =0 , temp =0, index = 0; int[] array = {10,9,8,7,6,5,4,3,2,1};//index배열을 크기값10으로 초기화.및 선언 for(int i =0; i 2021. 5. 30.

티스토리툴바