본문 바로가기

Algorithm292

[백준/C++] 오큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 i번째 숫자의 오른쪽에 있는 수 중에서 가장 왼쪽에 있는 수를 찾으면 되는 문제다. 즉, i번째 수가 오면 그 수를 기준으로 오른쪽에 큰수가 나오는지 탐색을 하면 되는 문제다. 여기서 문제를 풀 때, 만약 i번째 수마다 오른쪽을 탐색하면 O(n^2)의 시간복잡도가 걸리게 된다. 대신 빠르게 푸는 방법이 있다. 아래 그림과 같이 3, 5, 2, 7의 4개의 숫자의 수열을 예로 들어보자. 처음에 3이라는 숫자가 들어오면 기록을 한다. 아직까지는 3의 왼쪽에 어떤 숫자가 오는지 모른다. 이후 들어오는 숫자는 5다. 여기서 5는 3보다 크기 때문에, 3은 자신보다 오른쪽에 있는 큰 수를 발견한다. 그러므로 3.. 2024. 4. 9.

[백준/C++] 문자열 폭발 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 문자열이 완성되면 삭제를 하고, 뒤에 문자들을 이어 붙이면 되는 문제다. 문제를 풀 때, 앞에서 부터 문자열을 추가해 나가다가 M의 마지막 문자가 나오면, 저장된 문자들을 탐색해 삭제가 되는지 확인했다. 아래 그림을 통해 자세하게 알아보자 M의 마지막 문자인 4가 나왔으므로 4부터 탐색해 문자열 M과 같은지 확인한다. C4로 같았으므로 문자열을 삭제해 준다. 마찬가지로 진행을 하면 아래와 같이 정답이 나오게 된다. 이렇게 하면 문자열을 앞에서부터 n번 탐색해 문제를 해결할 수 있다. 이때 문자를 저장하고 삭제를 하는 방법은 여러가지가 있겠지만, 뒤에 있는 문자부터 빼 사용할 것이므로 stack을 .. 2024. 4. 8.

[백준/C++] 앱 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 냅색 문제와 같이 풀었다. M의 크기를 갖는 배열을 만든 다음 i 만큼의 메모리를 cost를 주고 만들 수 있다면 새롭게 비용을 주고 특정 메모리를 만들 수 있는지 체크했다. 이렇게 풀면 통과는 되지만 10,000,000 * 100의 연산을 해야하기 때문에 비효율적 이었다. 다른 풀이가 있을까 찾던 중 메모리가 기준이 아니라 cost를 기준으로 하는 풀이가 있었다. DP[N][cost]을 만들고 여기에 메모리를 저장 하는 방법이다. 아래 그림을 따라 진행해보자 먼저 처음에 위 그림과 같이 초기화를 한다. 이후 첫번째 비용과 메모리를 이용해 Cost를 써서 얼마의 메모리를 만들 수 있는지.. 2024. 4. 7.

[백준/C++] 동전 1 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 k의 크기가 10000으로 제한되어 있기 때문에 쉽게 풀 수 있는 문제다. 동전의 가치가 전부 다르고 몇 개를 사용해도 되며, k원을 만드는 모든 경우의 수를 구해야 된다. for문으로 j원의 돈을 만들 수 있으면 j원에 coin을 더해 [j+coin]원을 만들 수 있다. 이때, coin을 여러개 사용할 수 있으므로 [j+coin*2], [j+coin*3] ... 도 만들 수 있다. coin에 숫자를 곱해 더하는 방법도 있겠지만, 좀 더 편한 방법이 있다. 예를 들어 2, 4의 동전이 주어지고 k가 10이라고 하자 그러면 2로 만들 수 있는 돈의 가치에 대한 경우의 수는 아래 그림과 같다. 그러면 2로.. 2024. 4. 6.

[프로그래머스/C++] 쿼드압축 후 개수 세기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정사각형 안에 있는 숫자가 전부 같지 않으면 사각형을 4개로 나눠서 탐색하면 되는 문제다. 먼저 정사각형의 모든 숫자가 같은지 탐색한다. 이때 전부 숫자가 같다면 그 숫자가 0일 경우 0의 개수를 1 증가시키고, 1의 개수를 1 증가시키면 된다. 만약 다르다면 4개로 쪼개서 다시 탐색하면 된다. (재귀적으로 탐색) 4개로 쪼갤 때, x와 y좌표의 시작점과 끝점을 이용해 절반으로 나눠서 사용하면 된다. ex) [x좌표 시작, x좌표 중간], [x좌표 중간+1, x좌표 끝] 으로 경우를 나눌 수 있다 (y도 마찬가지) [아이디어 정리] 정사각형안의 모든 수가 같은지 검사한다. 만약 모든 수가 같다면, .. 2024. 4. 6.

[프로그래머스/C++] [1차] 다트 게임 (2018 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 문자열 구분만 잘하면 쉽게 해결할 수 있는 문제다. 먼저 숫자가 나오면 연속된 숫자를 탐색해 획득한 다트 점수가 몇인지 계산한다. 이후 나오는 문자열이 S, D, T인지에 따라 점수를 몇 제곱할지 구현한다. 만약 *이 나온다면 현재 점수와 앞 점수를 2배 해야하므로, 몇 번째로 다트를 던졌는지 기록하는 index를 선언해 사용했다. 여기서 숫자를 입력 받는 방법은 아래와 같이 구현했다. 먼저 num에 -1을 저장한다. 그리고 문자열을 탐색을 시작한다. 이때, 문자열에 있는 문자가 숫자라면 num에 어떤 수가 저장되어있는지 확인한다. 만약 -1이라면 아무 숫자도 입력이 안됐으므로 num의 숫자를 이번에 .. 2024. 4. 5.

[백준/C++] 양팔저울 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다. (n은 추의 개수) 여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다. 1. 구슬 쪽에 추를 올리는 경우2. 추를 사용하지 않는 경우3. 구슬 반대편에 추를 올리는 경우 그렇기 때문에 시간 복잡도는 O(3^n)이다. 한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다. (중복해서 만들어지는 추의 무게가.. 2024. 4. 5.

[프로그래머스/C++] 후보키 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 후보키가 될 수 있는 키들을 선정하려면 어떻게 해야할까 고민을 많이 했다. 이미 후보키가 된 조합이 포함되어 있다면 후보키가 될 수 없으므로 이를 구현하면 되지 않을까? 고민을 했다. 처음에는 재귀 함수를 만들어 가지치기를 하려고 했는데 잘 안돼서 그냥 키 하나로 만들 수 있는 경우, 키 2개로 만들 수 있는 경우... 의 모든 조합을 구하고, 이미 적은 키로 만들어진 경우는 제외하도록 코드를 구현했다. 나중에 다시 생각해보니 키들의 조합을 만드는 부분을 재귀함수로 가지치기 할 수 있을 것 같아서 재귀함수로 문제를 다시 풀었다. 예를 들어 1번 키를 무조건 포함, 2번 키를 무조건 포함.. 2024. 4. 4.

[백준/C++] 힘세고 강한 아침 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 풀 때, query가 들어올 때마다 계산을 했다. 그랬더니 시간초과가 나서 반복되는 계산을 줄이도록 문제를 풀었다. N이 100이기 때문에 첫 언어, 중간 언어를 정해 특정 언어로 변환하는데 걸리는 최소 비용을 계산할 수 있기 때문이다. 이 경우 O(N^2 * 최소 비용을 계산하는 시간복잡도) 이므로 문제가 해결될 것이라고 생각했다. 처음에 최소 비용을 계산할 때, priority queue를 이용해 탐색하지 않은 언어 중 항상 변환 비용이 가장 낮은 언어가 앞에 오도록 코드를 구현했다. 문제는 priority queue에 삽입하는데 O(logn)의 시간복잡도가 걸리기 때문에 시간초과가 또 났다... 2024. 4. 3.

[프로그래머스/C++] 문자열의 아름다움 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀이를 잘 생각해 구현하면 되는 문제다. 단, 크기가 300000이기 때문에 O(n^2)의 시간복잡도로는 해결할 수 없다. 그러므로 누적합을 활용해 O(n)의 시간복잡도로 문제를 해결했다. "aabba" 와 같은 문자열이 있다고 생각하자 이제 문자를 크게 두개로 나눠서 생각을 한다. 1. 양 끝 문자가 다른 경우 이 경우는 항상 문자열의 크기만큼의 아름다움을 갖게 된다. 2. 양 끝 문자가 같은 경우 이 경우는 양 끝 문자를 사이에 가장 아름다움을 갖는 문자를 찾아야 한다. 이제 아래와 그림을 보자 첫 문자 a부터 왼쪽으로 탐색을 시작한다. 탐색을 하다가 현재 문자가 b인데, 이전 문자가 a가 됐다. .. 2024. 4. 2.

[프로그래머스/C++] 빛의 경로 사이클 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 시작점이 정해져 있는지 아니면 정말 말 그대로 특정 격자에서 출발할 수 있는 모든 사이클을 구해야하는지 의문이 들었다. 제한사항을 보니 시작점 등의 제한사항이 없기 때문에 말 그대로 모든 사이클을 구하면 되겠다고 생각하고 문제를 풀었다. 이 문제에서 핵심은 사이클이다. 만약 한 격자에서 왼쪽으로 이동하는 경로가 있다면, 이 경로가 포함된 사이클은 몇 개일까? 정답은 무조건 한 개다. 왜냐하면 격자에서 특정한 방향으로 이동하게 되면, 결국에는 돌고 돌아 같은 사이클을 나타내기 때문이다. 그래서 사이클을 표시하기 위해 2차원 배열에 4가지 방향으로 이동했음을 저장하는 visited 배열을 .. 2024. 4. 1.

[프로그래머스/C++] 3 x n 타일링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 경우만 잘 파악하면 쉽게 풀 수 있는 문제다. 가로 세로가 2*3 인 사각형에 2*3인 사각형을 더하면 4*3인 사각형을 만들 수 있다. 이를 이용하면 길이가 n인 사각형을 만들기 위해서는 [0*3인 사각형, n*3인 사각형] + [1*n인 사각형, (n-1)*3인 사각형] ... 을 전부 계산하면 된다. + 참고로 이 문제에서 길이가 홀수인 사각형은 만들 수 없다. 이를 이용하면 문제를 풀 수 있는데 그 전에 알고 넘어가야 되는 게 있다. 위 그림과 같이 길이가 6인 사각형은 [2*3인 사각형, 4*3인 사각형] 처럼 볼 수 있고, [4*3인 사각형, 2*3인 사각형] 으로도 볼 수 있다. 이 경우 .. 2024. 3. 31.

[프로그래머스/C++] 브라이언의 고민 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 많은 예외처리를 하느라 시간이 꽤 걸린 문제였다 반례도 많이 만들어 테스트를 했다... [문제 풀이] 이 문제에서 중요하게 봐야할 점들은 아래와 같다. 1. 광고 규칙은 2개가 있으며, 서로 다른 광고 규칙 2개는 같이 적용될 수 있다. 2. 하나의 광고규칙이 한 단어에 여러번 적용될 수는 없다. 3. 광고 규칙에 사용된 소문자는 다시 사용할 수 없다. 위 3가지 사항에 유의해서 문제를 풀어야 한다. 먼저 광고문구 sentence를 앞에서부터 탐색한다. 이때, 대문자가 나오면 tempString이라는 str에 더한다. 만약 소문자가 나오면 그 소문자가 sentence에 몇 개가 나오는지 센다. 여기서 소문자의 개수에.. 2024. 3. 30.

[프로그래머스/C++] 안티세포 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제를 처음 봤을 때 어떻게 풀지 많이 고민했다. 모든 경우를 계속해서 계산하기에는 너무 계산이 많아졌기 때문에 이전에 계산된 내용을 이용해 빠르게 문제를 풀 수 있을 것 같았다. 고민 후에 DP와 Map을 이용해 문제를 해결했다. [문제 풀이] 안티세포 X와 Y에 들어 있는 수 들을 아래와 같이 표현한다고 가정하자 $$ Y\,=\,(i_{ys},\, ...\, i_{ye})$$ $$ X\,=\,(i_{xs},\, ...\, i_{xe})$$ 여기서 안티세포 Y와 X의 합이 같아서 합쳐진다면 합쳐진 새 안티세포 N은 아래와 같이 표현할 수 있다. $$ N\,=\,(i_{ys},\, ...\, i_{xe})$$ 이제 N의 왼.. 2024. 3. 29.

[프로그래머스/C++] 튜브의 소개팅 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보고 어떤 값을 기준으로 priority_queue를 사용하거나 BFS로 풀면 되겠다는 생각이들었다. 그런데 priority_queue를 사용하면 정렬하는데 시간이 걸린다. 게다가 내가 return 할 답은 거리가 가장 짧은 값 중에서 대화시간이 가장 짧은 값이기 때문에 거리를 기준으로 정렬을 할 것이라면, BFS를 이용하면 된다. 그래서 BFS로 문제를 풀었다. BFS를 이용하면 항상 원점에서 이동한 거리가 짧은 값이 queue에서 먼저 나온다. 그러므로 이를 이용해 특정 지점에 방문할 때 마다 가지치기를 해, 쓸모없는 경우들을 가지치기 해 주었다. 가지치기를 하기 위해서 visited라는 2차원 배.. 2024. 3. 28.

이전 1 ··· 6 7 8 9 10 11 12 ··· 20 다음

티스토리툴바