백준108

• [백준 14502번 / C++] 연구소 1. 벽을 설치 할 수 있는 경우를 완전탐색으로 구하기 2. 벽을 설치 할 수 있는 경우에 실제 map에 벽으로 만들기 3. bfs 돌리기 4. 안전지역인 영역이 큰 값으로 갱신해나가기 #include #include #include #include #include using namespace std; int map[8][8]; int wall[8][8]; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int max_cnt = -1; int m, n; int path_cnt; queue q; void bfs() { int s_map[8][8]; int visited[8][8] = { 0, }; int cnt = 0; queue birus; for.. 백준/완전 탐색 2022. 1. 28.

• [백준 3273번 / C++] 두 수의 합 투포인터 문제다. 1. 입력된 모든 값을 벡터에 저장한 후 오름차순으로 정렬시킨다. 2. 인덱스의 시작점, 인덱스의 끝점을 저장 시킨다. - 시작점과 끝점에 해당하는 원소가 같으면 시작점만 오른쪽으로 이동 - 시작점과 끝점에 해당하는 원소의 합이 X의 값과 같으면 카운트 및 시작점 오른쪽으로 이동. - 시작점과 끝점에 해당하는 원소의 합이 X의 값보다 작으면 끝점 왼쪽으로 이동. - 시작점과 끝점에 해당하는 원소의 합이 X의 값보다 크면 시작점 오른쪽으로 이동. #include #include #include using namespace std; vector v; int s, e; int main() { int n; cin >> n; v.resize(n, 0); for (int i = 0; i < n; .. 백준/증가수열 & 투포인터 2022. 1. 27.

• 

  [백준 2636번 / C++] 치즈 1. 사각형의 테두리는 0으로 되어있다. 2. {0,0}에서 bfs를 돌린다. 3. {ny,nx} 좌표를 가지고 있는 map의 값이 1이라면 벽이라고 생각을 하고 뚫고 가진 못하지만 방문 처리만 해주자. 4. 상,하,좌,우로 연결된 길을 모두 탐색했다면 visited에 1로 기록되어있는 map을 0으로 갱신하자. (즉, 벽을 허물라) 5. map에서 갱신 된 내용이 없으면 리턴하고 그렇지 않다면 다시 {0,0}에서 bfs를 돌린다. #include #include #include #include using namespace std; queueq; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int map[100][100]; int visited[100][1.. 백준/DFS BFS 2022. 1. 27.

• [백준 1072번 / C++] 게임 " 1 ~ INT_MAX " 범위에서의 이분탐색을 통해 result 값을 갱신. result 값과 Z값을 비교한 결과 result값이 크다면 high 위치를 mid-1 로 변경, 반대일 경우 low 위치를 mid+1로 변경. answer값이 0 그대로라면 0출력, answer값에 변화가 있었다면 answer값 출력. #include #include using namespace std; typedef long long ll; ll x, y, z; bool check(int mid) { ll X = mid + x; ll Y = mid + y; ll result = Y*100/X; if (result > z)return true; else return false; } int main() { cin >> x >.. 백준/이분탐색 2022. 1. 26.

• [백준 1450번 / C++] 냅색문제 이 문제는 상당히 까다로운 문제이니, " n = 4 , c = 3, v = [1,2,3,4]" 라는 값으로 재귀가 어떻게 돌아가는지 코드를 보고 그림으로 한번 표현해보자. part1 / part2로 나뉘어서 진행 part1을 예로 들어서 설명하겠다. part1에는 현재 [1,2] 라는 무게를 담고 있고 재귀를 도는데 "1"의 무게를 가진 놈을 담아? Yes or No (2가지) "2"의 무게를 가진 놈을 담아? Yes or No (2가지) 위의 경우를 가지치기로 만들어진 sum의 개수는 2X2 = 4 가지 이며, part1의 sum값은 [ 0, 2, 1, 3] 이 된다. part2의 sum값은 [0, 4, 3, 7] 이 된다. part2는 오름차순으로 정렬을 시킨다. [0, 3, 4, 7] 여기서 par.. 백준/DP 2022. 1. 26.

• [백준 2776번 / C++] 암기왕 1. 수첩 1에 적혀있는 수들을 오름차순으로 정렬. 2. 이분탐색을 통해서 해당하는 값이 있으면 1 출력. 없으면 0 출력 * unordered_map 을 통해서도 이 문제를 해결할 수 있습니다. 자료구조 자료구조" data-og-description="*헤더로 을 갖는다. 은 key 와 value 의 쌍으로 이루어진 균형 이진 트리이다. key 를 기준으로 사전순으로 정렬되어 있기 때문에 검색 속도가 빠르다. 바로 map 의 쓰임을 baebalja.tistory.com #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; .. 백준/이분탐색 2022. 1. 26.

• 

  [백준 14627번 / C++] 파닭파닭 1. 범위가 "1 백준/이분탐색 2022. 1. 25.

• 

  [백준 5430번 / C++] AC dequeue 자료구조를 활용하자. dequeue를 활용하지 않고 벡터를 활용하여 R이라는 명령어가 들어왔을 때 reverse라는 정렬을 할 수도 있다. 하지만 수행할 함수가 100,000이면서 R이라는 명령어만 주어졌고, n의 개수가 100,000이라면 100억번을 수행해야한다. 그렇다면 시간초과가 발생하게 된다. 또한, D라는 명령어가 들어왔을 때는 맨 앞에 원소를 지우는 erase 함수를 수행할 수 있지만 뒤에 있는 모든 원소를 하나씩 당겨와야하기 때문에 그만큼의 시간이 든다. 그렇기 때문에 dequeue라는 자료구조를 활용해서 제일 앞의 원소를 뺄지 또는 제일 끝의 원소를 뺄지를 back이라는 비트변수가 체크해준다. 즉, R이라는 명령어가 들어오면 back라는 변수를 1로 세팅하면서 현재 거꾸로 .. 백준/비트마스킹 2022. 1. 25.

• 

  [백준 14620번 / C++] 꽃길 완전 탐색 문제이다. 1. dfs 구현은 동일 2. 현재 지점에서 상하좌우를 돌아봤을 때 맵을 초과했거나 또는 이미 만개한 꽃잎과 겹치는 부분이 있을 경우 continue 3. 위의 조건을 통과하였다면 현재위치 포함 상하좌우 모두 visited 라는 배열에 저장 후 dfs 호출 4. dfs 호출 이후 코드는 visited 배열을 다시 0으로 초기화. (다른 지역에서 꽃이 필 경우도 모두 탐색해야하기 때문) #include #include #include int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; int n; int map[10][10]; int visited[10][10]; int result = INT_MAX; using namespace std; vo.. 백준/완전 탐색 2022. 1. 25.

• [백준 1189번 / C++] 컴백홈 dfs를 활용해서 완전 탐색으로 풀면 된다. 1. dfs 기본 문법을 활용해서 상 하 좌 우에 조건에 부합되면 들어간다. 2. 집의 좌표값과 일치하고 좌표값까지의 distance가 K와 일치하면 cnt+1을 해준다. 3. 재귀 처리후 돌아오면 visited 배열을 0으로 세팅한다. (다른 방향으로 가는 루트도 체크 해줘야하기 때문에 초기화) #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; int m, n, k; int map[5][5]; int visited[5][5]; int cnt; void dfs(int y, int x, int dis) { if (x == n - 1 && y == 0&&dis==k) .. 백준/완전 탐색 2022. 1. 25.