https://www.acmicpc.net/problem/1707 1707번: 이분 그래프입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에www.acmicpc.net   1. Preview시간 복잡도: O(V+E) 공간 복잡도: O(V or E) 참고 : https://ji-gwang.tistory.com/293 유형: dfs, bfs   2. 초기 접근 방법이분 그래프: 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프   2개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Preview 시간 복잡도: O(2N^2) 공간 복잡도: O(2N^2) 참고 : https://hongcoding.tistory.com/18 (최적화) 유형: bfs 2. 초기 접근 방법 1개의 벽을 부술 수 있는 "item"이 있다고 생각하자. 기존의 visited 배열에서는 item 사용 유무를 판단할 수 없으므로 visited[i][j] → visited[i][..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(N) 유형: 그래프 탐색, dfs 2. 초기 접근 방법 그래프 탐색을 하면서 자기자신을 만날 때, 즉 사이클이 형성이 되어야 한 팀이다. def dfs(start, x): for k in graph[x]: if not visited[k]: visited[k] = True judge.append(k) dfs(start, k) if visited..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 1. Preview 시간 복잡도: O(6*NM), bfs 공간 복잡도: O(NM) 유형: 그래프 탐색, bfs 2. 초기 접근 방법 visited[e] : 사다리 visited[nx] : 일반 주사위 길 2가지 경우 모두 queue에 삽입하여, 해당 경우를 고려해 탐색하게 된다. for s, e in road: if s == nx and not vis..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주www.acmicpc.net 1. Preview풀이 시간: 35분 + 30분시간 복잡도: O(NM)공간 복잡도: O(NM) 2. 초기 접근 방법board[][] 에서 모두 방문하는데 "dfs 탐색를 진행한 횟수" 라고 생각해 풀었다. 3 4DLLLDDDURRRU 곰곰히 고민해보니, 위와 같은 case에서 dfs 탐색이 3번 일어나지만, 필요한 safezone은 1개이다. 3. 생각 ..

https://www.acmicpc.net/problem/9019 9019번: DSLR네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에www.acmicpc.net 1. Preview시간 복잡도: O(4*commands) 공간 복잡도: O(commands) 2. 초기 접근 방법현재 풀이와 똑같이,queue()를 사용해 수행한 연산을 순서에 맞게 처리하여, 최소 연산 커맨드를 찾으려고 했다. 하지만 2가지 간과한 점이 있어 '시간초과'와 '틀렸습니다'를 받았다. 1) visited[num] = T/F (시간초과)방문한 숫자에 대해서, 이전에 ..