11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 비트마스크를 이용한 문제라고 하는데 어디에 어떻게 적용해야할지 감이 안잡혀서 생각나는대로 풀어봤다. 비트마스크 문제들도 여러개 접해보자. 풀이1 - 시간초과 이렇게 푸니까 시간초과가 나왔다 m = int(input()) S=set() #집합자료형 for _ in range(m): tmp = input().split() if len(tmp)==1: if tmp[0]=='all': s=set([i for i in range(1,21)]) else: s=set() continue a,b=tmp..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나는 코딩테스트 이론 공부를 '이것이 취업을 위한 코딩테스트다' 라는 책으로 하고 있다. 이 2667번 문제는 DFS/BFS 챕터에 있던 음료수 얼려먹기문제(DFS)와 유사했다. (검색하면 나옴) (음료수얼려먹기 문제 답) n=int(input()) graph=[] for i in range(n): graph.append(list(map(int,input()))) def dfs(x,y): #주어진 범위를 벗어나는 경우에 즉시 종료 if x = n or y = n:..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 대표적인 BFS 문제이다. 앞서 푼 1260번에서 사용한 BFS함수를 응용해서 풀었더니 쉽게 풀렸다! n = int(input()) m = int(input()) matrix=[[0]*(n+1) for i in range(n+1)] for i in range(m): a,b = map(int,input().split()) matrix[a][b]=matrix[b][a]=1 visit_list=[1]*(n+1) def bfs(v): count=0 queue=[v..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이문제는 DFS와 BFS를 이용해서 탐색하는 문제이다. DFS는 깊이탐색, 이어달리기, 한 정점에서 다른 정점 그리고 그 정점에 이어진 정점에 연결하는 느낌 BFS는 너비탐색, 한정점과 이어진 모든 정점을 들른 후에 다음 연결된 정점도 마찬가지로 한다. DFS에서는 재귀를 사용한다. 코드는 다음과 같다 n,m,v=map(int,input().split()) matrix=[[0]*(n+1) for i in range(n+1)]..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 BFS로 풀어야하는 문제이다. 설명은 코드와 함께 하겠다! from collections import deque n,m=map(int,input().split()) graph=[] for i in range(n): graph.append(list(map(int,input()))) dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(x,y): #큐 구현위해 deque라이브러리 사용 queue = deque() queue.append((x,y)) #queue가 빌때까지 반복..

2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이 문제는 투포인터 개념과 관련된 문제이다. 투포인터의 개념을 알고 적용하는것이 중요하다! n,m = map(int, input().split()) A=list(map(int, input().split())) start=0 answer=0 end=0 while start