C++
-
백준 5585 - 거스름돈백준 algorithm 2020. 7. 4. 10:47
=> 단순 구현 문제입니다. pay = 1000 - pay를 실행한다. 큰 단위의 수로 거스름돈을 최대한 많이 채운다. 1까지 채운 이후의 동전 개수를 구한다. => 단순한 문제이기 때문에 이 이상 설명은 하지 않겠습니다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int yen[6]={500,100,50,10,5,1}; int pay; cin >> pay; pay = 1000-pay; int cnt=0; for(int i=0; i 0) { pay %= yen[i]; cnt += tmp; } } cout
-
백준 1149 - RGB거리백준 algorithm 2020. 7. 4. 02:01
=> DP문제입니다. => 오랜만에 푸는 문제인지라 이해하는데 오래 걸렸습니다. => 빨간색을 칠하기 위해서는 이전에 초록색 혹은 파란색이 칠해져 있어야 합니다. =>이 경우, 둘 중에 최소값을 골라 해당하는 집에 빨간색을 칠하는 금액에 더해주어야 합니다. 파랑 or 초록 (1번째 집) 빨강 (2번째집) => 위의 방식처럼 이루어져야 합니다. =>2번째 집에 빨강을 칠하고 싶을 경우, 이전의 집의 색이 파랑 혹은 초록이어야 합니다. **주의할 점 : row가 0인 지점부터 값을 넣어줄 경우 (0-1) 지점을 참조할 수 있으니 실수하지 않도록 합니다. 점화식은 아래와 같습니다. dp[i][0] += min(dp[i-1][1] , dp[i-1][2]); dp[i][1] += min(dp[i-1][0] , d..
-
c++ array 배열 초기화 하는 방법유용한 정보 2020. 7. 3. 16:40
알고리즘 문제를 풀 때 배열을 초기화해야 하는 경우들이 있습니다. 해당 방법을 정리해보았습니다. 1.간단한 배열 초기화 방법 int arr[3] = {0,1,1}; 2. Bool형 배열 초기화 방법 bool arr2[3] = {false}; => 이와 같은 방법으로 초기화 시, 초기값들을 모두 false로 초기화할 수 있습니다. => 이와 같은 방법을 사용할 시, 처음 값만 설정한 값으로 설정되며 나머지 값은 false로 초기화됩니다. bool arr[3] = {true, true, true}; => 이와 같은 방법으로 배열을 모두 true로 초기화 할수 있습니다. 3. 선언한 뒤에 함수를 통해 초기화하는 방법 - fill_n fill_n(arr2, 3, true); => 초기화하려는 배열의 주소(배열의..
-
백준 11724 - 연결 요소의 개수백준 algorithm 2020. 7. 3. 16:27
=> graph의 연결 요소의 개수를 묻는 문제입니다. => 기존의 DFS와 BFS를 이해하신 분이라면 쉽게 풀 수 있는 문제입니다. 기존 방식대로기존 방식대로 입력을 받으며, 인접 행렬, 인접 리스트, 간선 리스트, check 행렬을 생성합니다. 연결 요소의 개수를 확인해야하므로 DFS나 BFS를 통해 Path를 찾으며 해당 check 행렬을 최신화합니다. 정점의 개수에 해당하는 check행렬이 모두 true가 될 때까지 진행합니다. 해당 프로세스를 진행하며 연결요소의 개수를 구합니다. *저는 DFS를 통해 연결요소의 개수를 셌습니다. 하지만 code에는 BFS함수까지 구현했으므로 BFS로 해도 무방합니다. *둘 중 어느 방법을 골라서 할지는 코드 작성자의 취향에 따라 갈립니다. #include #in..
-
백준 1260 -DFS와 BFS백준 algorithm 2020. 7. 3. 13:14
=> DFS와 BFS를 사용할 줄 아는지 묻는 문제였습니다. => 기본적으로 입력을 받을때 인접 행렬, 인접 리스트, 간선 리스트를 만들어두면 편합니다. => DFS와 BFS code 역시 형식이 정해져있으므로, 이해와 함께 암기해두시면 편리합니다. => DFS와 BFS에 대한 설명은 생략하겠습니다. => DFS : 깊이를 끝까지 따라가며 탐색하는 방법 ( stack을 사용하지만, 코드에서는 재귀를 통해 구현 가능) => BFS : 너비를 우선시하면 탐색하는 방법 ( queue를 사용하여 코드로 구현 가능) void dfs(int x, int n) //x는 탐색 시작점, n은 정점의 갯수 { check[x]=true; cout
-
백준 2941 - 크로아티아 알파벳카테고리 없음 2020. 6. 17. 16:36
=> 문자열을 다룰 줄 아는지 물어보는 문제입니다. => string 헤더를 제대로 이해하고 내장되어있는 함수들을 통해 풀 수 있습니다. => 저는 처음에 if문으로 구현할 수 있을 줄 알았는데, 해당 방식으로 하면 참조하지 말아야 할 위치를 참조하는 등의 잘못이 생깁니다. => string의 find() 함수와 replace 함수를 적절히 사용하여야 합니다. 크로아티아 알파벳을 담을 배열을 생성하고 초기화한다. 해당 크로아티아알파벳을 찾을 경우 해당 구간을 *로 바꿔준다 위의 과정은 같은 단어가 여러 번 들어가 있을 경우를 위해 다시 검색되지 않도록 하기 위해서 하는 과정이다. 해당 과정을 진행하며, 크로아티아 알파벳의 개수와 해당 알파벳의 길이를 점진적으로 구한다. 문자열의 길이 - 크로아티아 알파벳..
-
백준 1759 - 암호만들기백준 algorithm 2020. 6. 17. 15:44
=> 입력값의 범위가 작기 때문에 브루트 포스로 해결할 수 있습니다. ** 본인이 작성한 코드에는 정렬의 과정이 표현되어있지 않기 때문에, 함수 진입 전에 alpha vector의 sort과정이 필요합니다. #include #include #include #include using namespace std; bool check(string &password) { int conso=0; int vowel=0; for(char x : password) { if(x == 'a' || x=='e' ||x=='i' || x == 'o' || x== 'u') { vowel ++; } else{ conso++; } } return conso >= 2 && vowel >=1; } void go(int n, vector..
-
백준 2839 - 설탕 배달백준 algorithm 2020. 6. 5. 23:02
=> 브루트 포스 문제는 아니지만, 브루트 포스 문제로 해결하였습니다. 5를 3보다 더 많이 써야 효율적인 알고리즘입니다. 5를 더 많이 쓰기 위해 이중for문의 안쪽에 5를 위치하였습니다. 그후 3를 바깥쪽 for문에 위치하였습니다. 입력 받은 값과 i j와 3 5 를 곱한 값이 같은지 확인합니다. 이중for문이 끝나도 원하는 값이 없을 경우 -1을 출력합니다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; int FiveLimit = (N / 5); int ThreeL..