백준

1. 문제 풀이 이분 그래프인지 판별하는 문제였습니다. 그래프가 비연결 그래프일 때 처리하는 방법에서 애를 먹는 바람에 시간이 조금 걸렸습니다. 너무 안일하게 문제를 읽은 것 같습니다. 너비우선탐색을 사용해서 적대 관계와 우호 관계로 나눌 때, 인접한 두 정점이 같은 관계가 되는지 안되는지 판별해 문제를 풀이했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typed..

1. 문제 풀이 2차원 배열이 나오길래 DFS나 BFS일거라고 추측하였는데, 문제를 모두 읽어보고 핀이 최대 8개라는 조건을 확인하고 백트래킹을 사용할 수 있음을 파악했습니다. 배열의 크기가 안 주어져있길래 직접 예제 입력을 확인했습니다. base condtion을 지정하는 방법이 까다롭지만 flag 변수를 둬서 해결했습니다. 실행부는 좀 길긴 하지만 문제의 요구 사항을 직관적으로 구현했습니다. 문제를 풀이하고 질문게시판 구경을 좀 했는데, 남은 핀의 개수를 가지고 이동 횟수를 계산할 수 있다는 사실을 알았습니다. 그 이유는 이동 한 번에 핀 하나가 지워지므로 (남은 핀) = (원래 핀 개수) - (이동 횟수)가 된다고 합니다. 그래서 제 코드는 개선할 여지가 있어 보입니다만 할 일이 많아서 넘어가기로 ..

1. 문제 풀이숫자가 낮은 바이러스가 먼저 퍼진다는 조건을 만족하기 위해 우선순위 큐를 2개 선언해 번갈아 사용하면서 풀이하였습니다. 너비 우선 탐색에서 큐 대신 우선순위큐를 쓴 것 말고는 별다른 차이점은 없습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl;type..

1. 문제 풀이 flood fill 기법으로 각 섬의 번호를 할당했습니다. 루프를 돌면서 일자로 다리를 놓으면서 거리가 1이 아니고 다른 섬과 만나면 간선{ 거리, 현재 점, 다른 섬 }을 추가했습니다. 이를 바탕으로 max(섬 번호)가 정점의 개수가 되고 간선들로 크루스칼 알고리즘을 사용해 최소 신장 트리를 구했습니다. 모든 간선을 돌고 나서 최소 신장 트리를 이루는 간선이 max(섬번호) - 1개가 아니라면 -1을 출력했습니다. 2. 코드// Authored by : chjh2129#include using namespace std;using ti = tuple;using pi = pair;#define X first#define Y secondconst int dx[4] = { 1, 0, -1, 0..

1. 문제 풀이 단순 문자열 파싱 문제였습니다. 각 문자열에 매칭이 되는 숫자정보들을 해쉬에 저장, 문자열에서 숫자들과 연산자 정보를 컨버트 해서 뽑아내는데 뽑아낼 수 없는 상황에 처하면 false를 반환했습니다. true를 반환받았다면 숫자들과 연산자 정보를 가지고 순서대로 연산한 결과를 다시 문제에서 요구하는 형태로 바꾸어 출력했습니다. 여담이지만 원래 문제를 풀이할 때, 어느 정도 분석을 한 뒤 구현할 기능들을 나누어 풀이하였는데 이 문제를 풀던 날 너무 하기가 싫어서 생각을 안 하고 작성하면서 풀었습니다. 당연하게도 전 천재가 아니라서 WA를 무더기로 받았습니다. 지금은 AC를 받았지만 좀 하기가 싫었지만 지금은 생각이란 걸 조금 해서 풀이할 수 있었습니다. 확실한 건 어떤 문제를 마주치든 분석은..

1. 문제 풀이 투 포인터 알고리즘 문제입니다. 이진 트리나 해쉬를 사용해 시작위치(st)에서 끝 위치(en) 내에 사용 중인 서로 다른 문자의 개수를 세면서 조건을 확인했습니다. 저는 이진트리 map을 사용하였습니다. 이진트리에서 제거를 해줄 때, 해당 문자가 사용한 빈도가 0이 될 때에만 제거함으로써 같은 문자가 여러 번 사용되었을 때를 방지하였습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typ..

1. 문제 풀이 브루트포스 애드훅 문제였습니다. 저는 백트래킹을 사용했습니다. 입력받은 문자열의 각 알파벳 빈도수를 기록하였습니다. 그 후 각 숫자에 해당하는 단어들이 문자열 s에서 몇 개까지 뽑아낼 수 있는지 검사해 cnt 배열에 저장했습니다. 이 두 작업은 백트래킹 내 body가 커지지 않게 하려고 전처리한 겁니다. 백트래킹의 base condition은 k가 10일 때 남아있는 알파벳이 있는지 검사하는 방식으로 했습니다. 만약 남아있는 게 없다면 true를 반환해 순차적으로 종료되게 하였습니다. 백트래킹의 body에서는 숫자 k를 1개부터 cnt[k]까지 하나씩만 추가하면서 k+1로 넘어가게 했고, cnt[k]까지 추가해도 true를 반환 못 받았다면 k 숫자를 추가하지 않고 넘어가게 했습니다.  ..

1. 문제 풀이 크루스칼 알고리즘을 사용하여 풀이하였다. 랜선의 길이가 짧은 것을 우선 선택하면서 MST를 만들고, 선택되지 않은 랜선들의 길이를 모두 합하면 됩니다. 이때, Union에 성공한 간선의 개수를 세는 cnt변수를 두고 마지막에 cnt가 n-1인지 조사하면 모든 컴퓨터의 연결 여부를 확인할 수 있다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef ..