🐳 문제 - [백준] 외판원 순회 (2098번) 이번 문제의 경우 비트마스크 알고리즘 개념에 대해 간단하게 살펴본 후 외판원 순회 문제 풀이에 대해 알아보도록 하자 🐳 알고리즘 - 비트마스크 ( Bitmask ) 🎯 Bitmask 란 ?정수를 컴퓨터처럼 이진수를 이용해 나타내는 것을 의미한다.예를 들어 10이라는 숫자를 2진수로는 1010 이라고 나타내는 것처럼 정수를 이진수를 통해 나타내는 것이다. 🎯 비트마스크의 장점 및 사용이유한 가지 예시를 살펴보자예를 들어 A,B,C,D 라는 네 개의 스위치가 있다고 해보자. 각각의 스위치의 상태는 On 또는 Off 이다.어떻게 하면 A,B,C,D의 상태를 저장할 수 있을까?Python의 경주 setOn = set()를 통해 setOn에 켜져 있는 ..
✅ 문제 - [백준] 문자열 폭발 (9935번) ✅ 처음 풀이 코드 - 시간초과import syssentence = sys.stdin.readline().rstrip()bomb = sys.stdin.readline().rstrip()while True: tmp = sentence.replace(bomb,"") if tmp == sentence: break sentence = tmpif len(sentence) == 0: print("FRULA")else: print(sentence)bomb이 있는 경우 replace 하고replace한 결과 tmp가 sentence랑 같은 경우 반복문을 멈춘다 ❌ 문제점 이런식으로 풀면 replace 메소드가 문자열의 처음부터 끝..
✅ 문제 - [백준] 별자리 만들기 (4386번) ✅ 필요 알고리즘 개념 - 프림 알고리즘 ( Prim's Alghrithm )🎯 프림 알고리즘 ( Prim's Alghrithm ) 이란?프림 알고리즘이란 MST ( Minimum Spanning Tree , 최소 신장 트리 )를 찾는 방법 중 시작 노드부터 시작하여 방문한 노드 중 cost가 가장 적은 경로를 선택해 가며 최소 신장 트리를 만드는 일종의 그리디 알고리즘이다.그리디 알고리즘의 경우 순간의 최선의 선택이 결과적으로 최선의 선택임을 증명해야 하는데 MST를 푸는 알고리즘 중 프림(Prim's) 알고리즘과 크루스칼(Kruskal) 알고리즘은 증명이 된 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다. 🎯 프림 알고리즘 ..
✅문제 - 내리막 길 (1520번) ✅필요 알고리즘 개념 - DP/DFS🔵 DFS 와 BFS 중 무엇을 쓸 것인가◼ 이 문제는 경로 찾기 문제와 유사하므로 DFS와 BFS 중 하나를 써야 하는데 왜 DFS를 사용할까?이 문제의 경우 경로가 겹칠 때 다른 경로에게 영향을 주기 때문에 먼저 DFS로 한 경로를 끝까지 탐색하는 것이 유리하다. 🔵 DP 사용 법 ◼ 2차원 리스트에 (x,y)에서 (row,col) 까지 가는 경우의 수를 저장한다. DFS를 진행하던 도중 이미 들렀던 지점인 경우에는 바로 dp 값을 사용한다. ✅코드 설명import sysrow,col = map(int,sys.stdin.readline().rstrip().split())board = [] delta = [(1,0),(-1,0)..
✅문제 - 파일 합치기 (11066번) ✅필요 알고리즘 개념 - DP🔵특정 경로를 지나는 DP◼ 예제 입력 40 30 30 50의 경우위의 경우에 3가지 케이스가 존재할 수 있다.1) (1) + (2 + 3 + 4)2) (1+2) + (3+4)3) (1+2+3) + (4) 즉 중간 경로로 k를 선택해 지나가는 것이다. 그러므로 dp를 1차원 배열이 아닌 2차원 배열로 만들어 준다.dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end]를 만족하는 dp를 만든다. ✅필요 알고리즘 개념 - Knuth optimizationdp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[st..
✅문제 - 문자열 집합(14425번)✅오늘 배운점문제에서 두 집합 간의 비교를 위해 in method를 사용하였다.하지만 처음에 list에서 in method를 사용한 경우에 시간이 3724ms나 소요 되어 문제가 있다고 판단했다.그래서 list를 set로 변경하였더니 시간이 116ms로 감소하였다.이유는 파이썬 홈페이지에서 확인할 수 있었다set 자료형에서 in method의 시간복잡도는 최선: O(1) 최악: O(N)이고list 자료형에서 in method의 시간복잡도는 O(N)인 것을 확인할 수 있었다. ❗❗❗ 앞으로 성분의 포함 여부를 사용할 때는 set를 사용하자!! ✅첫 코드 - (시간 3724ms)import sysindex = int(sys.stdin.readline().rstrip()..
