문제https://www.acmicpc.net/problem/10799 여담3개월 전쯤에 풀이를 참고하지 않고 풀었던 문제인데 이번에는 예전의 내 코드를 보고 풀었다... 나름 실력이 늘었다고 생각했는데 전에 풀었던 문제도 못 푸는 것 보면 그렇지 않은가 보다. 대체 코테 실력은 언제 늘까..? 너무 슬프다 풀이이 문제는 현재 문자가 (인 경우와 )인 경우를 나눈 뒤, 스택을 이용해서 문제를 풀면 된다. 현재 문자가 (라면 다음 문자를 통해 현재 문자가 쇠막대기의 오른쪽을 뜻하는지, 레이저를 뜻하는지 판별해야 한다.만약 다음 문자가 )라면 레이저를 뜻하므로 잘린 쇠막대기가 생기게 된다. 따라서 현재 잘린 쇠막대기의 수, 즉 스택에 담긴 수만큼 total에 더하면 된다. 다음 문자가 (라면 쇠막대기의 오른..

문제https://www.acmicpc.net/problem/2457 여담정렬 방식과 대략적인 풀이 흐름은 알겠는데 어떻게 구현해야 할지 모르겠어서 결국 풀이를 참고했다. 여러 번 풀이를 보고 나서야 이해할 수 있었다. 역시 그리디는 너무 어렵다... 다시 또 풀어봐야지 그리고 월/일이 주어지는 경우, MMDD 형식과 같이 4자리 숫자 그대로 바로 저장하는 것이 더욱 편리하다는 것을 알게 되었다. 24.06.11다시 풀어봤는데도 어렵다.. 정렬의 순서까지는 생각해 냈는데, 가장 오랫동안 꽃이 피어있어야 하는 것을 어떻게 구현할지 몰라서 결국 또 풀이를 참고했다..ㅎ 나중에 다시 또 풀어봐야겠다😢 풀이이 문제는 그리디 알고리즘으로 풀면 된다. 우선 입력이 MMDD 형식으로 주어지고 날짜를 비교해야 할 일..

문제https://www.acmicpc.net/problem/2170 여담이 문제는 강의실 배정 문제와 비슷하다고 느꼈다. 그래서 그때 풀었던 방식을 기반으로 생각해서 풀었더니 한 번에 맞았다! 정답률이 조금 높을 걸 보니 어려운 문제는 아닌 것 같지만 그래도 조금 뿌듯했다. 그치만 다른 풀이를 참고했더니 굳이 연결된 선의 정보를 저장하지 않아도 된다는 것을 알게 되었다. 풀이를 보면 아 그러네..! 라는 생각이 들지만 왜 막상 풀 때는 생각나지 않을까😂 풀이문제의 핵심은 이미 선이 그려진 위치에 다시 선을 그을 수 있다는 점이다. 즉, 이미 그어진 선과 연결해서 새로운 선을 그을 수 있으므로 이미 그은 선과 현재 그을 선이 겹치는지 판별하는 것이 중요하다. 이미 그은 선과 현재 그을 선이 겹치는 경우..

문제https://www.acmicpc.net/problem/1744 여담어떤 멋진분이 질문 게시판에 반례 모음을 정리해 주셔서 덕분에 놓친 부분을 빠르게 찾아 고칠 수 있었다..! 나름 여러 반례들을 넣어봤다고 생각했는데,, 역시 아직 부족하다는 것을 느꼈다. 문제를 제출하기 전에 꼭 여러 반례들을 생각해보는 습관을 가지자! 풀이이 문제는 수열의 각 수를 적절히 묶어서 그 합이 최대가 되도록 만드는 것이다. (수의 범위: -1000 ~ 1000) 따라서 음수는 음수끼리, 양수는 양수끼리 곱해야지 합을 최대로 만들 수 있다. 음수와 양수를 따로 저장해서 음수가 저장된 배열은 오름차순으로, 양수가 저장된 배열은 내림차순으로 정렬한다. (작성자는 편의상 우선순위 큐를 사용했다.) 이때, 주의해야 할 점이 있..

문제https://www.acmicpc.net/problem/11501 여담SWEA에서 풀었던 백만 장자 프로젝트랑 거의 같은 문제인 것 같다. 그치만 기억하는 풀이 방법이 확실하지 않아서 풀이를 참고했다..ㅎ 요즘 들어 느끼는데 안 좋은 습관이 있는 것 같다. 이미 풀었던 문제는 풀이를 약간 기억하고 있는 경우가 많아서 그 기억을 기반으로 문제를 풀려고 한다. 또 "이미 풀었던 문제인데도 못 풀어..??" 라는 생각 때문에 비교적 빨리 풀이를 보고 문제를 푸는 것 같다. 이미 풀었던 문제라도 그 풀이를 도출하는 과정이 중요한 것이니까 제발 기억을 기반으로 풀지 말고 생각을 하고 풀자! ps. 그리디는 진짜 어려운 것 같다. 많이 풀어보고 이미 풀었던 문제도 다시 풀어보는 것이 정답인 듯..  풀이주식을..

문제https://www.acmicpc.net/problem/5430 여담예전에 문제를 풀 때는 뒤집는 함수가 나올 때마다 배열을 뒤집어서 시간 초과가 발생했었다. 그래서 투 표인터를 사용해서 뒤집는 것을 표현했다. 근데 덱을 사용해서도 풀 수 있다는 것을 알았다.. 덱을 사용하니까 오히려 더 쉽게 풀 수 있는 듯! 양방향으로 수를 빼내는 문제가 나올 때는 일단 덱을 생각하는 습관을 가져야 될 듯하다.양방향이 나온다? 일단 덱 생각하기! 풀이함수에는 R(뒤집기)와 D(첫 번째 수 빼기)가 있다. 만약 수행할 함수가 모두 R이라면, 최종 결과는 입력 결과 그대로이거나 뒤집힌 결과일 것이다. 즉, R 함수일 때마다 배열을 직접 뒤집는 것은 비효율적이다. 이렇게 풀면 시간 초과를 만날 수 있다. 시간 초과가 ..

문제https://www.acmicpc.net/problem/1021 여담덱을 사용해서 풀어야 하는 것은 알았지만, 원소의 위치를 얻는 메서드가 없어서 당황했다. 풀이를 참고했더니 LinkedList를 사용해서 구현할 수 있다는 것을 알게 되었다..ㅎㅎ 부족한 기본기가 발목을 잡네.. ^^ 앞으로 원소의 위치를 얻으려면 ArrayList나 LinkedList의 indexOf() 메서드를 사용하자!  풀이왼쪽과 오른쪽으로 원소를 이동시키기 때문에 덱을 사용해서 문제를 풀면 된다. (양방향 순환 큐 == 덱) 2번, 3번 연산의 최솟값을 구하기 위해 뽑아내려고 하는 원소가 왼쪽에 가까운지 오른쪽에 가까운지를 판별해야 한다. 만약 뽑아내려고 하는 원소가 중간보다 앞에 위치한다면 2번 연산을 수행하고, 뒤에 위..

문제https://www.acmicpc.net/problem/17298 여담탑 문제랑 옥상 정원 문제랑 거의 비슷한 유형이다. 그래서 이전에 풀었던 방식으로 쉽게 풀 수 있었다. 그런데 이미 관련 문제들을 풀어보고 문제 유형을 알기 때문에 바로 풀 수 있었다고 생각한다. 나중에 유형에 대한 힌트 없이 다시 풀어볼 필요가 있겠다! 풀이오큰수는 현재 원소의 오른쪽에 있으면서 현재 원소보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 즉, 현재 원소보다 크고 오른쪽에 위치하는 수 중에서 제일 첫 번째로 등장하는 수를 뜻한다. 따라서 가장 오른쪽에 위치하는 원소부터 스택에 넣어서 검사하는 방식으로 수행하면 시간 초과없이 풀 수 있다. 아래의 과정을 각 원소마다 반복해서 수행하면 된다. 스택이 비어있는 경우-..

문제https://www.acmicpc.net/problem/6198 여담탑 문제와 거의 유사해서 그 문제를 풀 때 배웠던 아이디어를 사용해서 풀었다. 조금 다른 부분이 있었지만 잘 생각해 보면 풀 수 있는 문제라 한 번에 풀 수 있었던 것 같다. 역시 많이 풀어보는 것이 중요한 듯! 풀이이 문제도 N이 최대 80,000개라 이중 반복문을 사용하면 시간 초과가 발생한다. 따라서 스택을 사용해서 시간 초과가 발생하지 않도록 풀이하면 된다.  따라서 아래의 과정을 각 빌딩마다 반복해서 수행하면 된다. 스택이 비어있는 경우현재 빌딩을 스택에 push하기스택이 비어있지 않는 경우스택에 peek한 빌딩의 높이 peek한 빌딩을 pop하고, 확인한 빌딩의 수 더하기스택에 peek한 빌딩의 높이 > 현재 빌딩의 높이..

문제https://www.acmicpc.net/problem/2493 여담처음에 시간 복잡도가 O(N²)이 되는 방식으로 풀었다. N이 최대 500,000개 주어지기 때문에 무조건 시간 초과가 발생할 것이라는 생각을 했지만, 떠오르는 방법이 이것뿐이라 어쩔 수 없었다.. 결국 풀이를 참고했는데 스택을 이용해서 이렇게 풀 수 있다는 것을 알게 되었다. 역시 문제를 많이 접해봐야 사고가 확장되는 것 같다. 풀이이 문제는 스택을 사용하면 시간 초과없이 쉽게 풀이할 수 있다. 아래의 과정을 각 탑마다 반복해서 풀이하면 된다. 스택이 비어있는 경우0을 기록하고, 현재 탑을 스택에 push하기스택이 비어있지 않는 경우스택에 peek한 탑의 높이 > 현재 탑의 높이peek한 탑의 번호를 기록하고, 현재 탑을 스택에 ..