목록브루트포스 (55)

1일1알

백준 14225번 부분수열의 합 C++

수열의 크기는 최대 20이고, 수열을 이루는 각 수가 최대 100000이기 때문에 나올 수 있는 최대의 수는 2000000이다. 2000000개의 크기를 갖는 배열을 만들어서 재귀함수를 통해 나온 수들의 합을 저장하고, 배열을 1부터 탐색하면서 만약 저장되지 않은 수를 찾는다면 탐색을 멈추고 탐색이 멈춘 부분을 출력하는 방식으로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector v; bool ans[2000001] = { false }; v..
알고리즘 2021. 11. 16. 12:32
백준 1254번 팰린드롬 만들기 C++

최소한의 알파벳으로 팰린드롬을 만드는 문제이다. (앞에서부터 읽는 것과 뒤에서부터 읽는 것이 같은 문자열) 주어진 문자열을 탐색하는데, 시작 지점을 1씩 늘려가면서 만약 팰린드롬이라면 문자열의 길이에 시작 지점을 더해서 문제를 해결하였다. 그림으로 그려보면 그림을 좀 못 그린 것 같긴 한데 설명을 해보자면, 처음 a와 e는 같지 않으므로 팰린드롬이 될 가능성이 없다. 그래서 시작 지점을 1 늘려준다. 그때 b와 e도 같지 않으므로 또 늘려준다. 이렇게 진행하다가 3번 인덱스 e에 도착했을 때 마지막 e와 같으므로 팰린드롬일 가능성이 있기 때문에 계속 검사를 해준다. 검사를 마쳤을 때 팰린드롬이 맞았기 때문에 문자열의 길이 8과 검사를 시작했던 인덱스 3을 더하면 11이 된다. ( abcefgfe + cb..
알고리즘 2021. 11. 14. 12:24
백준 2961번 도영이가 만든 맛있는 음식 C++

n개의 재료가 있는데, 각 재료에는 신맛과 쓴맛이 수치로 존재한다. 1개 이상의 재료를 사용해서 음식을 만드는데, 신맛과 쓴맛의 차이의 최솟값을 구하는 문제이다. 신맛은 재료들의 각각의 신맛의 수치를 곱한 값이 되고, 단맛은 재료들의 단맛을 더한 값이 된다. 처음에 문제를 분석할 때 신맛이 나는 재료와 단맛이 나는 재료가 분리되어 있다고 착각해서 조금 헤맸다. 문제를 다시 읽어보니 하나의 재료에 단맛과 신맛이 같이 있다는 것을 깨달았다. 그러고 나니 문제를 해결하는 방법이 쉽게 떠올랐다. 각각의 재료들의 신맛, 단맛 정보를 pair로 저장해서 벡터에 하나씩 삽입하고 벡터를 재귀적으로 돌면서 신맛과 단맛의 최솟값을 탐색하였다. 신맛이든 단맛이든 1, 2, 3이나 2, 3, 1이나 같은 값이 나오기 때문에 ..
알고리즘 2021. 11. 13. 13:44
백준 2589번 보물섬 C++

BST 탐색으로 해결할 수 있는 문제이다. 지도의 모든 부분을 검사하면서 만약 L인 지역이면 그곳부터 BST탐색을 시작하고, 가장 먼 곳 까지의 거리를 구하고 구한 거리들 중 가장 큰 값을 찾으면 해결할 수 있다. 땅을 방문했는지 안했는지 검사하는 visited 벡터를 만들었고, 새로 검사를 시작할 때는 visited 벡터를 초기화 해주었다. 그리고 BST탐색을 하기 위한 큐에는 pair을 사용해서 안쪽에 있는 pair는 좌표 정보를, int는 거리 정보를 저장하면서 탐색을 하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using na..
알고리즘 2021. 11. 11. 12:30
백준 2502번 떡 먹는 호랑이 C++

조금 특이한? dp 문제이다. 우선 점화식을 세울 때 생각한 것은 어떤 날이든 첫째 날과 둘째 날의 떡의 개수로 분해할 수 있다는 것이다. 예를 들어 5번째 날은 3번째 날 + 4번째 날이고, 3번째 날은 1번째 날 + 2번째 날, 4번째 날은 2번째 날 + 3번째 날.. 이런 식으로 밑으로 내려가면서 최종적으론 1번째 날과 2번째 날의 떡의 개수의 조합으로 나타낼 수 있다. 그림으로 나타내면 이런 식으로, 5번째 날은 최종적으로 2 * 1번째 날, 3* 2번째 날의 떡의 개수로 나타낼 수 있다. 하지만 숫자가 주어질 때마다 이런 식으로 계속 분해하면 시간이 오래 걸리기 때문에 bottom-up 방식으로 해결하기로 생각했다. pair을 이용하여 dp배열을 만들었는데, 첫 번째 원소는 첫 번째 날 떡의 개..
알고리즘 2021. 11. 5. 12:21
백준 2468번 안전 영역 C++

bfs로 해결할 수 있는 문제이다. 입력을 받은 영역 중에 가장 높은 영역을 max_height 이라고 저장한 뒤, 비가 안오는 경우부터 비가 max_height까지 오는 경우를 모두 검사해서 안전 영역이 제일 많은 경우를 찾았다. 각 지역에 홍수가 났는지를 알려주는 isFlood 2차원 벡터를 만들고 비의 높이에 따라 Init 함수를 통해 isFlood를 초기화 해주었다. 그리고 탐색할 때 visited 배열을 따로 만들기 번거로워서 방문한 안전 영역을 홍수가 난 곳으로 바꿔주면서 탐색을 하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace s..
알고리즘 2021. 10. 26. 11:59
이전 Prev 1 ··· 6 7 8 9 10 Next 다음