한걸음

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net BFS 기본 구조를 이해하고 있는지 물어보는 문제. 앞으로 역량 테스트 준비하면서 github도 사용해봐야겠다. 1. BFS 연결 요소들을 graph 에 담아서 너비 탐색을 시행한다. 연결 뭉치들이 여러개 있을 수 있으므로 각 노드를 전부 탐색하되, 방문 리스트를 활용해 이미 방문한 적이 있는 것은 같은 뭉치에 속해 있으므로 패스하는 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지 확산하는 것은 어렵지 않았으나, 공기청정기 작동방식 구현하는 것이 조금 까다로웠던 문제. 1. 미세먼지 확산 미세먼지 확산은 동시에 확산한다고 하나, 프로그래밍은 순차적으로 진행하기 때문에 Board를 그대로 이용하는 순간 난장판이 되어버린다. 참조되기전에 확산한 먼지가 참조될때 자리 잡고 있으면 같이 계산 때려버림. 그러므로 먼지의 정보를 따로 저장해두고 계산해야한다. 매 시간마다 먼..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 이해하는 것은 어렵지 않았지만, 구현이 상당히 까다로웠던 문제. 패키지들을 지양하고 문제를 풀려고 하니 더욱 맞추기 어려웠다. 결국 제한시간안에 문제를 풀지 못했다. 정답 처리 받는데 까지 걸린 시간... 6시간.. 그럼에도 잘한점을 찾자면, 어쨌든 해결했고 나름의 노하우(?) 하나 더 쌓았다는 것? 이번에 문제 풀면서 정말 많은 점을 알게 되었다. 1. 리스트 메모리 주소 할당 ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해당 문제의 핵심은 BFS 이다. 큐에 좌표 값을 넣고 해당 좌표값을 기준으로 근접한 셀과의 인구 차이가 L 과 R사이에 있다면, 방문 처리를 하고 인구이동할 연합의 영역을 결정해주고 이동시켜주면 된다. 문제를 계속해서 풀다보니 어느정도 접근법은 이해하기 시작했는데, 아직도 코딩이 익숙하지가 않다. 하다보면 나아지겠지 1. 전체 코드 메모리 : 131644 KB 시간 : 1240 m..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 문제자체는 간단하지만, 정말 구현하기가 힘든 문제. 대부분 많이 틀린 것 같은데, 이유는 정말 알기 힘든 것 같다. 나의 경우는 인덱싱 문제. 하드코딩을 하고 틀렸다는 결과를 보게 된다면, 인덱스 참조부터 잘 확인해야할 것 같다. 돌리고 돌리다보니 헷갈려서 인덱스 지정을 잘못주었다는 것을 뒤늦게 확인했다. 또한, 경우의 수가 너무 많아 반례를 찾기가 정말 어렵다. (웬만하면 대부분의 케이스에 대해서..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 오랜만에 가벼운 마음으로 풀 수 있는 문제를 만났다. 아직은 DFS 가 익숙하지 않아서.. 재귀함수로 접근하는 것이 어렵다. 그래서 치킨집의 개수 T와 폐업시키고 남길 치킨 집 수 M을 활용하여 조합 함수를 작성하였다. itertools를 이용하면 더욱 쉽게 접근이 가능한 문제이지만, itertools를 활용하지 않고 조합 함수를 만들어서 썼다. 1. 조합 함수 재귀함수 형태..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제는 위와 같다. 초기조건을 잘못주는 바람에 한참 해맸다... 앞으로 조심해야겠다. 드래곤 커브를 그릴때 보드판 크기는 0 보다 크거나 같고, 100보다 작거나 같다. 그러므로,, 보드판 지정할 때 [[False] * 101 for _ in range(101)] 이렇게 지정해줘야한다. 덕분에 스스로 설정해둔 제한 시간(180분) 안에 못풀었다.. 이런 실수는 없도록 하..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 백준 온라인 저지 사이트에는 다양한 문제집이 있다. 그 중에서도 삼성 SW 역량테스트에 대비하여 DFS, BFS 필수 문제들을 따로 정리해둔 문제가 있었다. 이번 문제는 DFS, BFS에 관해 기본적이지만 아주 핵심 내용을 담고 있는 문제를 간단하게 풀어보았다. 문제는 아주 간단하다. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하면 된다. 1...