문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 풀이 풀이 - BFS와 DFS 이분 그래프는 쉽게 말하자면 그래프에서 연결되어 있는 노드끼리 같은 색깔을 칠했을 때 총 두가지 색깔이 나온다는 의미다. 모든 노드를 탐색하면서 색깔을 칠하는 방식으로 해결했고 이 때 DFS를 이용했다. (BFS로도 풀 수 있다고 한다.) 재귀로 풀면서 해결하는데 문제는 비연결 그래프인 걸 감안하고 풀어야 한다.(이거 때문에 계속 오류남..) 탐색을 하면서 인접한 노드에 dfs를 수행..

문제 링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 트럭 갯수 : n, 다리의 길이 : w, 다리의 최대 하중 : L - w대의 트럭만 동시에 올라갈 수 있다. - 단위 시간에 하나의 단위 길이만큼 이동한다고 가정 - 다리 위에 올라가있는 트럭의 무게 합 deque 사용- nList에서 트럭을 뺄 때와 빼지 않을 때를 고려한다. 반복문 사용 - 공통적으로 시간+1, bridge에서 하나..

시간 복잡도와 Big-O 표기법 정리와 더불어 코테 준비로 사용하는 python 언어에서 자료형별 시간복잡도를 정리하였다. 1. 점근 표기법(Asymptotic notation) 점근 표기법 : 알고리즘의 성능과 효율성을 표기해주는 표기법 여기서 말하는 효율성은 실행시간이 적으냐(=시간복잡도), 메모리를 덜 차지하는지(=공간복잡도)에 걸려있다. 결국 시간복잡도와 공간복잡도를 나타내는 표기법인 셈. 시간복잡도(Time Complexity) : 입력된 N의 크기에 따라 실행되는 조작의 수 공간복잡도(Space Complexity) : 알고리즘이 실행될 때 사용하는 메모리의 양 점근 표기법에는 대표적으로 대문자 O 표기법, 소문자 o 표기법, 대문자 오메가(Ω) 표기법, 소문제 오메가 표기법(ω), 대문자 세..