Algorithm/boj

백준16916 // cpp 문자열 포함검사 O(N+M), strstr vs find

https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net * cpp 문자열 포함검사 O(N+M) strstr(문자배열1, 문자배열2) 반환 : 위치 포인터 //못찾으면 NULL ex)char[] c1= i`m on my way char[] c2 = way char[] c3=hpeth strstr(c1,c2) // return 11 strstr(c1,c3) //return NULL #include using namespace std; char s[1000004], p[1000004..

백준 9046 복호화 //map을 정렬하는방법, vector로 옮겨라, 문자열은 map필요X 배열만으로됨

https://www.acmicpc.net/problem/9046 9046번: 복호화 입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이 www.acmicpc.net * map을 정렬하는방법, vector로 옮겨라 vector v(m.begin(), m.end()); 이후 sort 하면된다 sort(v.begin(), v.end(),cmp) * 문자 index는 map필요X 배열만으로됨 사실 이문제는 문자를 index로 쓰기때문에 a[문자-'a']++ 을 카운트로 사용하는것 만으로 해결된다. map을 쓸필요가 없었다.. - 숫자 to int [문자-'0'] -..

백준 9934 완전이진트리 // 탐색결과를 트리로원복

9934번: 완전 이진 트리 (acmicpc.net) 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net * 탐색결과를 트리로원복 1 6 4 3 5 2 7 mid를 푸쉬, 재귀적으로 mid를 푸쉬하면된다. 3 6, 2 ... 종료조건국룰 : start>end ----> return; 종료조건 : start==end -> push(mid==start==end), return #include using namespace std; int _end,n; vector ret[14]; int a[1..

백준 2529 부등호 // 재귀로 완탐구현 , string 정렬시주의

2529번: 부등호 (acmicpc.net) * 재귀로 완탐구현 기본꼴 : go(index, 임시저장결과값) 1. 종료조건 2. 직접해보면서 일반화하라. 마지막숫자 == num[idx-1] 비교할숫자 == i 비교할op == a[idx-1] 임을 알 수 있다. * string 정렬시주의 "23" "123" 비교시 앞부터 하나씩 비교 하므로, 23이 더 크게됨에 주의. #include using namespace std; int n, temp, check[14]; vector ret; char a[14]; bool good(char a, char b, char op) { if (op == '' && a > b) return true; return false; } void go(int idx, string ..

백준 1987 알파벳 // 노드가 각자의visit을 가져야한다면 원복! , dfs visit[now] [next]둘중 하나만 해라

1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net * 노드가 각자의visit을 가져야한다면 원복! visited[a[ny][nx] - 'A'] = 1; dfs(ny, nx, cnt + 1); visited[a[ny][nx] - 'A'] = 0; * dfs visit[now] [next]둘중 하나만 해라 void dfs(int y, int x, int cnt) { v[y][x]=1;//항상 참이됨 ~~~~ v[ny][nx]=1; dfs[ny][nx]; } 문제 ..

백준 3197 백조의 호수 // bfs멈춰는 tempQ, 1차원에서 논리짜라, next경우의수를 나눠서 처리하라, pair Q 클리어하는법

3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net * 논리짜기 물) . . 다음(next)경우의수 : '.' X L '.'-> 계속, 입력시 이미큐에넣어놓음, 방문처리도함 -> 처리필요X 'L'->계속, L도 물로간주. 입력시 처리완료. -> 처리필요X X -> 멈춰 1.tempQ push 2. 방문처리 3. there을 '.'으로 수정. 백조) . . 다음(next)경우의수 : '.' X L '.'-> 계속, Q.push 'L'->..

백준 14497 주난의 난// bfs멈춰는 큐2개로 해결, 어려우면 1차원에서 논리를 짜라

14497번: 주난의 난(難) (acmicpc.net) 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net * 어려우면 1차원에서 해보면서 논리를 짜라 # 1 0 0 1 0 0 계속 //q.push 1->멈춰, cnt++ //temp.push, q=temp, cnt++ ex) next가 1일때, temp.push만 되므로 q.size==0이 됨 => q=temp, cnt++ 실행됨. //새로운시작 * bfs는 도중에 탈출X, 방문배열에 정답을 모두담고, 출력만해라. * 탈출조건 문제 while (true..

백준 12851 // bfs암기, 정답 경우의수 구하기는 cnt[next]+=cnt[here]

12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net * 정답 경우의수 구하기 핵심코드 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next >= 0 && next >k ; /* * bfs algorithm * 1.초기화 cnt[n] = 1; * 2.종료조건 * 3.next 범위체크 * 4.next 방문체크 * 5.visit[next] 갱신 * 5.1 q.push!..