Algorithm/자료구조

문제https://www.acmicpc.net/problem/9375 여담모든 조합을 계산하는 방법에 대해 계속 고민하다가 풀이를 참고했다. 복잡하게만 생각했었는데 풀이를 보고 이렇게 간단하게 계산할 수 있구나..? 하고 놀랐다.. 이럴 때마다 머리의 한계를 느껴.. 생각한 방법이 아닌 것 같으면 시야를 넓혀보는 습관을 가지자 제발! 풀이문제에 따르면, 같은 종류끼리는 입을 수 없다. 따라서 우선 종류별로 옷의 개수를 센다.headgear - 2개 (hat, turban)eyewear - 1개 (sunglasses) 그 후, 입을 수 있는 모든 방법의 수를 구해야 한다. 따라서 한 종류만 입는 경우, 두 종류만 입는 경우, ..., N 종류를 입는 경우와 같이 모든 경우를 계산해야 한다. 한 종류만 입는..

문제https://www.acmicpc.net/problem/2504 여담덧셈과 곱셈을 어떻게 나눠서 계산할지 몰라서 결국 풀이를 참고했다. 처음에는 이해가 안 돼서 계속 써보다가 분배법칙을 이용하면 된다는 말을 보고 이해했다.. 다시 풀 때도 풀이 로직을 알아서 쉽게 풀었지, 몰랐다면 끝까지 못 풀었을 것 같다. 다들 어떻게 이런 생각을 하는 걸까? 진짜 대단하다. 나도 분발해야지.. 풀이이 문제는 괄호를 기반으로 값을 구하는 것이기 때문에 스택을 이용해서 문제를 풀면 된다. 풀이 과정은 다음과 같으며, 자세한 내용은 코드를 참고하면 된다. 수학의 분배법칙을 생각하면 풀이 흐름을 쉽게 이해할 수 있을 것이다. (2 × (2 + 3 × 3) = (2 × 2) + (2 × 3 × 3)) ( 또는 [를 만나..

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

문제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한 탑의 번호를 기록하고, 현재 탑을 스택에 ..

문제https://www.acmicpc.net/problem/5397 여담이 문제는 에디터 문제랑 거의 유사하다. 에디터 문제를 통해 ListIterator를 다루는 방법을 배웠기 때문에 수월하게 풀 수 있었다!  풀이에디터 문제와 마찬가지로 LinkedList를 ListIterator를 사용해서 풀이하면 된다.  입력한 문자열은 명령어와 문자가 섞인 채로 주어진다. 따라서 각 문자를 하나씩 확인하면서 문자라면 iterator에 저장하고, 명령어라면 그에 맞는 명령을 수행하면 된다. 우선 LinkedList 객체에 listIterator() 메소드를 사용해서 ListIterator 객체를 생성한다. 그 후, 각 문자에 따라 다음의 과정을 반복한다.- 인 경우 (백스페이스)이전 문자가 존재하는 경우: it..

문제https://www.acmicpc.net/problem/1406 여담처음에 LinkedList를 사용해서 풀었더니 시간 초과가 발생했다. 아마 LinkedList에서 원하는 위치를 찾아가는 시간이 O(N)이라 그런 것 같다. 풀이를 참고하니 ListIterator라는 인터페이스를 사용해서 LinkedList를 편리하게 탐색할 수 있다는 것을 알게 되었다. LinkedList와 ListIterator에 대해 공부하고 정리해야 되겠다..! 풀이LinkedList와 ListIterator를 사용해서 풀이하면 된다. 이 문제는 ListIterator의 사용법을 익히는 문제라고 볼 수 있다. 따라서 ListIterator의 메소드를 조건에 맞게 적절하게 사용하면 된다.  우선 입력받은 문자열을 LinkedL..