꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2250 중위 순회(Inorder Traversal) DFS(Depth First Search) 알고리즘을 적용하여 푸는 문제였습니다.알고리즘은 아래와 같습니다.1. 트리를 입력 받을 때 pair형 배열에 인덱스를 부모로 하고 자식들을 입력받습니다. 부모가 항상 1이 아니기 때문에 입력받는 노드를 세서 한번만 입력되는 노드를 루트로 정합니다.2. 중위 순회 DFS를 실행합니다. 이 때, 해당 높이에서 제일 좌측에 있는 노드와 제일 우측에 있는 노드를 업데이트합니다.3. 각 레벨을 탐색하면서 제일 긴 길이를 구하고 해당 높이와 길이를 출력합니다. 주의할 점은, 1번에서도 언급했듯이 1번 노드가 항상 루트가 아니라는 점입니다! #in..

문제 링크입니다: https://www.acmicpc.net/problem/3653 난이도가 높은 세그먼트 트리 응용 문제였습니다.많은 사람들이 펜윅 트리로 풀었지만 세그먼트 트리 알고리즘으로는 풀리지만 펜윅 트리 알고리즘으로는 풀리지 않는 문제들이 존재하기 때문에 세그먼트 트리 알고리즘을 이용하여 풀었습니다. 알고리즘과 코드는 lyzqm(https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html?showComment=1531981580261#c7391195554365601508)님의 블로그를 참고하여 풀었습니다.기본적인 알고리즘은 아래와 같습니다.1. 배열을 M + N 크기로 설정하고 (M ~ N - 1)까지 1로 표시하고 (0 ~ M - 1)까지는 0으로 ..

문제 링크입니다: https://www.acmicpc.net/problem/1600 문제 자체는 쉽지만 코딩할 때 실수하기 딱 좋은 BFS(Breadth First Search) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 능력이 있을 경우에는 knight처럼 움직이고 해당 위치를 큐에 집어넣고, 능력이 없을 때처럼 움직이는 경우도 큐에 집어넣습니다.-> 이 때, visited 함수를 좌표와 능력 사용 횟수를 이용해 표시하는 것이 핵심입니다! 즉, 같은 좌표라도 능력 사용 횟수가 다르면 visited 함수는 표시가 되어있지 않습니다.2. 도착지점에 도달할 경우 움직인 횟수를 반환합니다. #include #include #include using namespace std; const int MA..

문제 링크입니다: https://www.acmicpc.net/problem/1939 BFS(Breadth First Search) 알고리즘과 이진 탐색(Binary Search)를 같이 사용해야 풀 수 있는 문제였습니다.문제가 조금 난해한데 결국 시작섬에서 도착섬까지 운반할 수 있는 최대 중량을 구하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 공장1과 공장2 그리고 중량 제한을 양방향으로 입력받습니다. 이 때, 이진 탐색을 위해 최대 중량 제한을 업데이트합니다.2. 여태까지 입력 받은 중량 제한 중 하나가 답이므로 low = 0, high = 최대 중량 으로 초기화하여 이진탐색을 합니다. 중량제한이 mid일 때 BFS 함수를 호출해서 시작섬에서 도착섬까지 운반 가능하면 low를 업데이트하고 운반할 ..

문제 링크입니다: https://www.acmicpc.net/problem/9205 문제 덕분에 '맨해튼 거리'라는 개념을 처음 알게 되었습니다.맨해튼 거리는 두 좌표 사이의 거리를 'x 좌표간의 거리' + 'y 좌표간의 거리'로 표현합니다.(https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC) 알고리즘은 아래와 같습니다.1. 좌표를 입력 받을 때 출발점, 편의점들, 그리고 도착점의 좌표를 pair형 배열에 입력받습니다.2. 편의점을 방문할 때마다 맥주 20병씩 가지고 다닐 수 있기 때문에 모든 좌표들을 비교하며 맨해튼 거리로 50 * 20 즉, 1000 이내에 있는 좌표들의 인덱스를 양방향 그래프에 추가합니다.3. 출..

문제 링크입니다: https://www.acmicpc.net/problem/2718 백준 2133번 타일 채우기(http://jaimemin.tistory.com/330)는 높이가 3인 직사각형이였는데 이번 문제는 높이가 4인 직사각형에 타일을 채우는 문제였습니다.이런 문제는 직접 경우의 수를 그려봐야 경우의 수를 구할 수 있고, 한칸 전 즉, width - 1에서 타일을 채운 방법을 알아야지 경우의 수를 구할 수 있습니다.주석에도 각 경우의 그림을 표현하였고 자세한 설명은 http://joonas-yoon.blogspot.com/2016/03/2718.html을 참고하시면 될 것 같습니다! #include #include //memsetusing namespace std; const int MAX = ..

문제 링크입니다: https://www.acmicpc.net/problem/7578 유형은 다르지만 백준 6549번 히스토그램에서 가장 큰 직사각형(http://jaimemin.tistory.com/705)처럼 세그멘트 트리를 응용해서 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. A열에 위치한 기계를 입력받은 뒤 B 배열에는 입력받은 기계 번호를 index, 인덱스를 value로 저장합니다.-> STL map을 이용할 경우 TLE 발생2. A열에서 순차적으로 교차하는 케이블 쌍의 개수를 구하는데 이는 1 ~ B[A[i]]까지 누적합을 구하면 됩니다.3. 2번 과정이 끝나면 해당 B[A[i]]를 1로 표시하고 누적합을 업데이트합니다.4. A열의 모든 기계에 대해 2, 3번 과정을 반복합니다. #in..

문제 링크입니다: https://www.acmicpc.net/problem/6549 지금까지 푼 세그먼트 트리 문제들은 간단한 구현 문제였지만 이번 문제는 응용을 해야하는 문제였습니다.오랜 시간 고민 끝에도 접근 방법을 모르겠어서 Crocus님 포스팅(http://www.crocus.co.kr/707)을 참고했습니다. 접근 방법은 아래와 같습니다.1. 세그먼트 트리를 초기화할 때 해당 구간 내 가장 낮은 막대의 인덱스를 저장합니다.2. query 함수를 통해 구간 내 제일 낮은 막대의 높이를 구합니다.3. getMaxArea 함수를 통해 해당 구간 내 최대 넓이를 구합니다.i) query를 통해 구간 내 최소 높이를 갖는 막대의 인덱스를 구합니다.ii) 해당 인덱스의 왼쪽에 막대가 존재할 경우 왼쪽 구간..

문제 링크입니다: https://www.acmicpc.net/problem/14867 BFS(Breadth First Search) 알고리즘을 적용하여 푸는 간단한 문제였지만 물통에 들어갈 수 있는 최대 양이 100,000이기 때문에 이차원 배열을 통해 visited를 표현할 수 없습니다.따라서, map을 이용해서 visited를 표현하는데 처음 두 정보는 A와 B 물통에 들어있는 물의 양, 그리고 마지막 정보에는 현재단계까지 도달하는데 걸린 횟수를 저장하면 쉽게 풀 수 있습니다.처음에는 조건부 연산자를 이용하여 M 단계에서 물을 이동한 후 newA와 newB를 저장했는데 시간초과가 발생했습니다.따라서, if else문을 통해 newA와 newB를 저장하였더니 AC를 받은 것으로 보아 조건부 연산자를 사..

문제 링크입니다: https://www.acmicpc.net/problem/1051 간단한 브루트 포스(Brute Force) 문제였습니다.주의할 점은, 길이가 1인 정사각형이 최소이므로 초기 result = 1로 초기화해줘야한다는 점입니다! #include #include #include using namespace std; const int MAX = 50; int N, M; int arr[MAX][MAX]; int maxSquare(void) { int result = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (int k = 1; k < min(N, M); k++) { //범위 내에 있고 각 꼭지점들이 같은 숫자라면 if..