본문 바로가기

알고리즘

 (100)
백준 2250 트리의 높이와 넓이 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. �� www.acmicpc.net 트리의 중위 순회를 이용하는 문제이다. 전위순회, 중위순회, 후위순회도 정리하면 좋겠다 전위 : root --> left --> right 중위 : left --> root --> right 후위 : left --> right --> root /* 트리의 높이와 너비 */ #include #include #include #include #define MAX_NODE 1000..
백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 알고리즘이랑 메모이제이션을 섞어서 풀었다. 이중 배열을 이용한 다익스트라 알고리즘은 시간복잡도가 O(N^2)인데 반해서 우선순위 큐를 이용하면 O(N * log N)까지 줄일 수 있다. 1. 각 점에서 X까지 최단거리를 다익스트라를 이용해서 구한다. 이 때 지나치는 정점을 활용하는 게 중요하다 예를 들어서 1 -- > 2 --> 3 --> X가 경로라면 2 --> X의 비용은 1 ..
백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 그래프 탐색과 DFS의 혼종이다. 그래프에 Cycle이 있는지 점검하는 문제다. 무식하게 풀자면 모든 노드를 DFS 돌려서 자기 자신으로 돌아오는 지 체크하면 된다! 근데 중복이 엄청 많을 것이다. 아무리 시간 복잡도가 3초라도 이런건 무조건 시간초과다 메모이제이션을 통해 최대한 중복 체크를 줄인다! 각 노드의 상태는 둘로 나뉜다. 1. 이전 DFS에서 방문한 노드 - Cycle 못 만든다. 2. 이번..
백준 3197 백조의 호수 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 1. 시간 복잡도 시간복잡도를 알면 문제 접근법이 그나마 보인다. 주어지는 R과 C가 각각 1500 이하 이므로 약 10^3이다. O(N^2) 까지는 너끈하지만 O(N^3)은 10^9가 된다. 대강 10억이다... 이건 시간 제한 1초에 무조건 걸리므로 최대 O(N^2 * logN)인 알고리즘을 찾는다. (적어도 N^3은 안된다...) 2. 문제풀이 L이 백조이고 이 둘이 만나는 데 걸리는 날을 ..
백준 1786번 찾기 KMP 알고리즘을 이용해서 풀 수 있는 문제다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net #include #include #include using namespace std; string s, t; int cnt; vector position, pi; void getPi(); void KMP(); int main(void) { char c; while ((c = getchar()) != '\n') { s += c; } while..
백준(BOJ) 1765번 피자 굽기 자바(java) https://www.acmicpc.net/problem/1756 1756번: 피자 굽기 문제 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 www.acmicpc.net https://github.com/asomeJay/algorithm/blob/master/Acm_icpc/Java/src/boj1756.java asomeJay/algorithm Algorithm Repository. Contribute to asomeJay/algorithm development by creating an account on GitHub. github.com 이분 탐색으로 풀 수도 있지만..
백준(BOJ) 1033번 칵테일 https://www.acmicpc.net/problem/1033 문제가 진짜 이상하다... 문제만 해석하면 아주 쉽게 풀 수 있다. 문제 조건은 다음과 같다. N개의 재료가 있고, N-1개의 레시피가 있다. 이들을 조합해서 N개 재료의 질량비를 알 수 있다. 그 말인 즉슨 이 재료들을 연결하면 TREE이다. 레시피는 재료 둘을 연결한다. 각 재료를 NODE로 각 레시피를 EDGE라고 볼 수 있다. Cycle이 없는 Graph이기 때문에 Tree이다. 해결은 간단하다. Tree의 점 하나를 찍고 그 점에 임시로 전체 레시피의 최소 공배수를 넣는다. 그 점부터 시작해서 재료 간의 질량비를 이용해서 전체 질량 비를 구한다. /* 1033 칵테일 */ #include #include #include #incl..
백준(BOJ) 11585 속타는 저녁 메뉴 내 속도 탄다. 이런 젠장 https://www.acmicpc.net/problem/11585 KMP 알고리즘을 사용하면 된다. 룰렛을 돌릴 문자열을 한번 더 더하면, 즉 원래 문자열이 S라면 S + S라고 하면 룰렛을 돌린 효과를 얻을 수 있다. S + S에 대해 KMP 알고리즘을 적용하면 문제가 쉽게 풀린다. 단, S + S의 마지막을 POP 해줘야 한다. 안그러면 (예를 들어) ABC 라는 문자열이 들어왔을 때 ABCABC가 되어서 상근이가 고기를 먹을려면 나와야하는 ABC를 두 번이나 세게 된다. 그러니까 처음 상태에서 룰렛을 계속 돌리면 다시 처음 상태로 돌아올 텐데, 이 돌아온 상태까지 센다는 말이다. /* 속타는 저녁 메뉴 */ #include #include #include #include..
BOJ(백준) 2252 줄 세우기 https://www.acmicpc.net/problem/2252 parent 배열을 통해서 어떤 애가 트리의 꼭대기인지 파악한다. 즉, 두 번째 for문에서 parent[i] == false를 체크하는데 이 조건문을 통과하는 녀석은 제일 뒤에 있는 학생이다. 세 번째 for문은 어떤 트리에도 속하지 않으니까 위치 조건이 없는 학생을 출력한다. print(int point) 함수는 매개변수로 들어온 point가 제일 뒤에 있는 학생이므로 이 학생의 앞에 오도록 지정된 학생을 방문하면서 출력한다. 몇 번 그려서 하면 바로 파악될듯 /* 줄 세우기 */ #include #include #define MAX_STUDENT 32000 + 1 #define MAX_COMP 100000 + 1 using names..
백준(boj) 1030번 프랙탈 평면 https://www.acmicpc.net/problem/1030 문제를 어떻게 풀 지 구상하는데 시간을 많이 투자했다. 처음부터 배열을 크게 잡는 건 메모리가 터지기 때문에 시도하지 않았고 recursive하게 함수를 돌리면서 각 칸의 색깔을 판정했다. 말로하는 것보다 코드를 보는게 이해가 빠를 듯하다. /* 프렉탈 평면 */ #include #include #define WHITE 0 #define BLACK 1 using namespace std; int Time, N, K, R1, R2, C1, C2, Biggest; int getColor(int r, int c); bool is_middle(int r, int c, int); int main(void) { ios_base::sync_with_s..

티스토리툴바