백준108

• 

  [백준 19637번 / C++] IF문 좀 대신 써줘 이분탐색을 이용한 문제이다~ #접근방법 이분탐색을 떠올려야 하는 단골 조건은 조건 범위가 10억을 넘길때이다. 뭐 아닌 문제도 있긴하겠지만 이분탐색을 이용해서 풀어야하는 문제는 대부분 10억 정도 되는 값을 조건으로 주어지기 때문에 해당 조건을 만났을 때 이분탐색을 의심해봐야한다. 이번 문제도 마찬가지다. 아래 조건을 보고 이분탐색을 고려해봐야한다. 칭호의 개수 N (1 ≤ N ≤ 10^5)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 10^5)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 10^5) 칭호의 개수가 100000 (10만) 이다. 그리고 캐릭터들의 개수 또한 100000 (10만) 이다. 그럼 여기서 생각을 해야할 것이 10만개의 캐릭터가 모두 상한값을 가지고 있다고.. 백준/이분탐색 2022. 4. 2.

• 

  [백준 13458번 / C++] 시험 감독 해당 문제는 브론즈 문제이지만, 두가지의 예외사항이 있기 때문에 포스팅한다. #접근 방법 로직은 단순하다. 총 감독관은 각 시험장에 한명씩 투입돼야 하기 때문에 각 시험장에 수용하는 인원에다가 총 감독관이 감시할 수 있는 인원을 빼주고 시작한다. 그리고 부감독관이 감시할 수 있는 인원을 나누어주면 부감독관의 인원이 나온다. 그리고 나누었을 때 나머지가 1 이상이라면 한 명의 부감독관이 추가돼야한다. 여기서 예외사항이 있다. 총감독관이 모든 시험장에 투입됐는데 총감독관 혼자서 모든 인원을 감시할 수 있다면 부감독관을 고용할 필요가 없다는 뜻이다. 그렇기 때문에 각 시험장에서 수용하는 인원에서 총감독관이 감시할 수 있는 인원을 뺐을 때 해당 인원수가 0 이하로 떨어진다면 부감독관의 투입을 고려하지말자. 두번.. 백준/그리디 2022. 3. 31.

• 

  [백준 12845번 / C++] 모두의 마블 그리디를 활용해서 풀면 되는 문제이다. #접근방법 그리디의 공통은 어떻게 하면 최적의 값을 구할 수 있는지 알아채야한다. 해당 문제 같은경우에는 문제를 잘 이해해서 의도를 파악해야한다. level 값이 만약 , 10 40 50 20 70 20 10 이런식으로 주어진다면, 어떻게 합을 하면 최댓값을 찾을 수 있을까 고민해야한다. 위의 예제에서 가장 큰 레벨의 값은 70이다. 그렇다면 70에다가 주변에 있는 레벨 값을 다 더해서 생성되는 것이 최대이지않을까? 라는 생각을 하는 순간, 바로 풀 수 있다. 즉, 배열에서 가장 큰 레벨을 가진 값과 인덱스 번호를 저장을 한 다음에 그 값을 기준으로 해서 다른 레벨의 값들을 더해서 만들어진 값들이 최댓값이 된다. #include #include #include us.. 백준/그리디 2022. 3. 31.

• 

  [백준 1976번 / C++ / Find&Union] 여행 가자 Find&Union을 활용한 문제이다. #접근방법 union 벡터를 생성하여 각 인덱스의 부모 노드를 자신의 인덱스 값으로 초기화 한다. map 배열에 i에서 j로 가는 경로가 있으면서 현재 i와 j의 부모노드가 다르다면 Union함수를 호출한다. Union 함수에서는 자신의 부모노드를 찾으러 Find라는 함수를 호출한다. Find 함수에서는 매개변수로 받은 값을 가지고 부모 노드를 찾으러 올라간다. 만약 자기 자신이 부모노드라면 해당 부모노드의 값을 반환한다. 이후 다시 Union함수에 돌아오면 i와 j의 부모노드를 알 수 있다. 만약 i가 j보다 작다면 j의 부모노드를 a로 설정한다. 반대로 i가 j보다 크거나 같다면 i의 부모노드를 j로 설정한다. 출력은 현재 경로의 첫번째 위치의 부모 노드의값과 .. 백준/그래프 2022. 3. 29.

• 

  [백준 1963번 / C++] 소수 경로 dfs를 활용해서 푼 완전탐색 문제이다 #접근방법 먼저 소수인지 아닌지 판별하기 위해서 에네토스테라스의 체 방식으로 체크를 해줬다. (소수가 아닌 것들은 모두 true로 설정하였다. ) 먼저 queue에다가 시작 숫자 4자리와 count 값을 넣어준다. 그리고 숫자 4자리 수에 각 자릿수 마다 0부터 9까지 넣어서 소수이면서 범위 내에 있고 방문하지 않았다면 dfs를 호출한다. 만약 세가지 조건에 하나라도 포함되어있다면 continue 를 해준다. 이후 찾고자 하는 숫자와 같다면 count값을 출력해주고 만약 찾고자 하는 값이 없다면 "Impossible"을 출력해주자. #include #include #include #include #include #include #include using namesp.. 백준/완전 탐색 2022. 3. 25.

• 

  [백준 1991번 / C++] 트리 순회 dfs를 잘 활용해서 무엇을 언제 출력해야할지 풀면된다. #접근방법 이차원 배열을 생성해서 각 알파벳들의 왼쪽 자식과 오른쪽 자식의 아스키코드값을 저장한다. 1. preorder 먼저 'A' 값을 매개변수로 전달해서 해당 루트값이 '.' 라면 리턴하고 그렇지 않다면, 루트 노드를 먼저 출력하고 루트노드의 왼쪽 자식과 오른쪽 자식 순대로 dfs를 호출한다. 2. inorder 먼저 'A' 값을 매개변수로 전달해서 루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다. 그 후 루트노드값을 출력하고 오른쪽 자식을 계속 호출을 반복한다. 3. postorder 먼저 'A' 값을 매개변수로 전달해서 루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다. 오른쪽 자식을 계.. 백준/그래프 2022. 3. 24.

• 

  [백준 15649번 / C++] N과 M (1) DFS를 활용해서 완전탐색으로 풀어보자. #접근방법 1. 먼저 n과 m을 입력 받은 후에 level 값을 파라미터 값으로 전달하면서 바로 dfs를 호출한다. 2. level이 m 이 되었을 때는 지금까지 push_back 해서 모은 result값을 출력한다. 3. 그렇지 않다면 1~n 만큼 반복문을 돌리면서 방문 처리되지 않았을 경우, 방문 처리 및 result값 추가하고 dfs를 호출 4. 호출해서 돌아온 후에는 방문처리를 false 하고 result 배열에 넣었던 값을 다시 빼준다. #include #include using namespace std; int n, m; bool visited[10]; vector result; void dfs(int level) { if (level == m) { f.. 백준/완전 탐색 2022. 3. 24.

• 

  [백준 18870번 / C++] 좌표 압축 unordered_map 자료구조를 활용해서 풀었다. #접근방법 1. 처음 입력받은 v라는 벡터의 데이터값들을 re_v에 옮겨닮는다. 2. re_v를 오름차순으로 정렬한 후 첫 번째 원소부터 살펴본다. 3. 해당 원소를 key값으로 가지는 map의 값을 cnt로 저장한다. 4. cnt는 해당 원소의 시작번호다. 즉, 이전에 같은 key 값을 가지고 있다면 그 번호로 세팅해 주어야한다. 그래서 본인은 prev라는 변수를 사용하여 이전에 사용했던 값과 다른지 비교를 하고 다르다면 +1 을 한 번호로 세팅해준다. 5. 이후 v라는 벡터의 원소를 key로 가진 map 의 value값을 출력하면 된다. #include #include #include #include using namespace std; int m.. 백준/구현 2022. 3. 24.

• 

  [백준 7569번 / C++] 토마토 [백준 6593번 / C++ ] 상범 빌딩 BFS 문제이다 . 코드가 상당히 길다. #접근 방법 상범이가 빌딩에 갇히고 말았다. 왜 갇혔는지 모르겠다. 평범한 BFS 문제보다 조금 까다로운 문제이다. 왜냐하면 평소에 풀던 문제는 상하좌우만 baebalja.tistory.com 위의 문제와 상당히 비슷한 BFS문제이다. #접근방법 토마토 문제는 상하좌우만 고려할 것이 아니라 윗층과 아랫층을 검사해야한다. 즉, queue에다가 y와 x 그리고 layer까지 고려한 데이터 값을 함께 넣어준다. 그리고 map이 가로와 세로를 넘어갔을 때만 체크해주는 것이 아니라 layer의 높이까지 고려해야한다. 익지 않은 tomato 개수를 미리 저장을 해주고 bfs를 호출해서 현재 익은 토마토에서 주변에 안익은 토마토가 있.. 백준/DFS BFS 2022. 3. 22.

• 

  [백준 3079번 / C++] 입국심사 이분탐색 문제이다. 해당 문제는 프로그래머스 입국심사 문제와 거의 똑같다고 보면된다. (사실, 그때 너무 열 받았던적이..) #접근방법 이분탐색에 대한 알고리즘을 모른다면 이분탐색 개념을 익히고 오는 것을 추천한다. 먼저 양쪽 끝 값을 설정해야 하는데 low와 high라는 변수를 둔다. 해당 변수들은 각각 제일 적게 걸리는 시간과 제일 오래 걸리는 시간을 초기화한다. 즉, low에는 0을 두고 high 에는 max.time[i] * m 을 둔다. high 초기화 값이 왜 저렇게 되는지 모를 수도 있는데 이게 무슨 말이냐면, 심사대 중 제일 시간이 오래 걸리는 심사대에 m명의 사람이 다 줄을 설수 있다. 그래서 최악의 상황에서 나올 수 있는 값을 high 값에다가 세팅 해주는 것이다. 이후 절반을 쪼개가면.. 백준/이분탐색 2022. 3. 22.