전체 글
백준 2667: 단지번호붙이기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ✏️ 풀이 BFS가 편해서 BFS를 이용해서 풀이하였다. 백준 2178: 미로찾기와 백준 11724: 연결요소의 개수 가 혼재된 느낌의 문제였다. 두개 문제의 아이디어를 섞으면 풀린다. 그래프 탐색 시작점을 모르니까 그래프 전체를 반복문으로 돌면서 bfs를 시작한다. 이때 bfs를 하면서 탐색이 된 위치는 0으로 바꾸어 다시 탐색하는 일이 없도록 해주면 된다. 이렇게해서 bfs()를 몇번..
백준 11724: 연결요소의 개수 해설- python
✏️ 문제 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 ✏️ 풀이 visited 리스트를 순차적으로 확인하면서 요소값이 0일때 bfs를 실행할거다. 그러면 만약 1,2,4 연결되어 있으면 bfs 한번실행에 다 1이될거다.. 그러면 다음 반복땐 3에서 bfs를 다시 돌릴거고 이런식으로하면 연결된 부분이 끝날때마다 bfs를 돌릴 수 있게 된다. 이때 bfs돌릴때마다 answer+=1..
백준 2606: 바이러스 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ✏️ 풀이 아이디어는 간단하다. BFS를 이용해 1부터 아래로 쭉 탐색해 리스트에 저장하고 리스트의 길이를 출력했다. 입력데이터의 표현방식은 인접행렬을 이용했다. from collections import deque n=int(input()) m=int(input()) # 인접영행렬 matrix = [[0]*(n+1) for i in range(n+1)] # 입력받는 값에 대해 영형렬에 1삽..
백준 2178: 미로탐색 해설- python
✏️ 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 풀이 미로에서 최단거리를 구하는 문제다. 최단거리를 구하는 탐색문제의 경우 BFS가 적합하다. from collections import deque n,m=map(int,input().split()) matrix=[] for _ in range(n): matrix.append(list(map(int,input()))) dx=[-1,1,0,0] dy=[0,0,1,-1] def bfs(a,b): queue=deque([[a,b]]) while(queue): x,y=queue.pop..
DFS와 BFS 각각 사용하는 경우
✏️ DFS와 BFS의 구현방법과 차이 설명 아래글에 설명해두었으니 이 내용은 여기서 확인바란다. 백준 1260: DFS와 BFS 해설- python ✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에.. duckracoon.tistory.com ✏️ DFS와 BFS 각각 어떤 상황에서 사용할까? 어떤 문제를 풀때 DFS를 써야할지, 어떤 문제를 풀때 BFS를 쓸지 난감한 경험때문에 정리한다. When is it practical to use Depth-First Search (DFS) vs..
백준 10866: 덱 해설- python
✏️ 문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ✏️ 풀이 파이썬의 collections.deque를 이용하였다. 사용법에 대한 내용은 여기에서 from collections import deque import sys n=int(sys.stdin.readline()) dq=deque() for _ in range(n): order=list(sys.stdin.readline().split()) if order[0]=='..
파이썬 collections deque 사용법과 응용
✏️ deque Stack이나 queue처럼 한 방향에서 삽입과 삭제가 일어나는게 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다. 파이썬에서 list를 사용하는 것과 유사하지만 deque를 사용하는 이유는 시간복잡도 때문이다. 리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 끝이 아니라 뒤에있는 원소들을 앞으로 하나씩 당겨주는 연산을 더 수행하게된다. 따라서 list의 삭제연산은 O(n)이 걸리는데 반면 deque의 삭제연산은 O(1)이다. 따라서 push, pop이 빈번한 알고리즘의 경우 list보다 deque를 사용하는 것이 효율적이다. ✏️ collections.deque 1. collections.deque.append(x) : deque의 맨..
백준 1260: DFS와 BFS 해설 (파이썬, node.js)
✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ✏️ DFS와 BFS 개념 DFS와 BFS 개념부터가 가물가물해서 처음부터 정리하려고한다. DFS(Depth-First-Search, 깊이우선탐색) 그림이 좋길래 가져와봤다. 탐색순서: 1->2->4->8->5->3->6->7 (1) 탐색시작노드를 스택에 삽입하고 방문처리를 한다. (2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있..
백준 11286: 절댓값 힙 해설- python
✏️ 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✏️ 풀이 파이썬의 heapq 모듈을 이용했다. 모듈 사용에 대한 내용은 여기에서 파이썬 heapq 모듈 사용법과 응용 ✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으 duckracoon.t..
파이썬 heapq 모듈 사용법과 응용
✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으로써 일반 리스트를 마치 최소 힙처럼 다룰수 있게 된다. 그냥 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘겨서 사용하면된다. 즉 heapq모듈을 통해서 원소를 추가하고 삭제하면 그 리스트는 최소힙이 된다. heap=[] ✏️ 최소힙 원소추가 heappush(), 첫번째 인자는 원소를 추가할 대상 리스트, 두번째 인자는 추가할 원소 시간복잡도: O(logN) heapq.heappush(heap, 4) heapq.heappush(heap, 1) heap..
백준 11000: 강의실 배정 해설 - python
✏️ 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ✏️ 풀이 그리디 알고리즘 공부하겠다고 푼거긴한데 우선순위큐가 핵심인 문제인 것 같다. 회의의 [시작, 끝]을 리스트에 입력받는다. 회의시작시간을 기준으로 정렬시킨다. 첫 회의의 종료시간을 새로운 큐를 만들어 저장시킨다. 그 다음 반복문으로 두번째 회의의 시작시간부터 비교하면서 회의가 가능하면 회의가 진행되었다고 생각하고 새로운 큐를 업데이트해주고 회의가 불가능한 시간이면(회의겹치면) 새로운 큐에 push를 해주어 강의실이 하나 더 ..
그리디 알고리즘 개념정리와 문제
✏️ 그리디 알고리즘 간단하게 이야기하면 뒷 일은 생각안하고 당장에 눈 앞에 있는 것중에 가장 좋은 것만을 택하는 알고리즘이라고 볼 수 있다. 시작점부터 시작해서 가장 큰수를 얻어야하는 문제가 있다. 여기서 노란색 화살표로 표현된 것이 그리디 알고리즘, 주황색 화살표로 표현한 것이 최적해이다. 처음에 10을 거쳐야 가장 큰 수인 500을 얻을 수 있지만 그리디 알고리즘은 당장에 가장 큰 수인 15를 먼저 선택했기떄문에 20을 출력하게 된다. 그리디(Greedy)알고리즘은 이처럼 최적해를 보장해주지 않는다. ✏️ 그리디 알고리즘의 사용조건 첫째. 그리디 알고리즘은 최적해를 보장해주지 않는다고 했다. 즉, 그리디 알고리즘을 이용했을때 최적해가 나오는 문제에 그리디알고리즘을 이용할 수 있다. 이를 만족시킬 조..