전체 글
-
Stack #1 -카테고리 없음 2019. 8. 30. 08:05
유용한 설명과 문제 풀이 https://www.acmicpc.net/blog/view/12 #include #include using namespace std; int a[100000]; int main() { int n; scanf("%d", &n); for (int i = 0; i a[i]) { int height = a[s.top()]; s.pop(); int width = i; if (!s.empty()) { width = (i - s.top() - 1); } ..
-
monotone stack스택(Stack) 2019. 8. 24. 22:08
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net -- 처음에 문제를 접근 했을때 bruth-force 로 문제를 접근 하였다. #include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector arr(n); for (int i = 0; i < n..
-
Angry Professor구현(Implementation) 2019. 4. 18. 13:43
https://www.hackerrank.com/challenges/angry-professor/problem Angry Professor | HackerRank Decide whether or not the class will be canceled based on the arrival times of its students. www.hackerrank.com 1. 문제 교수는 최소의 학생이 재시간에 도착하면 수업을 진행 하려고 한다. 문제의 k 는 교수가 원하는 제시간에 도착한 최소의 학생 수를 의미하며 n 개의 학생의 도착 시간이 주어진다. 2. 알고리즘 키워드 - 구현 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // Complete the angryProf..
-
Ransom Note해커랭크(HackerRank) 2019. 3. 12. 10:05
https://www.hackerrank.com/challenges/ctci-ransom-note/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps 1. 문제 주어진 문자열 벡터요소에 다음 벡터요소가 포함 되어 있는지 확인 하는 문제 2. 알고리즘 키워드 - hash 3. 코드 #include using namespace std; vector split_string(string); // Complete the checkMagazine function below. void checkMagazine(vector magazine, vector note) { so..
-
Left Rotation해커랭크(HackerRank) 2019. 3. 12. 08:36
1. 문제 2. 알고리즘 키워드 - 구현 * 문제 풀이 입력 으로 들어오는 배열에 요소를 왼쪽으로 d 만큼 ROTATION 하는 문제이며 d 입력 값에 따라 반복적으로 연산량이 증가 된다. 초기 접근은 d 만큼 반복문 내에서 swap 하도록 구현 하였으나 timeout 이 발생하여 다른 방법으로 접근 하기로 했음 문제에 주어진 조건에서 d 는 배열의 크기보다 작은 수로 입력 됨으로 아래와 같은 식을 세울 수 있다. 이동 될 위치 = ( 배열의 크기 - d + 현재 배열의 위치) % 배열의 크기 문제에서 주어진 예제 기준으로 대입 해 본다면 이동 될 위치는 아래 와 같다. index 0 일 때 = (5 - 4 + 0) % 5 이동 될 위치는 1 index 1 일 때 = (5 - 4 + 1) % 5 이동 될..
-
백준 1937번: 욕심쟁이 판다깊이우선탐색(DFS) 2019. 1. 20. 18:38
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 키워드 - DFS, 구현 Source #include #include #include #include #include #include..
-
백준 2511번: 카드놀이구현(Implementation) 2019. 1. 20. 16:14
https://www.acmicpc.net/problem/2511 1. 문제 2. 알고리즘 키워드 - 구현 승자에게 각각 3점을 부여, 비긴 경우에는 각각 1점 부여 점수가 같은 경우 마지막에 이긴 사람이 승자 3. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long int main() { std::ios::sync_with_stdio(false); cin.t..
-
백준 2512번: 예산이분 탐색(Binary Search) 2019. 1. 20. 15:48
https://www.acmicpc.net/problem/2512 1. 문제 2. 알고리즘키워드 - 이분탐색, 구현 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100#define INF 0x7fffffff#define CENDL "\n"#define ll long long..