목록알고리즘/백준 (59)
쌓고 쌓다
https://www.acmicpc.net/source/78693009 풀이 방법BFS를 이용한다.노드 방문시X노드부터 방문 노드까지의 거리가 담긴 dis에 담긴 거리가 K와 동일하다면 답에 추가한다. 전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] inputs = (reader.readLine()).split(" "); ..
https://www.acmicpc.net/source/78677494풀이 방법[i][j] 위치에서 벽을 부순 상태인지 아닌지를 구분할 수 있게 3차원 배열을 이용해 푼다.[i][j][0] 이라면 i,j 위치에 있을때 이전까지 벽을 한번도 부수지 않은 상태이고[i][j][1] 이라면 i,j 위치에 있을때 이전에 벽을 부순 이력이 있는 상태이다. [i][j][0]에서 다음 좌표에 벽을 만났다면 이 벽을 부술 수 있는 상태이다.[i][j][1]이라면 다음 좌표에 벽이 있다면 이전에 벽을 부순 상태이기 때문이 벽을 부술 수 없다. 위의 3차원 배열을 이용해 BFS를 이용해 푼다. 전체 코드import java.io.*;import java.util.*;public class Main { stati..
https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 전체 코드 #include #include using namespace std; int main(void) { string str; int res = 0; bool flag = false; getline(cin, str); for (int i = 0; i = 'A' && str[i] = 'a' && str[i]
[백준] 트리의 높이와 너비 2250번 C++ 풀이
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 전체 코드 #include #include #include using namespace std; pair node[10001]; vector v[10001]; int column[10001]; int parent[10001]; int col = 1; int h = 1; int mh = 1; void inorder(int root) { mh = max(mh, h); if (node..
[백준] LCA 11437번 C++ 풀이
https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 전체 코드 #include #include using namespace std; vector v[50001]; int parent[50001]; int depth[50001]; int N,M; void DFS(int x) { for (int i = 0; i < v[x].size(); i++) { if (depth[v[x][i]] == -1) { depth[v[x][i]] = depth[x] ..
https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 전체 코드 #include #include #include using namespace std; vector v[100001]; int parent[100001][17]; // log2(100000) = 16.61 -> 17 int depth[100001]; int N,M; void DFS(int cur) { for (int i = 0; i < v[cur].size(); i++) { in..
[백준] 트리의 순회 2263번 C++ 풀이
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 전체 코드 #include #include using namespace std; vector inorder; vector postorder; int Index[100001]; int N,root; void preorder(int inStart, int inEnd, int postStart, int postEnd) { if (inStart > inEnd || postStart > postEnd) return; int root..
[백준] 주사위 1041번 C++ 풀이
https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 전체 코드 #include #include #include using namespace std; vector v; long long N; long long minsum[6]; bool visit[6]; void solve(int idx, int cnt, long long sum) { if (cnt < 6) { if ((visit[0]==true&&visit[5]==true)..