알고리즘 (7) 썸네일형 리스트형 [카카오블라인드코테2021] 카드짝맞추기 카카오 코테 준비를 위해 풀어본 문제 매출하락최소화보다 쉬운 문제로 돼있지만 구현능력과 복잡한 시뮬레이션 문제로 2시간30분의 시간이 걸렸다. 출처 : programmers.co.kr/learn/courses/30/lessons/72415 문제해결을 어떻게 했는지 설명을 하자면, 먼저 무조건 가까운 카드를 고른다고 최솟값이 될것 같지 않았다. 그래서 모든 카드를 다 찾아봐야겠다고 생각했다. card_location 이라는 변수에 카드의 좌표를 입력해서 좌표를 찾는데 걸리는 시간을 줄이고자 했다. pair_loaction 이라는 변수에는 카드의 짝이 되는 card_location의 인덱스를 입력해서 짝을 찾는데 걸리는 시간을 줄였다. 현재 위치에서 다음 위치로 가는데 '최소' 움직임을 알기위.. [카카오블라인드코테2021] 매출하락최소화 카카오 코테 준비를 위해서 문제를 풀어보았다. 풀이 시간은 1시간 30분 정도로 오래걸림.. DP를 이용하였고, Top-Down 방식으로 접근하였다. 출처 : [ programmers.co.kr/learn/courses/30/lessons/72416 ] 내가 생각한 알고리즘에 대해서 간단히 설명을 하자면, 보스가 워크숍에 참석을 하게되면,(//참석을 함) 부하가 워크숍에 참석하든 안하든 상관이 없으므로, 참석했을때와 참석하지 않았을때의 최솟값을 더해준다. 보스가 워크숍에 참석을 안하게 되면(//참석을 안함) 무조건 한명은 참석해야하므로 만약에 모두가 참석하지 않을때가 가장 값이 작다면, 참석했을때와 참석하지 않았을때의 차가 가장 적은 부하를 참석시킨다. #include #include #define de.. [백준 1918] 후위 표기식 후위 표기시 답. 재귀를 이용해서 풀었고 *./,+,- 우선순위에 관해서, get_op_prior를 수정해서 op를 추가하는 것도 가능하게 만들었다. 알고리즘에 대한 대략적인 설명으로는 A+B*C 라는 입력이 들어오면 B*C를 곱해주고 nums에 추가해서 나중에 A+(B*C) 가 결과를 내놓는 방식이다. 괄호가 들어오면 재귀를 통해 결과를 도출한다. tree를 수정해서 char 에는 op 값을 넣고 int num이라는 변수를 추가한다면 숫자가 들어오는 중위표현식도 트리로 만드는 것이 가능한 알고리즘을 만들었다. 아래 알고리즘은 get_op_prior, tree를 수정해서 중위표현식을 유연하게 가져올수 있는 알고리즘이다. #include #include #include #include using names.. [백준 10972] 다음순열 : next_permutation 처음 이 문제를 풀때 c++ 에 next_permutation 이 있는지 모르고 문제를 풀었다. next_permutation이 어떻게 동작하는 지 이해해 보자! 4 6 5 3 2 1 의 다음순열은 어떻게 구할 수 있을까? 내가 한 짓은 브루트 포스로 모든 순열을 출력하고 비교해가며 유추하였다. 위 순열은 맨 앞의 수를 제외하면 내림차순으로 정렬되어 있다. 이 수의 다음 순열은 4의 다음수인 5 가 오게 되고 나머지 수는 오름차순으로 바뀐결과가 다음 순열이 된다. 5 1 2 3 4 6 그렇다면 1 3 6 5 4 2 이라면? 1 4 2 3 5 6 가 다음 순열이 된다. 1 2 4 6 3 5 이라면? 1 2 4 6 5 3 아래는 1 ~ 6 까지의 조합의 결과입니다. 제 설명과 번갈아서 보다보면 이해가 될것이.. 정규표현식(regex) 정리. 정규표현식 정규표현식에 쓰이는 규칙. (?:...) : ?????!!! 위 규칙의 대부분이 이해가 가지만 이해가 가지 않아 설명을 하겠습니다. 설명에는 (non-capturing) 이라고 되어있습니다. 물음표를 넣지 않고 그냥 (abc) 라는 그룹을 만든다면, 맨마지막에 String Replacement: $n 을 통해 n 번째 그룹에 있는 글자를 가지고 올 수 있습니다. 하지만, (?:...) 을 통해 그룹을 만들게 되면 $n을 통해 글자를 가져올 수 없지만 그만큼 메모리를 아끼게 되는 효과가 있습니다. 가장 많이 쓰이는 정규 표현식 4가지 1. regex_match: 문자열 전체가 정규 표현식에 맞는 지 확인. 간단한 예시 입니다. #include #include using namespace std;.. [백준 2671 잠수함식별] : 규칙 일치여부 regex_match 잠수함 문제를 regex_match(string s, regex re)을 이용해서 간단하게 풀어보겠습니다. regex_match : re 의 규칙에 맞으면 true, 틀리면 false를 리턴해 주는 함수입니다. regex re("(100+1+ | 01)+"): 10000111111 이 반복되거나 or 01 이 반복되는 스트링이라면 이용하여 간단히 정규표현식을 이용하여 정답을 얻을 수 있습니다. 아래는 정답 코드입니다. #include #include #include #include using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0); string s; cin>>s; regex re("(100+1+|01)+"); cout [백준 2042] 구간 합 구하기 세그먼트 트리의 기본중에 기본 구간 합 구하기 알고리즘입니다. a~b 까지의 합을 구하기 위해서 세그먼트 트리를 사용하면 입력값의 2배의 공간이 필요하지만 O(logn) 의 시간복잡도로 결과를 가져올수 있어 유용한 트리입니다. 저는 세그먼트 트리 문제를 풀때면 아래와 같이 그림을 그려 해결합니다. 8개의 원소를 가지는 트리을 만들면 아래와 같이 만들어집니다. 이해하기 편하게 그림으로 표현 하겠습니다. seg[tree_size*2]={0} : 8 1 2 3 4 5 6 7 8 의 입력이 들어왔을때 세그먼트 트리 작동. make_seg: 첫번째 줄에서는 tree_size+i 에 입력값을 추가해 줍니다. 두번쨰 줄에서 인덱스가 tree_size-1 ~ 1 까지 트리를 초기화 해줍니다. update_seg(idx.. 이전 1 다음
