본문 바로가기

코테42

[BOJ] 숫자판 점프 Link: https://www.acmicpc.net/problem/2210Level : S2유형 : 완전탐색, dfs📌 문제 탐색하기입력 : 5X5 배열 각 요소 값 이 문제는 임의의 위치에서 인접해있는 4 방향으로 5번 움직이는 문제다.따라서 5*5 총 25개의 인덱스에서 4 방향으로 탐색해야 한다. 시간 복잡도를 생각해보면 임의의 점 선택 : 5*5선택된 점에서 4 방향으로 5번 움직이는 경우의 수 : 4*4*4*4*4 시간복잡도는 O(n^2)이지만 연산 횟수는 25,600번 밖에 되지 않는다. 따라서 이 문제는 '완전탐색'으로 진행한다. 📌  코드 설계하기1. 5*5 배열의 값을 입력으로 받는다.2. 반복문을 돌면서 임의의 점을 택하고 그 점에서 대해 dfs 함수를 실행한다.3. 재귀를 이용하.. 2024. 8. 7.
[BOJ] 부분수열의 합 Link: https://www.acmicpc.net/problem/1182Level : S2유형 : 부르트포스, 백트래킹📌 문제 탐색하기N (1S ( |S|  이 문제는 주어진 수열에서 내가 원소를 뽑아 부분수열을 만들 수 있다.이때, 내가 뽑는 원소의 갯수는 정해지지 않았다. 즉 합이 S가 되기 위해 뽑을 수 있는 모든 경우의 수를 고려해야 한다. 조합을 생각해서 시간 복잡도를 대략 계산해볼 수 있다.N의 최대가 20이므로 위의 조합에 대입해보면, 시간복잡도는 O(2^n)이다.2^n이 최악의 시간복잡도이지만, 수의 최댓값이 20으로 약 1,000,000 + a 정도 밖에 되지 않는다. 따라서 '완전탐색'을 이용하여 뽑을 수 있는 원소의 갯수를 다 고려해본다. 📌  코드 설계하기1. 정수의 갯수가 .. 2024. 8. 6.
[BOJ] 두 스티커 Link : https://www.acmicpc.net/problem/16937Level : S3유형 : 부르트포스📌 문제 탐색하기H,W (1N (1R, C (1 스티커 N개 중에서 스티커 2개를 선택해 붙여있을 때 붙여진 스티커 넓이의 최댓값을 구하기 위해서 먼저 N개 중에서 스티커 2개를 뽑아야 한다. 이때 스티커의 최대 수는 100이므로이중 반복문을 이용해서 선택한다고 했을 때, 시간 복잡도는 O(n^2)은 약 10,000 정도이다. 또한 스티커는 회전하여 붙일 수 있으므로 2개의 스티커가 회전하는 경우의 수는 2*2 = 4가지이다. 완전 탐색으로 탐색해도 시간복잡도가 커지지 않으므로 전체 N개에서 스티커 2개를 뽑을 수 있는 경우를 모두 탐색하여 진행한다. 📌  코드 설계하기1. 문제의 입력값.. 2024. 8. 5.
백준 2178번 - 미로 탐색 #include using namespace std; int n, m, y, x, ny, nx, visited[103][103]; char adj[103][103]; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; //최단경로 문제-> bfs 이용 int main(){ cin >> n >> m; for(int i=1; i adj[i][j]; } } queue q; visited[1][1] = 1; q.push({1,1}); while(q.size()){ tie(y, x) = q.front(); q.pop(); for(int i=0; i 2023. 11. 8.
[queue]백준 10845번 - 큐 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net #include #include #include using namespace std; int n; queue q; int main(){ cin >> n; for(int i=0; i> s; if(s=="push"){ int num; cin >> num; q.push(num); }else if(s=="pop"){ if(q.size()==0) cout 2023. 10. 1.
[stack]백준 9012번 - 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net #include #include using namespace std; int n; int main(){ cin >> n; for(int i=0; i> s; for(int i=0; i 2023. 10. 1.

티스토리툴바