문제 풀이

[BOJ 알고리즘, C++] #14889_스타트와 링크, DFS, 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 14889_스타트와 링크 깊이 우선 탐색을 통해 차이 값이 최소가 되는 두 배열을 구합니다. 문제 풀이 1. 깊이 우선 탐색 알고리즘 활용 [BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색 [BOJ 알고리즘, C++] #15649_N과 M(1), 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 15649_N과 M (1) 깊이 우선 탐색을 통해 중복이 없는 수열의 개수를 구합니다. 문제 풀이 1. 깊이 우선 탐색(DFS) 루트 노드. webddevys.tistory.com 2. 풀이 깊이 우선 탐색을 통해 각 정점(각 선수)을 방문합니다. 더불어, 루트 노드를 시작으로 인접 노드들..

[BOJ 알고리즘, C++] #9663_N-Queen 문제, 백 트래킹 BOJ 알고리즘 문제 풀이, 9663_N-Queen 문제 백 트래킹을 통해 같은 행 혹은 대각선에 Queen이 위치하는지 확인합니다. 문제 풀이 1. 백 트래킹 깊이 우선 탐색을 기반한 알고리즘으로 "후보 해"의 집합에서 "최적해" 집합을 찾아내는 알고리즘입니다. 먼저, 깊이 우선 탐색은 트리 구조를 기반으로 수행되는 알고리즘입니다. 반면, 백 트래킹 알고리즘은 "조건"에 맞지 않는 정점 혹은 브랜치에 대한 "DFS"를 진행하지 않습니다! 정리하자면, "백트래킹 알고리즘 = DFS + 특정 조건"이라고 볼 수 있겠습니다! 2. 백트래킹 알고리즘의 대표 문제, N-Queen 문제 N x N 체스판에서 퀸들이 서로 공격할 수 없도록 배치..

[BOJ 알고리즘, C++] #15649_N과 M(1), 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 15649_N과 M (1) 깊이 우선 탐색을 통해 중복이 없는 수열의 개수를 구합니다. # 문제 # 풀이 1. 깊이 우선 탐색(DFS) 루트 노드 혹은 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색하는 방법입니다. 2. DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태이다. 어떤 노드를 방문했었는지 방문 여부를 반드시 검사해야 합니다. 너비 우선 탐색보다 간단합니다. 검색 속도 자체는 너비 우선 탐색에 비해 느립니다. 3. 예제 0번 노드를 시작으로 깊이 우선 탐색을 시작합니다. 0번과 인접한 노드들을 순차적으로 순회합니다. 0번과 인접한 1번 노드를 방문합니다...

[Programmers 알고리즘, C++]#Level 2_이진 변환 반복하기 Programmers 알고리즘 문제 풀이, Level 2_이진 변환 반복하기 이진 변환 알고리즘과 STL 알고리즘을 활용하여 풀이하는 문제입니다. 문제 풀이 #include #include #include using namespace std; bool Pred(char c) { return c == '0'; } vector solution(string s) { vector answer; int delete0Cnt = 0; int decToBinCnt = 0; vector tmpV; while(s != "1") { // 1. 0 제거, for 문을 돌면서 삭제하면 String에 직접적인 변화 for(int i=0; i 이진 변환 ..

[Programmers 알고리즘, C++]#Level 2_JadenCase 문자열 만들기 Programmers 알고리즘 문제 풀이, Level 2_JadenCase 문자열 만들기 cctype 제공 함수를 활용하여 풀이하는 문제입니다. 문제 풀이 /* * #include 제공 함수 주의할 점 : islower(), isdigit(), isupper() 등의 함수는 반환 값이 int입니다. if(islower(str[i]) == true)는 정상적으로 수행되지 않습니다! */ #include #include #include using namespace std; string solution(string s) { string answer = ""; bool changeCheck = true; if (isdigi..

[Programmers 알고리즘, C++]#Level 1_정수 내림차순 정렬 Programmers 알고리즘 문제 풀이, Level 1_정수 내림차순 정렬 char int 간 변환과 string 정수 간 변환을 활용하여 풀이하는 문제입니다. 문제 풀이 // 1. char to int = -'0' // 2. int to char = +'0' // 3. stoi, stol, stof, stod 활용 #include #include #include using namespace std; long long solution(long long n) { long long answer = 0; vector v; string str = to_string(n); for(int i=0; i char 변환을 위해 + '0' 해줍..

[BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound BOJ 알고리즘 문제 풀이, 10816_숫자 카드2 정렬 알고리즘을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. 문제 풀이 1. Map 컨테이너 활용 // 1. Map 컨테이너를 활용했지만, 2번 코드보다 소요 시간과 메모리 사용량이 비교적 훨씬 높음... #include #include #include typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; // 숫자 + 개수 map m; vector v; cin >> N;..

[BOJ 알고리즘, C++] #10815_숫자 카드, 이진 탐색, Binary Search BOJ 알고리즘 문제 풀이, 10815_숫자 카드 이분 탐색을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 이진 탐색(Binary Search) Details [정의] : 정렬된 원소 목록을 반으로 나누어 찾고자 하는 원소와 중심이 되는 원소를 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 중심 원소를 옮겨서 반복적으로 비교 작업을 수행합니다. 시간 복잡도는 O(log n)으로 선형 탐색보다 뛰어난 성능을 보여줍니다! 다만 몇 가지 단점들이 물론 존재합니다! [특징] : 정렬 상태의 자료구조에서만 가능합니다. 그리고, 연결 리스트에서 사용이 힘듭니다...

[BOJ 알고리즘, C++] #1008_C++ A/B, 부동 소수점, precision(), fixed BOJ 알고리즘 문제 풀이, 1008_A/B 나누기 값을 주어진 부동소수점 자리까지 출력하기 문제 풀이 1. stdio 사용 #include int main() { double a; double b; scanf("%lf, %lf", &a, &b); printf("%.13lf", a / b); return 0; } 2. iostream 활용 // 1. std::cout.precision(n) : 실수 전체 자리수를 n까지 표현 double a = 3333.333333; std::cout.precision(6); cout

[BOJ 알고리즘, C++] #25305_커트라인, 정렬 알고리즘, STL, 내림차순 BOJ 알고리즘 문제 풀이, 25305_커트라인 STL이 제공하는 정렬 알고리즘을 통해 커트라인 바로 위 점수를 출력하는 문제 문제 풀이 [Basic C++] #32-3_STL 정렬 알고리즘 [Basic C++] #32-3_STL 정렬 알고리즘 C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다. "전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다. 정렬 알고리즘 webddevys.tistory.com // greater() : 내림차순 정렬 // less() : 오름차순 정렬, Default sort ( begin(v), end(v), less() or greater..