백준4 [BOJ]2606번: 바이러스 문제 풀러가기 링크 2606번: 바이러스문제 분류가 플로이드 와샬 알고리즘으로 되어 있는데 나는 DFS로 풀었다. 플로이드 와샬을 짜본적이 아직 없고 사실 BFS 연습 문제 추천에서 나온 문제라 풀려고 한 건데 BFS보단 DFS가 더 쉬울 것 같았기 때문이다 ㅋㅋ 문제 자체는 간단한데 1번 컴퓨터에서 바이러스가 시작되서 연결이 되어 있는 모든 컴퓨터까지 감염이 되는데 그 감염되는 컴퓨터의 개수를 세라는 것이다. --> 탐색 DFS와 BFS라는 문제를 풀어 봤다면 엄청 쉽게 풀 수 있다. 사실 컨셉만 다른 거지 문제는 똑같다고 보면 된다. 코드 2018. 2. 5. [BOJ] 1932번: 숫자삼각형 1932번 문제 풀기! 1932번: 숫자삼각형정말 고민을 많이 했는데 생각보다 간단했었따... 이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다. 문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2) 개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다. [1] [2] [3] [4] [5] [1] 7 [2] 3 8 [3] 8 1 0 [4] 2 7 4 4 [5] .. 2018. 2. 3. [BOJ]2605번: 줄 세우기 2605: 줄 세우기 풀이이 문제는 여러가지 방법으로 풀 수 있다는 생각을 했다.스택으로도 풀 수 있고, swap으로도 풀 수 있다는 생각을 했지만 나는 swap으로 했다. 별로 추천하고 싶은 방법은 아니지만 도저히 이 방법 밖에는 생각이 나지 않았기 때문에 이 방식으로 문제를 해결했다. 1) 우선 나는 1부터 n까지의 숫자를 배열에 다 채웠다.2) 반복문을 i = 0 ~ i < n 만큼 도는데, 변수 idx의 값은 i에 따라 바뀐다.(순서대로 돌기 때문에)3) 뽑은 번호를 x라고 할 때 x == 0이면 아무런 행동도 취하지 않으므로 continue를 해주고 나머지 경우에는 x번 만큼 반복문을 돌면서 swap을 해주면 된다. 4) 마지막 출력!!! 아직도 잘 모르겠다고요? 네 충분히 이해합니다. 저도 다.. 2017. 9. 3. [BOJ] 2477번: 참외밭 링크 : https://www.acmicpc.net/problem/2477 2010년 초등부 3번 문제다. (4,5번은 나중에 풀어봐야겠다) 이 문제는 입력 값이 어떻게 주어지든 간에 이.어.져.서 주어진다는 것을 이용하면 된다.직사각형 넓이 최대값 구하는 것은 쉽고 (가로, 세로 MAX 값 구해서 곱해주면 된다. 이것 또한 가로, 세로는 연결되어 있으니깐 잘 이용하면 된다!),작은 직사각형을 구해서 빼줘야 한다. 근데 여기서 알아야 할 것이 참외밭은 무조건 육각형이라는 것이다.그렇기 때문에 가로, 세로의 최대값이 나온 지점에서 가로의 index를 i라고 하면 i를 +3, +4 해준 값을 곱하면 작은 직사각형이라는 것이다!"잘 모르겠으면 그림을 보면서 비교를 해보자."그렇게 해서 최대 직사각형 넓이를 구.. 2017. 8. 26. 이전 1 다음
