본문 바로가기
반응형

분류 전체보기308

[백준/C++] 오등큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 오큰수 문제와 크게 다른게 없다. HTML 삽입 미리보기할 수 없는 소스 오큰수가 오른쪽에 있는 수 중에서 크면서 가장 가까운 수를 찾는 문제였다면, 오등큰수 문제는 등장하는 횟수를 비교하는 문제다. 즉, 비교하는 게 숫자의 크기가 아니라 등장횟수로 바뀐 것 뿐인 문제다. 처음에 문자가 몇 번 등장했는지를 map이나 array를 이용해 기록한다. 이후 순차적으로 숫자를 비교해 등장 횟수가 i번 째 수보다 큰지 비교하면 된다. 만약 i번째 수와 같거나 작다면 stack에 i번째 숫자를 기록한다. (stack에 i번째 수 추가) 마찬가지로 stack구조를 이용하면 문제를 쉽게 풀 수 있기 때문에 stack.. 2024. 4. 10.
[백준/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.
[Unity] Touch로 물체 Drag하기 HTML 삽입 미리보기할 수 없는 소스 카메라가 고정된 환경에서 물체를 터치해서 움직이려고 했다. 이를 구현하기 위해서 Ray와 Touch, Camera.main.ScreenToWorldPoint를 이용했다. 내가 구현하려던 움직임은 3D 환경에서 드래그앤 드롭으로 2D 평면 이동하듯이 시키고 싶었다 그런데 문제가 있었다 카메라가 기울어져있는 상태로 위에서 쳐다보는 상태였기 때문에 Screen에서 Touch한 곳의 좌표와 내가 보는 화면의 world좌표가 실제로는 달랐던 것이다. 즉, 아래 그림과 같은 상태였던 것이다. 실제 터치된 좌표와 터치된 object의 좌표가 달랐기 때문에 드래그를 시작하면 좌표에 오차가 생겼다. 이를 offset을 이용해 보정해 문제를 해결했다. GameObject hitObj.. 2024. 4. 4.
[프로그래머스/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.
반응형

티스토리툴바