CS
[BaekJoon] 백준 2667번 단지번호 붙이기
[BaekJoon] 백준 2667번 단지번호 붙이기 문제: https://www.acmicpc.net/problem/2667 내코드 - 기본적인 bfs문제 - 단지내 아파트 수 세주는 것과 입력받을 때 아파트가 공백없이 입력된다는 점을 주의해서 입력받으면됨. - 백준에 제출할때는 scanf_s대신 scanf 써줌 - 자잘한 실수가 많았음. - 아래는 아이패드에 정리한 내용. 코드블럭 #include #include #include #include #include #include using namespace std; int n; int arr[25][25]; bool visited[25][25] = { false, }; list l; int num = 0; int numApt; pair cur; queue..
[BakJoon] 백준 7569번 토마토
[BakJoon] 백준 7569번 토마토 문제: https://www.acmicpc.net/problem/7569 내코드 - 처음에는 큐에 queue 이렇게 하려고 했으나 stl에는 배열이 들어가지 않는다고 해서 dist는 배열을 따로 만들어주었다. - 7576번 토마토와 비슷하지만 높이가 추가 되서 인접한 토마토만 추가해주고 높이만 따로 생각해주면 된다. - 아래는 아이패드에 정리한 내용 #include #include #include #include using namespace std; int h, m, n, maxN = 0; int x, y, z; int arr[100][100][100]; int dist[100][100][100]; bool visited[100][100][100]; queue q..
[BaekJoon] 백준 7576번 토마토
[BaekJoon] 백준 7576번 토마토 문제: https://www.acmicpc.net/problem/7576 내코드 - BFS 문제 - 처음에 익어있는 토마토의 위치를 전부 큐에 넣고 시작해야하는 문제 - 크게 어렵진 않았다. - 아래는 아이패드에 정리한 내용 #include #include #include #include #include using namespace std; int m, n, maxN = 0; int arr[1000][1000]; bool visited[1000][1000] = { false, }; queue qu; pair cur; void isNear(int a, int b) { if (a = n || b >= m) return; if (ar..
[BaekJoon] 백준 1697번 숨바꼭질
[BaekJoon] 백준 1697번 숨바꼭질 문제: https://www.acmicpc.net/problem/1697 내코드 - bfs문제인데 인접한 값 == 수빈이가 이동할 수 있는 위치(즉, 수빈이의 현재 위치를 x라고 하면 x-1, x+1, x*2)으로 생각하고 풀면 간단한 문제. - 처음에 런타임 에러가 나서 왜 그런가 봤더니 수빈이가 이동하는 위치가 100,000을 넘어가면 visited에서 배열의 범위가 초과되기 때문에 나는 거였다. - 그리고 틀렸다고 나와서 이번에는 수빈이와 동생의 위치가 같을 때를 따로 조건을 걸어주었다. - 배열을 초기화 할때 bool visited = { false, }이런식으로 하니까 전체가 같은 값으로 초기화가 됨. - 아래는 아이패드에 정리한 내용. #includ..
[BaekJoon] 백준 2178번 미로탐색
[BaekJoon] 백준 2178번 미로탐색 문제: https://www.acmicpc.net/problem/2178 내코드 - 시작점으로부터 거리를 측정해야하는 전형적인 bfs로 풀면 되는 문제 - scanf_s를 visual studio에서 썼는데 백준에서는 scanf를 써서 풀었다. - 무한대라는 의미에서 math.h를 include해서 INFINIFY를 써줬는데 0으로 출력되서 int 범위의 최대값인 2147483647을 초기 최소값으로 입력해줬다. - dist를 저장하기 위해 queue에 값을 저장할때 이중 pair를 써줬다. - 아래는 풀이를 위해 아이패드에 정리한 내용 #include #include #include #include #include using namespace std; int..
[BaekJoon] 백준 1926번 그림
[Baekjoon] 백준 1926번 그림 문제: https://www.acmicpc.net/problem/1926 내코드 - BFS를 이용하는 문제 - 코드짜고 바로 통과할만큼 간단한 문제였다. - 아래 파일은 아이패드 노타빌리티에 정리한 내용 #include #include #include #include using namespace std; int n, m; int** arr; bool** visited; int num = 0, maxNum = 0; queue qu; void isNear(int p, int q) { if (p = n || q >= m) return; if (arr[p][q] == 1 && visited[p][q] == false) { qu.push(..
[Algorithm] BFS(Breadth First Search), DFS(Depth First Search)
[Algorithm] BFS(Breadth First Search), DFS(Depth First Search) 블러드 필(Blood Fill) 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘 BFS(queue), DFS(stack)로 풀수 있음. BFS(Breadth First Search) - 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘. - 모든 칸이 큐에 1번 씩만 들어감이 보장되므로 시간 복잡도는 칸이 N개 일때 O(N). - 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문. - 그래프를 시작점을 루트로 하는 트리라고 생각한다면 height가 작은 노드부터 차례대로 방문하는 전체 탐색 방식이라고 할수 있음. - 현재 보는 칸으로부터 추가되는 인접한 칸은 반..
[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix)
[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix) 수식 표기법의 종류 * 연산자: +, -, *, ... 피연산자: 1, 2, 3, ... 1. 전위 표기법 (ex. +AB) 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법. 2. 중위 표기법 (ex. A+B) 연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법. 이항 연산자 표현이 적합하다. 3. 후위 표기법 (ex. AB+) 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법. 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장. 수식 표기법의 변환 1. 중위 -> 전위 중위 표기법으로 표기된 3+2+4*5+3/1 를 전위 표기법으로 바꿔본다...