본문 바로가기

백준4

[Week04] 알고리즘 - 비트 마스킹 백준 외판원 순회 문제(TSP)를 풀려면 비트 마스킹에 관한 개념이 필요하여 공부하게되었다. 해당 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net keywords 비트마스킹 dp, 비트마스킹 bfs, 비트마스크 순열, 비트마스크 조합 비트 마스킹 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이다. check = [False] * .. 2022. 4. 26.

[Week03] 알고리즘 - DFS / BFS 백준 문제 두 문제를 구분하는 기준이 약간 모호하지만.. 문제를 풀면서 만났던 몇몇 유형들을 까먹지않기 위해 정리해둔다. DFS / 백트래킹 nums = [1,2,3] result = [] permute = [] def dfs(): if len(permute) == len(nums) : result.append(permute[:]) return for i in range(len(nums)) : if nums[i] not in permute : permute.append(nums[i]) dfs() permute.pop() dfs() print(result) DFS 25731번 : 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를.. 2022. 4. 21.

[Week03] 알고리즘 - 유니온 파인드 트리 탐색 알고리즘 - 유니온 파인드 Union Find ✅ 개념 / 원리 : 대표적인 트리 알고리즘 : 합집합 찾기, 서로소 집합 알고리즘 이라고도 부른다. 유니온 파인드는 집합(set)을 합하기위한 연산이다. 양뱡향 연결 리스트를 사용해 합집합 연산 구현이 가능하지만 시작 복잡도가 안좋아 트리 형태를 활용한다. 부모를 가르키는 트리처럼 링크를 만들어 집합을 표현한다. 하나의 트리가 하나의 set이며 트리의 parents를 찾아 올라가 루트를 만나면 루트값이 집합의 대표값이다. 두개의 집합에 루트값을 찾아서(find) 루트값이 다르면 하나의 트리로 만든다.(union) > 트리 높이 h만큼의 시간 복잡도를 갖는다. 집합의 합집합 시킨다는 개념을 생각하면 문제 풀때 헷갈려서 주어진 그래프의 루트를 찾는 .. 2022. 4. 20.

[Week02] 알고리즘 - 이분탐색 [Week02] 알고리즘 키워드 - 이분탐색, 분할정복, 스택, 큐, 우선순위 큐 검색 알고리즘 - 선형탐색 / 이분 탐색 이분탐색 정렬이 되어있는 배열에서 특정 데이터를 찾기 위해서 모든 데이터를 순차적으로 확인하는 대신 탐색의 범위를 절반으로 줄여나가는 탐색 방법 이분탐색 사용시 주의사항 주어진 배열은 정렬되어있어야한다. 무한 루프에 빠지지않게 mid값을 잘 지정해준다 차례로 증가(혹은 감소)시키면서 풀어야하는 탐색문제에 큰 수의 범위가 주어진다면 이분탐색을 떠올려보자. 시간복잡도 O(logN) ✅ 이분탐색 구현하기 while문을 이용하여 구현 def binary_serch(a,n_list) : st = 0 en = n-1 while st a : en = mid -1 else : st = mid + .. 2022. 4. 9.

이전 1 다음

티스토리툴바