본문 바로가기

Algorithm

 (2139)
(C++, Python3) - 백준(BOJ) 1697번 : 숨바꼭질 https://www.acmicpc.net/problem/1697📕 풀이방법📔 입력 및 초기화1. 수빈이의 좌표 n, 동생의 좌표 k를 선언 후 입력받습니다. 2. 현재 탐색할 경로정보를 저장할 deque dq를 선언 후 현재 수빈의 좌표와 시간 0을 초기값으로 넣어줍니다. 3. 각 좌표 check배열을 선언 후 0에서 10만까지 위치에 존재할 수 있으므로 10만1의 크기를 선언해줍니다.📔 풀이과정함수 bfs를 구현해줍니다.1. dq에서 원소를 pop해 현재 좌표 pos가 k인지 비교해 맞다면 해당 time을 반환합니다. 2. 수빈이 현재 좌표에서 갈 수 있는 곳은 x-1, x+1, x*2이므로 범위를 초과하지 않으며 해당 좌표가 방문하지 않았다면 방문처리 후 dq에 append해줍니다. * 도착..
(C++) - 백준(BOJ) 11403 : 경로 찾기(BFS) 답 #include #include #include #include using namespace std; int N,a[101][101],d[101][101],c[101][101]; queue q; void BFS(int t)//정점에 연결되어 있는 간선을 모두 본 후에 마지막에 자신을 거치는 경로가 있는지 살펴본다 { q.push(t); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 1; i > N; for (int i = 1; i a[i][j]; } for (int i = 1; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11403번:경로 찾기(DFS) 답 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std;int N,a[101][101],d[101][101],c[101][101],t;queue q;void DFS(int x)//정점 x에 연결되어 있는 모든 간선을 확인하고 경로에 등록한다{ for (int i = 1; i > N; for (int i = 1; i a[i][j]; } for (int i = 1; i
(C++) - 백준(BOJ) 2252번 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 문제였습니다. 풀이방법 1. 단 방향그래프로 만듭니다. 2. dfs를 수행하면서 모두 호출한 후에는 stack에 정점을 push해줍니다. 3. 모든 원소를 stack pop하면서 출력합니다. Code indegree이용하는 법 #include #include #include using namespace std; int N,M,u,v,ins[320..
(C++) - 백준(BOJ) 11723 : 집합 #include #include using namespace std; int M, S, n; char k[10]; int main() { scanf("%d", &M); while (M--) { scanf("%s", k); if (!strcmp(k, "add")) { scanf("%d", &n); n--; S = (S | (1
(C++) - 백준(BOJ)코딩 1149번 : RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2차원 bottom up dp로 풀었습니다. 풀이방법 D[i][j] = i번째 집을 j색으로 칠할 때 최소 비용 빨강:1 초록:2 파랑:3 D[1][1] = A[1][1]; D[1][2] = A[1][2]; D[1][3] = A[1][3]; A[i][j] = 입력 j로 칠했을 때 i-1, i+1번째 집은 j색으로 칠할 수 없다. 1.i번째 집을 R로 칠했을 때 (2
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1967번:트리의 지름 답 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include using namespace std;int n, u, v, w;struct Edge { int to; int cost; Edge(int to, int cost) : to(to), cost(cost) { }};vector a[10001];int c[10001];int d[10001];void bfs(int start) { memset(d, 0, sizeof(d)); memset(c, 0, sizeof(c)); queue q; c[start] = 1; q...
(C++) - 백준(BOJ) 1991번 : 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리순회를 구현해보는 문제였습니다. 풀이방법 전위순회(preorder) : 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위순회(inorder) : 왼쪽 자식 -> 루트 -> 오른쪽 자식 후위순회(postorder) : 왼쪽 자식 -> 오른쪽 자식 -> 루트 Code #include using namespace std; int n, a[26][2]; void preOrder(int x){ if(x..

티스토리툴바