🐳 문제 - [백준] 외판원 순회 (2098번) 이번 문제의 경우 비트마스크 알고리즘 개념에 대해 간단하게 살펴본 후 외판원 순회 문제 풀이에 대해 알아보도록 하자 🐳 알고리즘 - 비트마스크 ( Bitmask ) 🎯 Bitmask 란 ?정수를 컴퓨터처럼 이진수를 이용해 나타내는 것을 의미한다.예를 들어 10이라는 숫자를 2진수로는 1010 이라고 나타내는 것처럼 정수를 이진수를 통해 나타내는 것이다. 🎯 비트마스크의 장점 및 사용이유한 가지 예시를 살펴보자예를 들어 A,B,C,D 라는 네 개의 스위치가 있다고 해보자. 각각의 스위치의 상태는 On 또는 Off 이다.어떻게 하면 A,B,C,D의 상태를 저장할 수 있을까?Python의 경주 setOn = set()를 통해 setOn에 켜져 있는 ..
🐳 문제 - [백준] CCW (11758번) 🐳 알고리즘 - CCW ( Counter Clock Wise ) 🎯 CCW 란 ?CCW 알고리즘은 좌표평면 위의 세 점이 이루는 관계를 알기 위한 알고리즘이다. 먼저 식부터 살펴보면 아래의 식과 같습니다.우선 위의 식이 어디서 나왔는지 알아야합니다. 위의 식은 좌표 평면 위의 세 점이 만드는 삼각형의 넓이를 벡터의 외적을 이용해 구하는 식입니다.먼저 세 점을 이용해 두 벡터를 만듭니다. 저는 (x1,y1) 을 기준으로 두 벡터를 만들어 주겠습니다.그 럼 두 벡터를 v1, v2 라고 합시다. v1 = (x2-x1, y2-y1), v2 = (x3-x1,y3-y1) 이 됩니다.이 두 벡터를 외적해 줍니다. 외적한 결과는 크기와 방향을 가집니다. 외적한 값의..
✅ 문제 - [백준] 다리 만들기 2 (17472번) ✅ 필요 알고리즘 개념 - BFS / MST ( Kruskal Alogorithm )🎯 크루스칼 알고리즘( Kruskal Alghrithm ) 이란?크루스칼 알고리즘이란, 그래프 자료구조에서 그리디 알고리즘을 적용해 MST ( Minimum Spanning Tree , 최소 신장 트리 )를 찾는 방법이다. 그리디 알고리즘의 경우 순간의 최선의 선택이 결과적으로 최선의 선택임을 증명해야 하는데MST를 푸는 알고리즘 중 프림(Prim's) 알고리즘과 크루스칼(Kruskal) 알고리즘은 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다. 크루스칼 알고리즘을 적용하는 순서는 다음과 같다.간선을 리스트에 ( 길이, 노드1, 노드2 ) 형식으..
✅ 문제 - [백준] 문자열 폭발 (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) 알고리즘은 증명이 된 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다. 🎯 프림 알고리즘 ..
✅문제 - [백준] 타임머신 (11657번) ✅필요 알고리즘 개념 - Bellaman-Ford Algorithm🔵 Bellman-Ford AlgorithmBellman-Ford 알고리즘은 한 node 에서 다른 모든 node 들로 가는 최단 거리를 구하는 알고리즘이다. 🔵 Bellman-Ford Algorithm 와 Dijkstra Algorithm의 차이1. Dijkstra Algorithm는 음의 가중치를 갖지 않는 상황에서 사용한다.이때 순간순간 가중치가 가장 작은 간선을 선택하는 것이 최단거리를 보장하므로 Greedy와 Priority Que를 이용하여 구현할 수 있다. 2. Bellman Ford Algorithm은 음의 가중치를 갖는 상황에서 사용한다.이때는 가중치가 가장 작은 간선을 ..
