백준108

• 

  [백준 15903번 / C++ / 그리디] 카드 합체 놀이 우선순위 큐에 대한 자료구조를 알고 있으면 해당 문제는 상당히 쉽게 풀린다. #접근방법 먼저, 그리디하게 접근을 해야한다. 가장 작은수를 만들기 위해선 어떻게 해야할까? 직관적으로 생각해봤을 때도 바로 느낌이 올 것이다. 가장 작은 수부터 차례대로 더해야한다. 하지만 벡터나 배열로 생성하였을 경우 매번 오름차순으로 정렬하는 것은 번거롭다. 그렇기 때문에 우선순위 큐를 활용하자는 것이다. 즉, 카드의 개수만큼 입력받아서 최소힙으로 만들면 되는것이다. 4, 2 , 3 , 1 을 입력값으로 받았다면 1을 top 으로 가진 최소힙으로 구성되어지고 top 위치한 두개의 노드를 pop 해서 더한 결과를 두번 push 해주면 된다. 가장 작은 값이 항상 top 에 위치하는 최소힙 자료구조를 활용하면 이 문제는 쉽게 .. 백준/그리디 2022. 6. 28.

• 

  [백준 5014번 / C++ / BFS] 스타트 링크 BFS 를 활용한 문제가 은근 많다. 최근 코테에서도 BFS 를 활용해서 풀었던 기억이 난다. DFS/BFS 를 응용한 문제를 파악하고 바로 풀수 있게끔 충분히 연습하자. #접근방법 이 문제의 핵심은 서두에서 언급했듯이 BFS를 활용하는 것이다. 여기서 건물의 위아래로 왔다갔다하는 것이 조금 헷갈리면 건물을 오른쪽 방향으로 누웠다고 생각해보자. 그러면 크기가 f인 배열에 현재 위치 s 에서 오른쪽(up), 왼쪽(down) 으로만 갈 수 있는데 목적지 g 에 도착하면 끝난다. 바로 응용해보면 현재 위치를 담은 좌표를 queue에 담고 너비 우선탐색을 하는것이다. 즉, 왼쪽으로 갔을 때 좌표값과 오른쪽으로 갔을 때 좌표값을 queue담으면 된다. 그리고 방문처리를 해준다. 여기서 중요한 문제는 1. 왼쪽 좌.. 백준/DFS BFS 2022. 6. 28.

• 

  [백준 3020번 / C++ / 누적합] 개똥벌레 최근 프로젝트를 여러 진행하다보니 3개월 간 코테준비를 못하다가 이 문제를 시작으로 다시 준비하려고 한다. 처음 이 문제에 접근했을 때 이중 for 문을 사용했다. (오랜만이라 시간 복잡도 생각도 안하고 접근... ) 제한 시간은 1초인데, 시간 복잡도는 O(N*H) 이 걸린다. 1억번의 연산이 1초 정도니까 N ≤ 200,000, 2 ≤ H ≤ 500,000 200000*500000 = 1조? 이중 for문 돌리면 100퍼센트 시간 초과가 뜰거다. 그렇기 때문에 한번의 루프로 이 문제를 해결해야한다. 누적합을 사용해보자. #접근방법 석순이와 종유석은 bottom 과 top 에서부터 자란다. 먼저 번갈아가면서 길이가 입력한다고 하니 차례대로 bottom 벡터와 top 벡터에 입력받은 값을 인덱스로 보고 .. 백준/구현 2022. 6. 28.

• 

  [백준 1874번 / C++ / 스택] 스택 수열 #접근 방법 먼저, 임의의 수열을 만들기 위해 N을 입력받고 N만큼의 수를 입력받는다. 본인은 하나의 입력값을 입력할 때 바로 Stack을 활용했다. 1. 스택이 현재 비어있지 않고 top 이 입력받은 수라면 pop 하고 '-' 추가 2. number의 현재 값이 입력받은 값보다 작다면 같을때까지 스택에 (number++) push 와 '+" 추가 3. 스택이 현재 비어있지 않고 top이 입력받은 수보다 크다면 바로 "NO" 출력 후 종료 -> "반드시 오름차순을 지키도록 한다"조건때문에 top 이 입력받은 수보다 크다는 것은 해당수열을 만들수 없다는 것을 의미. 만들수 있었으면 조건 1에서 바로 pop 되어지기때문. #include #include #include #include using namesp.. 백준/구현 2022. 6. 28.

• 

  [백준 2688번 / C++] 줄어들지 않아 dp를 활용한 문제이다. #접근방법 제일 먼저 생각해야하는 것은 각 자릿수를 나타내는 dp배열을 생성해야한다. 예를 들어, dp[1][3] 은 첫번째 자릿수의 값이 3일 때! dp[2][1] 은 두번째 자릿수의 값이 1일 때! dp[4][0] 은 네번째 자릿수의 값이 0일 때! 그렇기 때문에, 먼저 dp[1][i] 를 1로 초기화 한다. 왜냐하면 첫 번째 자릿수의 각 숫자들은 오로지 하나만 존재할 수 있다. 그리고 dp[2][i] 를 갱신해나가야하는데, dp[2][0] 이라면 "00", "01", "02", "03" ..... "08", "09" 의 경우의 수가 있다 즉, dp[1][0]~ dp[1][9]의 합과 같다. dp[2][4] 라면 "44", "45", "46", "47", "48", "49" .. 백준/DP 2022. 4. 14.

• 

  [백준 1461번 / C++] 도서관 그리디 문제이다 #접근방법 본인은 우선순위 큐를 적절하게 사용을 해서 풀었다. 이것보다 더 나은 코드가 있다고 생각을 하지만 문제를 보자마자 직관적으로 떠올렸던 풀이방법이였기에 풀었던 방식을 설명하려고 한다. 이 문제에서 중요한 점은 마지막에 책을 갖다 놓고 나면 다시 돌아올 필요없다 라는 것이다. 그리디하게 해당 문제를 접근하기 위해서 위의 문장을 읽고 바로 떠올려야한다. " 음.. 그러면 가까이 있는 책들을 먼저 갖다놓고 제일 거리가 먼 책을 마지막에 갖다 놔야겠구나" 왜냐하면 가장 멀리 있는 놈을 마지막에 갖다 놔야 다시 돌아오는 비용이 추가로 들지 않기 때문이다. 먼저 문제에 접근할 때 우선순위 큐 두개를 생성하는데 하나는 음수, 하나는 양수값을 모아놓는다. 그리고 책의 좌표값을 입력할 때 가장 .. 백준/그리디 2022. 4. 6.

• 

  [백준 13904번 / C++] 과제 ​#접근방법 점수의 최댓값을 얻기 위해서는 당연히 과제 점수가 높은 것을 제일 먼저 할당 받아야한다. 그렇기 때문에 처음에 입력받을 때 마감일 d와 점수 w 를 정렬해줘야한다. 우선 제일 중요한 과제 점수가 높은 것부터 내림차순으로 정렬해주었다. 그리고 만약 과제 점수가 같을 경우네는 마감일이 짧은것부터 오름차순으로 정렬했다. (실행해본결과 상관없는 조건이다) 아무튼 과제 점수가 높은 것들부터 해서 cost라는 배열에 집어넣어준다. 예를 들어 , 마감일이 4이고 점수가 50이라면 인덱스 4를 가지고 있는 cost라는 배열에 50을 저장한다. 이후에 마감일 4이고 점수가 40이 들어왔을 경우 마감일 1~3 일을 차례대로 훑어보면서 빈자리에 넣어준다. 만약 빈자리가 없다면, 이전에 더 높은 점수를 가지는 과.. 백준/그리디 2022. 4. 5.

• 

  [백준 12904번 / C++] A와 B 그리디 문제이다. #접근 방법 처음에 문제를 읽어봤을 때 이걸 어떻게 해야하지..? 생각이 들수도 있다. 나도 그랬다. 문자열 S에 언제 A를 추가해야할지, 또는 언제 B를 추가하고 뒤집어야하는지.. 한 3분정도 생각하다가 답이 안나와서 만들어야 할 문자열에서 A와 B를 빼면 되지 않을까? 라는 생각이 들었다. 한번쯤은 직관적으로 문제에 접근해도 좋지만 만약 안풀린다면 추가하는 것이 아니라 반대로 생각해서 빼보는 방식도 고려해봐야할 것이다. 즉, 문자열 S1에서 만들어야 할 문자열이 S2 라면, S2에서 A를 빼주고, 또는 B를 빼주고 문자열을 뒤집는다. 언제동안? S1과 S2의 길이가 같을때까지! 문자열의 길이가 같아졌을 때 같은 문자열이 맞는지 비교해서 출력하면 끝이다. #include #includ.. 백준/그리디 2022. 4. 5.

• 

  [백준 1449번 / C++] 수리공 항승 백준의 그리디로 분류되어 있는 문제를 풀어보았다. #접근방법 해당 문제는 조금만 생각해도 쉽게 풀릴 수 있다고 생각한다. 로직은 다음과 같다. 해당 지점에서 좌우 0.5 간격을 줘야한다는 말이 거창하게 들릴 수 있지만 해석해보면 그냥 물이 새는 지점은 구멍이고 그 구멍을 막기 위해선 한 칸을 막아야한다는 뜻이다. 즉, 길이가 1인 테이프를 그냥 붙이라는 말인데 말을 저렇게 하는거다. 먼저 물이 새는 지점의 데이터를 받아서 오름차순으로 정렬을 한다. 그 후, 시작 지점에서 바로 소유하고 있는 테이프의 길이를 더하고 -1을 해준다면 그 값이 테이프의 마지막 위치다. 예를 들면, 만약 물이 새는 시작 지점이 3이고 소유하고 있는 테이프 길이가 5라면 3 4 5 6 7 이라는 장소를 다 막을 수 있는 것이다. .. 백준/그리디 2022. 4. 5.

• 

  [백준 4179번 / C++] 불! bfs 를 이용해서 풀면 되는 문제이다. #접근방법 이 문제는 생각보다 예외사항이 많았다. 이 점들을 고려하지 못한채로 접근해서 수정작업이 좀 필요했다. 그래서 문제를 풀기 전에 지문을 꼼꼼히 읽고 접근해야할 습관이 필요하다고 뼈저리 느꼈던 문제이다. 이 문제를 요약하자면 불이 상하좌우로 먼저 퍼지고 나서 지훈이가 불을 피해서 지도의 끝에 도착하면 빠져나갈 수 있다. 그냥 전형적인 BFS() 문제인데 예외사항이 무엇인지 한번 살펴보자. J는 입력에서 하나만 주어진다. 문제를 보면 위의 문장 한줄이 나와있다. 여기서 유추를 했어야만 했다. 즉, "J는 입력에서 하나만 주어질 수 있다" 라는 말은 F는 입력에서 하나일 수도 있고 없을 수도 있고 두개 이상일 수도 있다는 뜻이다. 나는 처음 접근할 때 아무생각.. 백준/DFS BFS 2022. 4. 2.