본문 바로가기

Problem Solving/백준

 (80)
[백준 / Python] 체스판 다시 칠하기 문제 설명 문제 풀이 우선 다른 알고리즘이 떠오르지 않아 무식하게 모든 경우의 수를 풀어내고자 했다. 체스판 사이즈만큼 모든 보드를 돌아보며 실행하면 (8 * 8) * (50 - 8 + 1) * (50 - 8 + 1)번이며 이는 1억번보다 작아 풀어낼 수 있겠다고 생각했다. 검은색으로 시작하는 경우와 흰색으로 시작하는 경우를 한 번에 확인하기 위해 black, white를 선언했고 row가 바뀔 때마다 색이 바뀌는 것을 보고 따로 코드로 작성해주었다. 이후 각 경우에서 색칠해야하는 횟수가 가장 적은 것을 최솟값으로 저장한 후 제출하였다. 코 드 import sys N, M = map(int,sys.stdin.readline().split()) board = [] for i in range(N): list..
[백준/C++] 9935번 문자열 폭발 풀이 문제 해석 문제 풀이 우선 문자열은 100만 개라 O(N2)으로는 풀 수 없을 것 같았다. 문제에서 문자열을 찾아서 지워내면 되는 것이니 스택이나 정규식 풀이 방법이 먼저 떠올랐다. mirkovC4nizCC44 에서 C4를 추려내는 등의 과정을 고려했더니 문자열을 비교할 때 어디까지 겹치는 문자열을 보유했었는지 저장하도록 하였다. (전에 문자열 알고리즘 중에 이런 게 있었는데 까먹었다.ㅎㅎ) [로직] 문자열과 폭발 문자열을 한 문자씩 비교하며 정답 문자열에 추가한다. 문자가 같다면 폭발 문자열의 인덱스를 하나 증가시킨다. 다르다면 지금 인덱스를 스택에 넣어 저장하고 현재 문자열부터 다시 비교한다. 만약 인덱스가 폭발 문자열의 길이와 같다면 길이만큼 정답 문자열에서 제거한다. 만약 이전 인덱스 스택이 비었..
[백준/C++] 14003번 가장 긴 증가하는 부분 수열 5 풀이 문제 해석 문제 풀이 우선 수열의 크기가 100만이라서 O(N2) 풀이로는 해결할 수 없다. dp +이분탐색을 이용한 O(NlogN) 풀이 방법이 필요하다. 풀이 방법은 14002번을 풀어보면 알 수 있는데 DP 배열을 1차원으로 사용한다고 생각해보면 될 것 같다. 지금 숫자가 내가 가진 숫자 최대값보다 크다면 배열의 마지막 값으로 추가한다. (코드상 order 배열) 지금 숫자가 최대값보다 작다면 이분탐색을 통해 지금 숫자보다 큰 최소값과 교환해준다. 이 때 1차원 DP의 경우 값을 덮어 씌워가며 계산을 진행하는게 정석인데, 가장 긴 증가하는 부분 수열의 길이를 찾을 때 바뀌어나간 값들의 길이가 최대가 되지 않는 이상 길이 자체에는 영향을 미치지 않는다. 여기까지가 14002번의 문제 풀이다. 그러나 ..
[백준/C++] 1181번 풀이 문제 설명 문제 풀이 2만개의 단어면 정렬 후 출력을 해도 문제가 없을 것이라고 생각했다 (NlogN가 2억 미만이므로) 중복을 따로 제거하기 귀찮아서 set을 이용하였고 set의 정렬방법을 따로 정의해주었다. 이 때 set은 operator를 overloading할 때 const를 쓰지 않으면 컴파일 오류가 나는데 원인은 아래 링크에서 설명하겠다. https://readble-ko.tistory.com/185 [C++] set operator 사용 시 const가 필요한 이유 백준 문제를 풀다가 신기한 것을 발견했다. vector나 배열의 비교 연산자를 오버로딩할 때는 const가 없어도 컴파일 오류가 없었는데, set의 비교 연산자를 오버로딩하려고 하니 const가 없을 때만 컴 readable-ko..
[백준/C++] 11140번 LOL 해설 문제 해석 문제 풀이 문제를 조금만 살펴보면 삭제하는 경우는 고려할 필요가 없으며 추가하거나 수정하는 경우만 생각하면 된다는 것을 알 수 있다. 삭제하는 경우는 l과 l사이에 문자열이 있는 경우인데 문자열이 1개보다 많은 경우면 결국 2개를 삭제해주는 것보다 l 앞이나 뒤에 2개의 문자를 추가하는 경우가 더 이득임을 알 수 있다. 고려사항 결국 아래에 산정된 경우만 고려하면 통과할 수 있는 문제가 된다. L과 L 사이에 문자가 1개 경우 - 문자 1개 추가 lo, ol, ll인 경우 - 문자 1개 추가 o, l - 문자 2개 추가 lol - 문자 추가 x 코 드 #include using namespace std ; int N ; int main() { cin >> N ; while(N--) { stri..
[백준/C++] 2252번 줄 세우기 (Topology sort) 문제 해석 문제 풀이 코딩테스트 준비하면서 위상 정렬은 알고 있어야지~ 싶어서 한 문제 풀려고 찾아본 문제이다. 위상 정렬이 기억나지 않아 푸는데 좀 헤맸다. 문제 풀이에 들어간 내 의식의 흐름은 아래와 같다. 우선 배열(인접행렬)로 생성하면 3만 x 3만으로 128MB는 훌쩍 넘어 터질 것 같아 인접리스트(adjacency list) 형태로 구현하였다. 만약 한 번도 누군가의 뒤에 선다는 정보가 없었던 사람이 있다면 모두 큐에 넣어주고 순서대로 출력하면 되겠다 싶었으나 (반례: 4,4 1->2 2->3 4->3 4->1 형태로 준다면 단순 bfs로는 해결할 수 없고 응용해야한다는 것을 알게 되었다. bfs에서 생기는 반례는 결국 내 이전 작업이 끝나지 않았는데 내가 먼저 queue에 들어가서 생기는 문..
[백준/C++] 1525번 퍼즐 풀이 문제 해석 문제 풀이 종이에 끄적여보니 0을 바꾸는 순서와 숫자의 위치에 관계를 찾기에는 어려움이 있었고 BFS로 브루트포스처럼 모든 나갈 수 있는 경우의 수를 보기에는 체크해야하는 배열이 99개라서 10억에 가까운 배열을 생성하기엔 어려움이 있어 보였다. 그렇다면 map에 필요한만큼 넣고 순서를 잘 백트래킹형식으로 작성해주면 되겠다고 생각했는데 그냥 int를 넣기에는 어려움이 있어서 1차원으로 flatten한 이후 string으로 변환시켜주었다. 그리고 문제에는 함정이 존재하는데 flatten해서 1차원 배열로 계산하는 경우 4번째칸에서 3번째칸으로 7번째칸에서 6번째칸으로 이동이 불가능하다 코 드 #include using namespace std ; const string want = "123456..
[백준/C++/USACO] 23879번 Air Cownditioning 풀이 문제 이해 문제 풀이 이 문제에서 주어지는 배열 2개의 차이를 가지고 이리저리 그리디하게 생각해보았지만 도저히 패턴을 찾을 수 없었고 조금 신박한 방법으로 풀어야하는 문제였다. 문제에서 주어준 배열의 차이는 아래와 같은데 이 이후로가 생각하지 못했던 신박한 부분이었다. 여기에 앞뒤로 0을 붙여주고 인접한 두 수 사이의 차를 구하면 이렇게 되는데 [증명] basis: 어떤 값이 0에서 시작해서 0이 되려면 더하고 뺀 값이 같아야하는 것은 자명하다. 우리가 원하는 것은 결국 희망 온도의 차이가 0이 되는 것이고 희망 온도의 차이가 0이 되면 인접한 차이 값 역시 0이 되어야 한다. 특정 구간의 배열에 1도를 높이거나 1도를 낮추면 위 그림처럼 선택한 배열 앞 뒤로 +1과 -1 혹은 -1 +1 되는 것을 확인..

티스토리툴바