백준108

• 

  [백준 1202번 / C++] 보석 도둑 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대로 우선순위에 따라 정렬된 Queue라고 보면 도니다. 와 동일한 라이브러리에서 지원 해주며 특정 원소를 push 를 할 때 O(logN)만에 이루어진다. 해당 시간 baebalja.tistory.com 이 문제는 priority_queue 내림차순인 Max heap구조를 사용하면된다. 먼저, 다음과 같은 예시가 주어졌다고 가정하자 테스트 케이스가 다음과 같이 주어졌을 때 오름차순으로 정렬을 한다. 이후, 가방의 크기가 작은 것부터 해서 담을 수 있는 보석을 하나씩 다 담아본다. 즉, 가방이 담을 수 있는 무게의 크기가 2라면 2이하인 보석들이 Queue에 빼곡빼곡 쌓여있다고 생각하면 된다. 그리고 더이상 담을 수 없는 무게의 보석이.. 백준/그리디 2022. 1. 18.

• [백준 9375번 / C++] 패션왕 총 4가지 (바지 안입을 때, 바지1, 바지2, 바지3) -> 총 4가지 근데 여기서 알몸이 아닌 상태여야 하기 때문에 마지막에 -1 을 해줘야한다. 여기서 map 을 활용하여 의상 종류를 키값으로 갖는 벨류값을 하나씩 증가하여 같은 종류의 의상 개수를 확인할 수 있다. #include #include #include using namespace std; int main() { int n; cin >> n; for (int i = 0; i > nn; map m; for (int j = 0; j > s1; string s2; cin >> s2; m[s2]++; } int sum = 1; for (auto x :.. 백준/구현 2022. 1. 18.

• 

  [백준 6236번 / C++] 용돈 관리 이분 탐색 문제이다. 어떤식으로 이분 탐색을 활용하는지 한번 살펴보자. 먼저 비교할 값을 이분탐색을 통해서 추출해낸다. 예를 들어 low 값과 high 값을 1과 100000값으로 정했으면 low와 high를 이용해 중간값을 구할 수 있다. 다음 그림을 한번 살펴보자. 즉, 첫 중간값은 50,000이 되고 두번째 중간값은 25,000 ... 이런식으로 계속 분할하다 보면 mid가 50일 때가 나올것이다. 이때를 한번 살펴보자 밑에 그림에서 현우가 날마다 사용하려고 하는 돈이 "10 40 30 10 50 10 40" 이라고 가정을 하자. 현재 mid 값인 50으로 현우가 날마다 사용하려고 정한 돈을 계속해서 빼주고 충당이 안된다면 다시 mid값을 초기화 시켜서 반복한다. mid값을 다시 초기화 시키는 작업.. 백준/이분탐색 2022. 1. 17.

• 

  [백준 2343번 / C++] 기타 레슨 [백준 6236번 / C++] 용돈 관리 이분 탐색 문제이다. 어떤식으로 이분 탐색을 활용하는지 한번 살펴보자. 먼저 비교할 값을 이분탐색을 통해서 추출해낸다. 예를 들어 low 값과 high 값을 1과 100000값으로 정했으면 low와 high를 이 baebalja.tistory.com 위의 문제와 거의 똑같은 문제다. 해당 링크 설명을 보고 한번 풀어보자. #include #include #include using namespace std; int l = 1; int h = INT_MAX; int n, m; vector v; bool check(int mid) { for (int i = 0; i mid)return 0; } int sum = 0; int cn.. 백준/이분탐색 2022. 1. 17.

• 

  [백준 1103번 / C++] 게임 쉽게 생각하고 dfs를 적용해서 해보니 메모리 초과가 떴다. 즉, 50X50 배열에서 값에 따른 재귀를 계속 호출하면서 스택에 함수가 계속 쌓이게 된다. 이로인해서 메모리 초과가 발생하게 되는것이다. 그렇기 때문에 방문 했던 곳에 대한 카운트 값을 기록 즉, 메모이제이션 DP를 활용해야했던 문제였다. 먼저, 다음 그림의 예제값으로 그림을 그려보자. (0,0) 좌표에 해당하는 값은 "2" 이다. 그렇다면 상하좌우를 살펴보면서 갈 수 있는 길을 찾게 된다. 나아가야 할 방향의 순서를 "우좌상하" 라고 가정하고 한번 풀어보겠다. 그렇다면 먼저 오른쪽 방향으로 먼저 가보겠다. 이때 vsited(좌표값) 에 방문했다고 체크를 해두자. 오른쪽 방향에서 만나는 숫자는 3이다. 여기서도 똑같이 vsited(좌표값) 에.. 백준/DP 2022. 1. 17.

• 

  [백준 14469번 / C++] 소가 길을 건너간 이유 3 쉬운 문제이니 그림을 참고해서 한번 생각해보자 위와 같이 예제가 주어졌다고 가정하자. 2초에 들어와서 1초동안 8초에 들어와서 3초동안 5초에 들어와서 7초동안 "정렬 시켜준다." 2초에 들어와서 1초동안 5초에 들어와서 7초동안 8초에 들어와서 3초동안 여기서 time이라는 변수를 만들어줘서 time 은 "시작시간 + 검문시간" 을 저장해주는데 이때 중요한점은 "시작시간 + 검문시간" 이 다음 소가 들어오는 시간과 겹칠 수 가 있다. 그렇기 때문에 time이 겹칠 경우 계속해서 누적해주면서 time값을 갱신해준다. #include #include #include using namespace std; int main() { int n; cin >> n; vector v; for (int i = 0; i .. 백준/구현 2022. 1. 17.

• 

  [백준 1781 / C++] 컵라면 [백준 2109번 / C++] 순회강연 처음에 이 문제를 접근할 때 이런식으로 접근 하였다. #include #include #include using namespace std; int check[10001]; int sum; bool cmp(pair p1, pair p2) { return p1.first > p2.first; } int main() {.. baebalja.tistory.com 이 문제는 위의 문제와 완전 동일하다고 볼 수 있다. 이 문제를 풀기 위해서 위의 문제를 먼저 풀어보고 해설을 읽고나서 풀어보길 추천한다. #include #include #include #include using namespace std; int main() { int n; cin >> n; vector v; p.. 백준/그리디 2022. 1. 17.

• 

  [백준 9935번 / C++] 문자열 폭발 처음에 작성했던 코드이다. #include #include using namespace std; string s1, s2, result; int main() { cin >> s1 >> s2; int pos=0; for (auto c : s1) { result += c; if ((pos=result.find(s2))!=string::npos) { result.erase(result.begin()+pos, result.end()); } } if (result.size())cout > s2; for (int i = 0; i = s2.size()) { if (result.substr(result.size() - .. 백준/구현 2022. 1. 17.

• 

  [백준 2178번 / C++] 미로 탐색 해당 문제를 bfs() 를 활용해서 풀었다. bfs나 dfs 를 어느정도 활용 할 줄 아시는 분이라면 쉽게 풀수 있을 것이다. 항상 (1,1) 에서 출발하여 해당 지점부터 map 의 1로 저장되어 있는 부분을 지나가면서 map 의 끝지점까지의 거리를 살펴보면 된다. 첫 시작점부터 map 값이 1인 자리를 visited 배열을 활용해 거리를 갱신해 나간다. 다음 그림을 보면서 어떤식으로 visited가 갱신되는지 확인해보자 그림은 백준 첫 예제를 토대로 그린 것이다. #include #include #include #include #include using namespace std; int map[101][101]; int visited[101][101]; int dx[4] = { -1,0,1,0 }; i.. 백준/DFS BFS 2022. 1. 17.

• [백준 2979번 / C++] 트럭 주차 쉬운 문제다 1부터 100이라는 시간에 겹치는 차의 개수를 배열에 저장한 뒤 그 배열의 인덱스를 돌아보면서 차의 개수에 따른 값을 sum값에 더해주면 된다. #include using namespace std; int arr[101]; int main(){ int a,b,c; cin>>a>>b>>c; for(int i=0; i>x>>y; for(int j=x; j 백준/구현 2022. 1. 17.