코딩 테스트/백준 (C++, Python)32 cpp) 백준 1181: 단어 정렬 Problem https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 알파벳 소문자로 이루어진 N개의 단어가 들어오면 다음과 같은 조건에 따라 정렬하시오. 1) 길이가 짧은 것부터 2) 길이가 같으면 사전 순으로. 단, 중복된 단어는 하나만 남기고 제거해야 한다. Solution #include #include #include using namespace std; bool check(string a, string b){ int i=0; //.. 2023. 6. 13. cpp) 백준 1003: 피보나치 함수 Problem https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net fibonacci(3)의 경우 1은 2번 출력되고, 0은 1번 출력된다. fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오. Solution 매번 재귀함수를 호출해서 수를 구한다면 시간 초과가 뜨기 때문에 규칙성을 찾아 문제를 해결해야 한다. 과정을 짚어보면, '0 호출 횟수'와 '1 호출 횟수' 모두 기존의 피보나치 함수와 유사한 것을 확인할 수 있다. n 피보나치 수 0 호출 횟수 1 호출 횟수 0 0 1 0 1 1 0 1 .. 2023. 6. 10. cpp) 백준 1541: 잃어버린 괄호 Problem https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 .. 2023. 6. 9. cpp) 백준 25206: 너의 평점은 Problem https://www.acmicpc.net/problem/25206 25206번: 너의 평점은 인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치 www.acmicpc.net 전공평점을 계산해주는 프로그램을 작성해보자. 전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다. P/F 과목의 경우 등급이 P또는 F로 표시되는데, 등급이 P인 과목은 계산에서 제외해야 한다. Solution #include #include #include #include using namespace std; int main(){ string score; do.. 2023. 6. 9. cpp) 백준 1260: DFS와 BFS Problem https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하시오. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더 이상 방문할 수 없는 경우 종료한다. 정점 번호는 1번부터 N번까지! Solution #include #include using namespace std; #define MAX 1001 int n, .. 2023. 6. 9. BFS, DFS 이해하기 Summary 대표 유형 : 경로탐색, 네트워크, 조합 만들기 BFS는 Queue 또는 LinkedList로 구현하고 DFS는 재귀함수로 구현한다. BFS는 모든 경우의 수를 한 걸음씩 수행하기 때문에 최악의 경우 시간 복잡도가 DFS에 비해 낮다. 이에 반해, DFS는 한 가지 경우의 수를 깊이 파기 때문에 최악의 경우에 시간 초과가 날 위험이 있다. Reference https://www.youtube.com/watch?v=BsYbdUnKZ-Y https://velog.io/@vagabondms/DFS-vs-BFS DFS vs BFS 넓고 깊은 알고리즘 세계는 DFS로? BFS로? velog.io 2023. 6. 8. 이전 1 2 3 4 5 6 다음
