유자의 코딩모험

10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 문제풀이 처음 시도했을 때는 모래성을 모두 queue에 넣고 8방향을 모두 살펴 무너지는지 확인 후 무너지지 않는 모래성을 queue에 다시 넣어줬다. 결과는 시간초과.. 더보기 #include #include #define MAX 1001 using namespace std; int h, w; int map[MAX][MAX]; bool visited[MAX][MAX]; int dx[] = { -1, 1, 0, 0, -1, -1, 1,..

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제풀이 용액들의 특성값이 주어졌을 때 세 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다. 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하다. 세 용액들을 더하면 오버플로우가 날 수 있기 때문에 배열은 long long 자료형으로 선언해준다. 3SUM - Wikipedia Unsolved problem in computer science: Is there an algorithm to sol..

2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제풀이 BOJ 2470 두 용액이랑 같은 코드로 풀 수 있다. [BOJ 2470] 두 용액 C++ 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000 woojeenow.tistory.com C++ 코드

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제풀이 용액들의 특성값이 주어졌을 때 두 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다. 투 포인터 알고리즘으로 left는 첫번째 인덱스부터, right는 마지막 인덱스부터 탐색해나간다. diff는 특성값과 0의 차, minx와 miny는 두 용액의 인덱스 정보이다. 두 용액의 합이 diff보다 작은 경우 정보를 갱신해준다. 두 용액의 합이 0이라면 특성값이 0에 가장 가까운 용액을 찾은 것이므로 탐색을 ..

14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 문제풀이 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값을 찾는 문제다. 투 포인터 알고리즘으로 left는 첫 번째 인덱스부터, right는 마지막 인덱스부터 탐색해나간다. 최대 특성값은 200,000,000이므로 answer는 200,000,000으로 초기화해준다. 탐색을 하면서 answer보다 0에 가까운 특성값을 찾으면 갱신해준다. sum이 0보다 작으면 a[left] 값이 더 커져야 하므로 left++, sum이 ..

4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제풀이 문자열을 3등분해서 가운데 문자열에 해당하는 부분은 공백으로 바꾼다. end - start가 1이 되면 종료해주면 된다. C++ 코드

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 문제풀이 처음에 문제를 읽고 어떻게 해야될지 한참 생각해도 잘 모르겠어서 다른 블로그 글을 참고했다. [백준 4256] 트리 예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 baelanche.tistory.com 위 트리를 살펴보자. 전위 순회 : 3 6 5 4 8 7 1 2..

2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 동꿀오소리님 풀이 참고 [백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리 문제 donggoolosori.github.io 문제풀이 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제이다. 위 트리의 인오더, 포스트오더, 프리오더를 살펴보자. 중위 순회 : 5 6 8 4 3 1 2 7 후위 순회 : 5 8 4 6 2 1 7 3 전위 순회 : 3 6 5 4 8 7 1 2 굵게 표시해놓은 것이 루트 노드이다. 후위 순회는 [왼쪽 ..