오구의코딩모험

코딩테스트 대비를 위해해커랭크에서 누적합 / 이분 탐색 / 힙 / 투 포인터 관련 알고리즘연습하기..! 1. The Maximum Subarray (Normal) 📌 문제 요약주어진 배열로 만들 수 있는 부분 배열 중연속적인 원소들의 최대 합과 단순 최대 합을 구하라. 구현 코드vector maxSubarray(vector arr) { vector answer; int addNum[100001]; fill(addNum, addNum+arr.size()+1, 0); addNum[0] = arr[0]; for(int i=1; i0) positive += num; if(positive == 0) positive = *max_element(arr.begin(), a..

코딩테스트 대비를 위해해커랭크에서 해시테이블 관련 알고리즘연습하기..! 1.Ransom Note (Easy) 📌 문제 요약두 문자열 리스트(megazine, note)에서 단어 빈도 비교magazine의 단어들로 note를 만들 수 있는지 확인 구현 코드void checkMagazine(vector magazine, vector note) { unordered_map um; for(string s : magazine) um[s]++; for(string s : note){ if(um[s]) um[s]--; else { cout 💡 알고리즘 요약unordered_map 으로 magazine의 단어 빈도 세기note의 각 단어가 m..

코딩테스트 대비를 위해해커랭크에서 문자열 관련 알고리즘연습하기..! 1. String Construction (Easy) 📌 문제 요약문자열을 구성할 때, 처음 등장하는 문자는 1달러,이미 등장한 문자는 복사하며 비용은 0달러 이다.총 비용을 계산 ! 구현 코드int stringConstruction(string s) { int freq[26] = {}, cnt = 0; for(char c : s) { if(freq[(c-'a')]==0) { cnt++; freq[(c-'a')]=1; } } return cnt;} 💡 알고리즘 요약문자열의 서로 다른 문자 개수가 곧 정답 구현 팁unordered_set o..

https://www.acmicpc.net/problem/1717 문제 3줄 요약1. n+1개의 집합이 있다.2. 합집합 연산과 두 원소가 같은 집합인지 판별하는 연산을 수행한다.3. 1로 시작하는 입력에 대해서는 포함 여부를 출력한다. 문제의 제한 사항을 확인해보면n은 최대 10^6 이므로 단순히 set를 이용한 집합 연산은 불가능하다고 생각하였다. 해당 문제에서는Disjoint-set(서로소 집합, 분리 집합)을 표현하는 Union-Find 알고리즘을 이용하였다. 해당 알고리즘이 익숙하지 않다면아래 영상을 참고하길 바란다!! https://www.youtube.com/watch?v=rE-OUyZJgOk 위와 같은 집합이 존재할 때,부모 정점 테이블을 이용하여 집합의 연결을 수행한다. 연결..

https://www.acmicpc.net/problem/11657 문제 3줄 요약1. N개의 도시가 있다. 1번 도시가 기준이다.2. 도시를 건너는 버스는 시작 도시, 도착 도시, 걸리는 시간(양수가 아닌 경우 존재)으로 표현한다.3. 나머지 도시로 가는 가장 빠른 시간을 구해라. 만약 시간을 무한히 오래 전으로 되돌릴 수 있다면 -1을 출력한다. 2번 도시부터 차례대로 시간을 출력하되해당 도시로 가는 경로가 없는 경우 또한 -1을 출력한다. 여기서무한히 오래 전으로 되돌릴 수 있다는게 무슨 뜻 일까? 걸리는 시간 C가 음수이며,음수가 포함된 경로가 순환을 이루면반복을 통해 최단 시간이 무한한 음수로 가는 경우를 뜻하게 된다. 따라서최단 경로 알고리즘인 다익스트라 알고리즘은 사용할 수 없으며,벨만..

https://www.acmicpc.net/problem/1749 문제 3줄 요약1. 동주와 점수 따먹기 게임을 한다.2. N*M 행렬 각 칸에 -10'000 ~ 10'000의 정수를 하나씩 쓴다.3. 행렬의 부분 행렬의 합이 최대가 되게 구하라!   예제를 보고누적합을 생각하니 DP를 사용해야겠는데?라는 생각이 떠올랐고풀었던 유사한 문제가 생각났다.  https://59travel.tistory.com/104 [C++] BOJ 15724번 : 주지수https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를59travel...

https://www.acmicpc.net/problem/1074  문제 3줄 요약1. 2^N x 2^N 크기의 2차원 배열을 Z모양으로 탐색한다.2. 순서는 왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래 순으로 Z 모양이다.3. r행 c열은 몇 번째로 방문하는지 출력해라!  N=3일 경우는 아래와 같이 탐색한다.  그림만 봐도 끔찍하다. 이번 문제는 큰 문제를 작은 문제로 나누어서 해결하는분할 정복 문제이다. 따라서 Z모양으로 탐색하는 부분과재귀를 통한 2 x 2 사각형 탐색하는 부분이 필요하다. 작성된 코드를 보고 분석해보자.   if(pow(2,w-1) != 1){ for(int i=x; i 한 변의 길이가 2^w이며, (x, y) 좌표부터 시작하는 사각형은2x2 길이의 사..

https://school.programmers.co.kr/learn/courses/30/lessons/388353 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 3줄 요약1. n x m 크기의 물류창고에 출고 방식은 지게차와 크레인 두 가지가 있다.2. 지게차는 외부와 접근할 수 있는 경우 / 크레인은 어느 것이든 접근해서 꺼낼 수 있다.3. 출고 요청이 끝나고 난 후, 남은 물류 컨테이너 수를 출력해라.   물류 창고 컨테이너 적재량(= n)은 최대 50,컨테이너 길이(= m)의 최대 또한 50이다. 출고 요청은 최대 100개이며,알파벳 한 개로 구성된 요청은 지게차,알파벳 두 개로 구성된 요..

https://www.acmicpc.net/problem/6443 문제 3줄 요약1. 씬디는 애너그램 프로그램을 만들어 줄 수 있는 남자가 좋다.2. 애너그램은 입력받은 문자열의 단어들을 재배치한 단어들을 출력하는 것이다.3. 재배치한 문자열의 중복은 제외하고 알파벳 순서로 출력해라.  예시를 보면 바로 이해가 가능하다. (입력) abc → (애너그램) → (출력) abc acb bac bca cab cba abc가 입력으로 주어지면a 1개, b 1개, c 1개로 만들 수 있는 문자열들을 출력하면 된다. 출력할 때알파벳 순서대로 출력해야하니 위와 같이 순서로 출력된다. 문자열의 최대 길이가 21이라고문제에 조건으로 주어졌다. 따라서 완전 탐색은 불가능하기에조합 함수를 사용하거나백트래킹을 통한 탐색이 필요..

https://school.programmers.co.kr/learn/courses/30/lessons/388352 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 3줄 요약 1. 비밀 코드는 1 ~ n까지의 서로 다른 정수 5개 (오름차순)이다.2. 이 비밀 코드를 맞추기 위해 m 번의 시도를 하며, 몇 개 맞췄는지 알려준다.3. 시도한 결과를 보고 비밀 코드로 가능한 정수 조합의 개수를 출력하자.    제한 사항을 보니조합의 개수가 최대 30C5 (약 14만개)이다. 따라서 브루트포스 알고리즘을 이용해도풀 수 있을 것이라 생각했고 그 결과..무식하게 5중 포문을 작성했다. 하지만 값을비교하는 과..