노는 게 제일 좋아

이런 문제를 싫어하지만.. 자주 나오는듯 하다. 내용이 많아서 어려운 문제다. 게다가 6초나 준다.. 시간이 얼마나 많이 걸릴 지 예상이 가는 문제다. https://www.acmicpc.net/problem/9019 #맞은 풀이 #include using namespace std; const int MAX = 10000; int A,B; bool visited[MAX]; int main(){ int T; cin >> T; //테케 while(T--){ cin >> A >> B; //초기화 for(int i = 0; i

음.. 처음 생각하기 정말 어려웠다. 어떻게 BFS로 푼다는 거지..? BFS는 모든 단계 탐색이 비용이 같아야하는데.. 쟤는 0초인데?? 우선순위 큐를 쓰라는 말을 들어도 못알아듣다가 다른 분의 코드를 조금 보고나서야 알았다. https://www.acmicpc.net/problem/13549 #맞은 풀이 #include using namespace std; int N, K; bool visited[100002]; int main(){ cin >> N >> K; //왜 우선순위 큐를 사용해야하느냐?? //+1,-1의 노드를 탐색하는 것과 *2 노드를 탐색하는 것은 다르다. //즉, *2를 하는 것은 할 수 있는 만큼 하고 +1과 -1을 해야한다. //즉, 단계도 단계지만 시간으로 구분되어야 한다. //..

우리가 BFS나 DFS를 사용하는 것은 알아봤다. 응용이 어떻게 될 수 있으며어떤 개념을 알고 가야하는지 고찰해보자. (대부분 BFS를 요구하고 DFS는 재귀를 이용하는 문제가 많다) 우리는 그렇다면 어떤 문제가 DFS고 BFS인지 알 수 있어야 한다. 이 문제를 보자 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 1926번 C++ [CPP] 딱히 BFS인지는 모르겠으나 BFS로 해도 될 것 같은 느낌이 든다. 다음 문제를 보자 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] 최소의 칸 수를 구하란다. 즉, 탈출까지 최단거리를 구하란다. 그래서 BFS를 쓴다. 솔루션을 찾았을 때 BFS..

우선 Python 에서의 split 함수를 보자 2개의 인자를 받는다 1. delimiter, 구분자 2. 해당 문자열 알아봤다면 시작해보자 그렇다면 우리는 우선 가장 흔한 공백을 기준으로 만들어보자 막연하게 드는 생각은 공백을 만나면 공백을 만나기 전까지의 모든 문자열을 어떠한 컨테이너에 넣고 문자열을 다시 진행하면 될 것 같다. 즉, 문자열을 하나하나 조사한다는 말이다. 공백을 만나면 그때까지의 문자열을 다시 집어넣고 다시 공백이 나오지 않을 때까지 탐색한 후 다시 반복한다. 만약 문자열이 끝나면 끝나게 된다. 대충 이런 생각으로 짠다. 위에서 아이디어를 뽑아보자면 1. 문자열을 하나하나 조사할 것임 2. 공백만났을 때 하는 행동 3. 문자열의 끝에 닿았을 때 하는 행동 C++에서 알다시피 문자열은 ..

toupper와 tolower를 알고 있다면 쉽게 풀 수 있는 문제였다. 어렵지 않았고 논리적으로만 생각하면 되었다. https://programmers.co.kr/learn/courses/30/lessons/12951 #맞은 풀이 #include using namespace std; string solution(string s) { //check가 true인 상태일 때(공백 다음에 나오는 문자) int i = 0; //true로 시작해야 맨 처음 단어에 대응 가능. bool check = true; while(s[i]){ //공백일 경우 flag하고 넘어감 if(s[i] == ' '){ check = true; i++; continue; }else{ //공백이 아닌 문자를 만났을 경우 //1.첫번째 문..

스택을 아는데도 문제를 보면 막상 생각이 안난다. 스택의 문제를 생각해보면 스택은 바로 이전의 것과 비교하는 것이 많이 나온다. 이 문제도 마찬가지였다. https://programmers.co.kr/learn/courses/30/lessons/12973 #맞은 풀이 #include #include #include using namespace std; int solution(string s) { int answer = -1; //문자의 개수가 홀수라면 모두 없앨 수 없음 if(s.size()%2 == 1) return 0; stack stk; for(char x : s){ if(stk.empty()){ stk.push(x); }else{ if(stk.top() == x) stk.pop(); else st..

투 포인터 좋은 예라고 볼 수 있다. 여기서 R의 예외조건에 대해서 알아야하는데 내가 짠 알고리즘에서는 R이 커져버려서 while문에 다시 못들어가는데 있었다. https://www.acmicpc.net/problem/16472 #맞은 풀이 #include using namespace std; int N; string s; map kind; int ans = 0; // 최대 구간 길이 int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>N; cin>>s; int num = 0; // 종류 int L = 0; int R = 0; if(s.size()

어렵지 않지만 예외가 있었다. 바로.. 같은 용액이 쓰이면 안된다는 것이었다. 처음에 나는 두번째 가까운 원소까지 찾을 생각은 안했었다. 하지만 모든 것이 알칼리성이나 산성으로 되었을 때는.. 두 번째로 가까운 원소가 필요해졌다. https://www.acmicpc.net/problem/2470 #맞은 풀이 #include using namespace std; //두 용액 더한 값 범위 int로 가능 int N; int liq[100000]; vector ans; //해당 액체의 숫자에 (-1) 곱한 것과 가장 가까운 원소를 찾아야함 //즉, x와 일치하거나 가장 가까운 원소를 return함. int bisearch(int input){ int x = -input; //우리가 찾아야하는 값. int l ..

이것도 아주 중요한 문제라고 할 수 있다. 중복되는 값을 어떻게 골라내느냐이다. https://www.acmicpc.net/problem/1039 #맞은 풀이 #include #include #include #include using namespace std; int N, M, K; int ans; set check[11]; //★★★★★★★ void func(string s, int cnt) { string after = s; int x = stoi(s); //string으로 받은 숫자. //K번 바꿨을 때. if (cnt == K) { ans = max(x, ans); return; } //바꿀 수 있는 모든 경우의수 확인 for (int i = 0; i < M - 1; i++) { for (int ..

백트래킹에서 그래도 조건이 많이 붙어서 가지치기를 어떻게 하는지 공부할 만한 문제다. 행과 열 처리는 어떻게든 가능하지만 3*3이 어느 칸인지 찾는 것을 조금 고민해볼 필요는 있다. 결국 1~3까지 첫 째 4~6까지 두 번째.. 이렇게 생각하면 어떻게 할 지 감이 온다. https://www.acmicpc.net/problem/2580 #맞은 풀이 #include #include using namespace std; int pane[9][9]; // 9*9 게임판 bool check = false; // 답을 찾았는지 체크 vector vec; // 채워야 할 곳의 좌표 int number = 0; // 채워야 할 곳의 개수 //조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를..