알고리즘 문제 풀이 (8) 썸네일형 리스트형 백준 1920 - 수 찾기 (c++ 풀이) 1. 문제 2. 유랑자의 풀이 전략 a배열 구현 후 for문 순회 찾기, bool check 배열 만들어 확인하는 방법 각각 시간초과, 메모리초과가 날 것이다. 따라서 map 자료구조를 활용하면 O(n*log(n))으로 찾을 수 있을 거라고 생각했다. 3. 풀이 비교 block님의 풀이와 비교한 후기입니다.(링크 : https://blockdmask.tistory.com/166) 근본적으로 사용한 알고리즘은 같지만, 표면 상 풀이방법은 약간 다른 것 같습니다. block님은 sort 정렬(O(n*log(n))) 이후 이진탐색(O(log(n)))을 통해 시간 초과를 해결했습니다. 반면 유랑자는 map 자료구조를 통해 문제를 해결합니다. 두 과정을 비교해보면, 첫째, block님의 sort 정렬 시의 시간복.. 백준 15686 - 치킨 배달 (c++ 풀이) 1. 문제 2. 유랑자의 풀이 전략 - BFS는 시간초과 -> 단순 최소합 구하기 / 조합 bfs로 풀었다가 시간초과가 났다. 간과한 점은, 경로 중에 다른 집이 있어도 상관없다는 것이다. 이 점 때문에 bfs로 구현할 필요가 없어졌다. 단순히 한 집에 대해 선택한 치킨집들에 대해 멘헤튼 거리의 최소값을 구해주면 되었다. 1) 최대 m개의 치킨 집을 선택하는 조합함수 comb를 활용해 치킨집을 선택한다. 2) 선택된 치킨집에 대해 최소 맨해튼 거리를 구하는 minValue 함수를 통해 결론을 도출한다. 3. 풀이 비교 다음은 얍문님의 풀이와 비교한 후기입니다.(링크 : https://yabmoons.tistory.com/50) 풀이 알고리즘은 같습니다. 이러한 문제는 거의 대부분 비슷한 풀이일 겁니다. .. 백준 14891 - 톱니바퀴 (c++ 풀이) 1. 문제 2. 유랑자의 풀이 전략 크게 어려움 없이 구현하면 되는 문제다. 허나 rotate 함수(파생되는 주변 톱니바퀴 변화)를 구현하는 좀 애먹었다. rotate 함수를 구현하는 과정에서, v배열에 인접한 톱니바퀴 구간 3개를 저장해놓고 각 원소쌍들(인접영역 1개)가 같은 값이면(같은 극이면) 움직이지 않고, 다르면 움직이는 것으로 생각하고 구현해나갔다. 하지만, 움직이는 톱니바퀴로부터 연결되지 않아 오류가 발생하는 case가 존재했다.(1, 2 / 4 -> 지정된 톱니바퀴 4에 대해 1, 2는 떨어져있다) 이 경우 톱니바퀴1, 2의 인접부위가 다른 값을 가져 움직일 수 있다고 생각했으나, 4와 연결된 3 톱니가 움직이 않게 되면 그 효과가 전파되지 않는다. 이 문제는 움직일 톱니에 연결된 톱니들 .. 백준 14503 - 로봇청소기 (c++ 풀이) 1. 문제 2. 풀이 전략 - DFS 딱 봤을 때 DFS라고 생각했지만 조금은 다른 방식으로 구현해야 했다. 문제에서의 '후진'이라는 기능 떄문이다. DFS가 도는 방식을 생각해보자. DFS는 실행되는 좌표(X, Y)가 존재한다. 현재 돌고 있는 DFS함수를 DFS1이라고 하고, DFS1을 호출했던 이전 DFS함수를 DFS0라고 하자. 보통의 DFS 방식은 DFS1이 끝나면 DFS0로 돌아가게 된다. 하지만 이 문제에서는 그렇게 하면 안된다. DFS1에서 후진할 시점에서 후진한 뒤의 좌표가 DFS0가 실행된 좌표와 다를 수 있기 때문이다. 이를 해결하기 위해 유랑자는 DFS가 반환되면 이전 DFS로 돌아가지 않고, 새로운 DFS(후진하는 좌표로 이동하는)를 리턴하게 해주었다. 3. 풀이 비교 lee33님.. 백준 14502 - 연구소 (c++ 풀이) 1. 문제 2. 풀이 전략 - combination, bfs 빈 공간 중 3개의 벽을 결정하고(comb), 기존 바이러스부터 bfs를 통해 퍼진 바이러스 개수를 센다.(countRoom) 3. 풀이 비교 개발자교닝님 풀이방법과 비교한 리뷰입니다. (링크 : https://code-kh-studio.tistory.com/78_) 3개의 벽을 세운 후 바이러스를 퍼트리고 그 개수를 센다는 큰 그림은 같습니다. 교닝님 풀이는, 벽을 세우는 각 case에 대해 새로운 배열을 선언해서 개수를 세줍니다. 이 경우 각 case들 간의 로직이 서로 간섭되지 않기 때문에 이전 case에서 세준 개수가 다음 case에 영향을 주지 않습니다. 반면 유랑자의 풀이는, visit이라는 바이러스가 퍼졌거나 벽이 있을 때 해당 칸.. 백준 14500 - 테트로미노 (c++ 풀이) 1) 문제 2) 풀이 전략 - dfs 채울 수 있는 도형은 어떤 형식으로든 변끼리 이어진 4의 넓이를 가진 형태이면 된다. 따라서 깊이가 4인 dfs를 구현하면 된다. 하나 주의할 점이 있다. dfs로 만들어지지 않는 위 문제에서 분홍색 형태이다. 이 경우를 따로 따져주는 exception 함수를 구현했다. 틀렸던 코드 if(flag 백준 15486 - 퇴사 2 (c++ 풀이) 1) 문제 2) 풀이 전략 - DP DP류 문제를 풀 때 첫 index에 담기는 값부터 마지막까지 그 값들이 어떤 방식으로 담기는지 시뮬레이션을 해보면 대충 짐작이 간다. 두 가지 해야할 작업이 있다. 1) 배열의 첫번째 값부터 순차적으로 d 배열을 채워나갈 때, 만약 해당 index의 값이 직전 index 값보다 작다면 일단 그 값으로 갱신해준다. 2) 해당 index 날에 작업하는 연산을 수행한다. if(i+t n; for(int i=1; i> arr[0][i] >> arr[1][i]; d[0]=0; for(int i=1; i 백준 1932 - 정수 삼각형 (c++ 풀이) 1) 문제 2. 문제 풀이 전략 - DP 삼각형 최상단에서 내려오면서 모든 경로에 대해 그때그때 합을 최신화 해준다. 이때 기존 배열이 아닌 새로운 배열 d[][]에 넣어주면서 최신화 해준다. -> 특정 노드까지의 합을 구할 때 2가지(왼쪽 위, 오른쪽 위) 경우가 있어 기존 배열에 최신화하면 두번째 경로 합을 구하지 못하기 때문이다. 첫 지점에 대한 초기화 작업을 수행하지 않도록 배열의 index를 1부터 설정해준다. 첫 지점부터 왼쪽 위, 오른쪽 위에 대한 연산 작업이 이후 과정과 똑같이 이뤄질 수 있도록 하여 코드를 단순화한다. 3) 풀이 비교 하루 한 문제님의 풀이와 비교한 후기입니다. (링크 : https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1932.. 이전 1 다음
