분류 전체보기 292

[백준 BOJ] 1919 애너그램 만들기

1919_애너그램 만들기 링크 https://www.acmicpc.net/problem/1919 풀이 애너그램은 철자를 굉장히 중요하게 생각합니다. 그렇기 때문에 영단어를 철자로 나누어 기록합니다. 그 후, 소문자만 들어오기 때문에 a~z까지 서로 얼마나 차이나나 구하면 제거해야 하는 최소 개수의 문자 수가 나옵니다. 차이를 구하는 방법은 max에서 min을 빼면 됩니다. 코드

PS/BOJ 2018.11.19

[백준 BOJ][stack] 3015 오아시스 재결합

3015_오아시스 재결합 링크 https://www.acmicpc.net/problem/3015 풀이 우선 스택을 사용해서 사람들을 내림차순으로 나열하고(같은 수도 포함), 이전보다 더 큰 수가 들어오면 스택을 지워나가며 ans를 구합니다. 다 끝나고 스택에 남아있는 내림차순 사람들을 지워나가며(1명 남기고) ans에 더해줍니다. 지울 때가 중요한데요. 내림차순 도중 더 큰 게 들어오면 이렇게 지워질 때 자신의 양쪽을 볼 수 있으니 ans에 2씩 더해주면 됩니다. 하지만 자신이 맨 왼쪽이었다면 왼쪽을 볼 수 없으니 ans에 1을 더해주면 됩니다. 그리고 같을 때가 문제인데요. 같은 키를 가진 사람들끼리 볼 수 있는 인원 + 같은 키를 가진 사람들이 볼 수 있는 왼쪽 오른쪽 사람을 더해주면 됩니다. 가운데..

PS/BOJ 2018.11.18

[백준 BOJ][stack] 6549 히스토그램에서 가장 큰 직사각형

6549_히스토그램에서 가장 큰 직사각형 링크 https://www.acmicpc.net/problem/6549 풀이 이 문제는 스택을 이용해서 풀 수 있는 문제입니다. 각 칸에서 왼쪽과 오른쪽으로 각각 어느 칸까지 뻗어 나갈 수 있는지 구하고, 그 길이 * 높이를 곱해서 가장 큰 크기를 선택하면 답이 나오고, 시간 복잡도는 3n, O(n)이 됩니다. 왼쪽으로 뻗어 나갈 수 있는 정도를 구하는 방법은 0번지부터 n-1번지까지 스택에 오름차순 정렬을 하는 것인데요. 높이가 같을 때도 스택에서 pop 해줘야 합니다. 그렇게 되면 스택 안에 있는 번지들은 i번째(현재 고려하는 칸)에서 왼쪽으로 뻗어 나갔을 때, 만나게 되는 장애물들을 나타내게 됩니다. i번째의 높이가 스택의 top번째의 높이보다 높다면 왼쪽으..

PS/BOJ 2018.11.17

[백준 BOJ][stack] 2493 탑

2493_탑 링크 https://www.acmicpc.net/problem/2493 풀이 각 레이저가 왼쪽으로 얼마나 뻗을 수 있는지 체크하기 위해서 스택을 사용해 풀 수 있습니다. 이 문제에서는 내림차순 스택을 사용하면 되는데요. 시작을 1번지라고 두고 1번지부터 n번지까지 스택에 내림차순을 유지하면서 집어넣는 것입니다. 스택 내부의 번지들은 현재 i번째 탑이 발사한 레이저 신호를 수신할 가능성이 있는 탑을 의미합니다. i번째 탑의 높이가 바로 스택의 top번째 탑의 높이보다 작거나 같다면 발사한 레이저는 바로 왼쪽 탑이 수신할 것이므로 left[i]는 top이 됩니다. 그리고 이제 i번째 탑이 수신할 가능성이 제일 높으니 i를 push합니다. i번째 탑의 높이가 스택의 top번째 탑의 높이보다 크다면..

PS/BOJ 2018.11.16

[백준 BOJ] 16204 카드 뽑기

16204_카드 뽑기 링크 https://www.acmicpc.net/problem/16204 풀이 O가 적혀 있는 카드가 M개, 내가 O를 적은 카드가 K개라고 한다면, K가 M보다 많을 때 M개 맞힐 수 있고, 그렇지 않을 때는 K개 맞힐 수 있습니다. 따라서 min(K, M)이죠. 그리고 X가 적혀 있는 카드가 N-M개, 내가 X를 적은 카드가 N-K개일 테니 마찬가지로 min(N-M, N-K)입니다. 둘을 더해주면 답이 됩니다. 코드

PS/BOJ 2018.11.15

[백준 BOJ] 1629 곱셈

1629_곱셈 링크 https://www.acmicpc.net/problem/1629 풀이 b가 21억까지기 때문에 곱하고 나머지 구하기를 반복하다 보면 시간을 초과하게 됩니다. 그래서 지수법칙을 이용하기로 했습니다. 제곱한 걸 다시 제곱하면 네 제곱이 되고 또 제곱하면 여덟 제곱이 되는 것을 이용하는 것입니다. 아홉 제곱을 구하기 위해서는 첫 번째 수 a를 다시 곱하면 됩니다. 이렇게 제곱과 첫 번째 수를 곱함으로써 b 제곱을 만들면 됩니다. 하지만 그 방법은 다운탑이므로 탑다운으로 과정을 구하고 난 후 쌓아 올려줍니다. 이런 방식으로 코드를 짜면 log2n으로 구할 수 있겠네요. 코드

PS/BOJ 2018.11.11
반응형