ALGORITHM

    [Recursion] 재귀 호출 기본 개념 및 예제
    ALGORITHM/Recursion

    [Recursion] 재귀 호출 기본 개념 및 예제

    들어가며 완전 탐색을 할 때에 사용할 수 있는 방법 중 하나인 재귀 호출에 대해 공부해보고자 합니다. 이번 포스팅은 알고리즘 문제해결전략(구종만 저) 6장을 공부하며 정리한 내용입니다. 재귀 호출 재귀 함수(Recursive function)란, 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 의미합니다. 반복문을 재귀 함수로 바꿔 구현해보면, 재귀 호출의 기초적인 특징을 확인할 수 있습니다. 아래 예시에서는 기존 반복문 사용에 비해 재귀 호출의 이점이 별로 없지만, 기초적인 특징은 확인이 가능합니다. 1부터 n까지의 합을 구하는 반복문 int sum(int n) { int ret = 0; for(int i = 1; i

    [leetcode] 1315. Sum of Nodes with Even-Valued Grandparent
    ALGORITHM/DFS(Depth First Search

    [leetcode] 1315. Sum of Nodes with Even-Valued Grandparent

    1315. Sum of Nodes with Even-Valued Grandparent 문제 이진 트리(Binary Tree)가 주어지면, grandparent가 짝수인 노드의 합을 구하는 문제이다. 풀이 이진 트리는 TreeNode structure로 구현되어 있다. 각 노드별로 left와 right를 가리키는 포인터를 가지고 있다. 따라서, root 노드부터 훑으면서, 각 노드가 짝수라면 해당 노드의 grandchild의 합을 구하면 된다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), r..

    [leetcode] 1221. Split a String in Balanced Strings
    ALGORITHM/Greedy

    [leetcode] 1221. Split a String in Balanced Strings

    1221. Split a String in Balanced Strings 문제 Balanced string은 동일한 개수의 'L'과 'R'로 이루어있는 string을 의미합니다. 주어진 string s을 최대한 많은 balanced string으로 나눈 후 balanced string개수를 출력합니다. 풀이 Balanced string은 RL, LR, RRLL, LLLRRR, RRRLRLLL과 같이 R과 L의 개수가 동일한 string을 의미합니다. 따라서, L과 R의 개수를 각각 세어 동일한 개수만큼 나오면 balanced string이 하나 더 생긴 것으로 볼 수 있습니다. class Solution { public: int balancedStringSplit(string s) { int balanc..

    [leetcode] 605. Can Place Flowers
    ALGORITHM/Greedy

    [leetcode] 605. Can Place Flowers

    605. Can Place Flowers 문제 긴 화단에 중간 중간 식물이 심어져 있다. 식물은 바로 붙어서 자랄 수 없어 적어도 한 칸씩 띄워서 자라야 한다. flowerbed라는 integer array는 0과 1로 구성되어 있으며, 0은 비어있음을 의미하고 1은 식물이 심어져 있음을 의미한다. n 값은 새로 심고자 하는 식물의 수이고, n개를 심을 수 있을 경우 true이고 심을 수 없을 경우 false를 반환한다. 풀이 답안1의 경우는 discuss를 보지 않고 처음 풀었을 때 나온 답안이라 좀 코드 자체가 복잡해 보인다. 답안1은 flowerbed를 0번째 인덱스부터 반복문을 돌 때, i번째의 위치가 맨 처음인지, 맨 마지막인지, 중간인지 나누어 풀었다. 만약 i가 0이라면, (i+1)번째가 0..

    ALGORITHM/C++

    [sort] sort(정렬) 알고리즘

    sort algorithm sort 알고리즘은 헤더 파일에 속해 있으므로, #include 을 하여 사용해야 합니다. sort(start, end)를 이용하여 [start,end) 범위에 속하는 인자들을 오름차순(default)으로 정렬할 수 있습니다. 따로 구현하지 않고 algorithm 헤더에 속한 sort을 사용하면, quick sort로 정렬된 결과를 얻을 수 있습니다. vector 정렬 예 오름차순 정렬 #include #include #include using namespace std; int main() { vector v = {1,3,2,4,6,8}; printf("Before sort:::\n"); for(int i = 0; i < v.size(); i++) printf("%d ", v[..

    [leetcode] 455. Assign Cookies
    ALGORITHM/Greedy

    [leetcode] 455. Assign Cookies

    455. Assign Cookies 문제 i번째 아이는 g[i] 이상 사이즈의 쿠키를 받아야 만족하고, j번째 쿠키의 사이즈를 s[j]라고 한다. 이때, s[j] >= g[i]일 때 i번째 아이에게 j번째 쿠키를 줄 수 있다. 이 문제의 목적은 최대한 많은 아이들에게 만족할만한 쿠키를 나눠주는 것이다. 풀이 최대한 많은 아이들에게 쿠키를 나눠주어야 하므로, 각 아이들이 만족할만한 쿠키 사이즈 중 가장 작은 사이즈를 나눠줘야 한다. 따라서, 아이들이 만족할 쿠키 크기 벡터인 g 벡터를 오름차순으로 정렬하고 줄 수 있는 쿠키 사이즈 개수 벡터인 s 벡터를 오름차순으로 정렬해야 한다. 정렬된 벡터들의 값을 비교하면, 각 아이에게 줄 수 있는 최소 크기의 쿠키를 줄 수 있다. 답안 class Solution {..

    [leetcode] 392. Is Subsequence
    ALGORITHM/Greedy

    [leetcode] 392. Is Subsequence

    392. Is Subsequence 문제 string s와 string t가 문제에 주어지며 s가 t안에 속하는지 true or false로 답하는 문제이다. 여기서의 subsequence란, 오리지널 string에서 특정 문자들을 지웠을 때 나올 수 있는 string을 뜻한다. (예: "ace"는 "abcde"의 subsequece) 풀이 이 문제는, string s에 있는 각 문자들이 string t에 있는지 하나씩 확인하고 지나가면 된다. 즉, s의 첫 문자를 t의 첫 문자부터 비교하여 동일한 문자가 나오면 s의 다음 문자를 t의 다음 문자(s와 동일했던 문자 다음)와 비교하는 식으로 풀면 된다. 나는 s의 문자들이 모두 t에 있는지 체크하는 용도로 count 변수를 사용했는데, 해당 변수를 사용하..

    ALGORITHM/C++

    [string] string to char vector/배열

    string to char 배열 #include #include using namespace std; int main() { string str = "hello"; char charStr[str.length()+1]; strcpy(charStr, str.c_str()); for(int i = 0; i < sizeof(charStr)/sizeof(char); i++) printf("%c", charStr[i]); printf("\n"); return 0; } string to char vector string을 새로운 char vector로 만드는 경우 #include #include #include using namespace std; int main() { string str = "hello!"; ve..

티스토리툴바