본문 바로가기
반응형

분류 전체보기313

[백준/C++] 벽 부수고 이동하기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 (0, 0)에서 출발해 (N-1, M-1)에 가장 빨리 도착하는 최단경로를 구하는 문제다. 이 문제에서 중요한 점은 경로 중간에 벽이 있는 경우에는 벽을 부수고 이동할 수 있다는 점이다. 일단, 최단경로를 구하기 위해서는 BFS를 이용해 특정 지점에 처음 도달했을 경우에 이동한 칸수가 정답이다. 하지만 이 문제에서는 벽을 부술 수 있기 때문에 이를 고려해야 한다. 그러므로 특정 지점에 방문했을 때, 벽을 부수고 방문했는지와 벽을 부수지 않고 방문했는지를 구분해서 저장해 준다. 이를 위해 visited의 2차원 vector에 벽을 부수고 방문한 경우, 부수지 않고 방문하는 경우의 2가지 경우를 고려해 [.. 2024. 4. 13.
[백준/C++] 뱀과 사다리 게임 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 칸에 이동했을 때, 뱀이나 사다리가 있다면 다른 칸으로 이동할 수 있는 게 특징이다. 이렇게 이동을 하면서 마지막 칸인 100번 칸에 도착하면 승리하는데, 주사위를 조작해 원하는 숫자를 낼 수 있다면 100번 칸에 도달하기 위해 주사위를 가장 적게 굴리는 횟수를 구하는 문제다. 한번 이동할 때 마다 주사위를 굴리는 횟수가 1씩 늘어나므로, BFS로 문제를 풀면 빠르게 풀 수 있다. 이동 할 수 있는 곳은 현재 칸에서 1~6으로 6 곳이고, 이 6곳에 도착했을 때 뱀이나 사다리가 있다면 다른 칸으로 이동하면 된다. 이렇게 BFS로 문제를 구현하면 100번 칸에 처음 도달했을 때, 주사위를 굴린 횟수.. 2024. 4. 13.
[백준/C++] 3차원 토마토 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 토마토의 3차원 버전이다. 모든 토마토가 익을 수 있는지 확인하고, 만약 모든 토마토가 익는다면 걸리는 최소 시간을 구하는 문제다. 특정위치에 있는 토마토가 익을 수 있는 시간 중 가장 빠른 시간을 구해야 하므로, BFS를 이용하면 첫 방문했을 때가 토마토가 가장 빨리 익는 시간이 되는 것이다. 여기서 특정위치에 있는 토마토가 다음으로 탐색할 수 있는 곳은 6방향이다. 이를 이용해 6방향으로 탐색을 하고, 방문한 적이 없으면서 토마토가 있으면 queue에 넣어 탐색을 진행하면 된다. BFS로 문제를 풀 줄 안다면, 처음부터 토마토가 없는 빈칸만 잘 구분해주면 된다. 모든 위치에 대해 탐색이 끝났다면, .. 2024. 4. 12.
[백준/C++] 숨바꼭질 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N에서 출발해 M에 도착하는데 걸리는 가장 적게 걸리는 시간을 구하는 문제다. 그러므로 BFS로 풀면 M에 처음 도달한 순간이 가장 시간이 적게 걸린 것이다. 임의의 점 X에서 다음에 갈 수 있는 곳은 X+1, X-1, X*2이다. 그러므로 이 3곳에 대해 queue에 삽입해 탐색을 하면 된다. 여기서 다음에 갈 위치가 이미 방문한 적이 있다면, queue에 삽입할 필요가 없다. 왜냐하면 BFS로 탐색을 하기 때문에 첫 방문이 가장 시간이 적게 걸린 순간이기 때문이다. 이제 문제를 풀 때, 방문을 체크할 visited vector와 queue를 이용해 문제를 풀면 된다, ​ [아이디어 정리] N에서 M.. 2024. 4. 12.
[백준/C++] 오아시스 재결합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 두 사람이 서로 볼 수 있는지 수를 계산하는 문제다. A와 B를 선택해 그 사이에 사람의 키를 비교하기에는 매우 비 효율적이다. 두 사람 사이에 키가 큰 사람이 없기만 하면 서로 마주볼 수 있으므로 이를 이용해 문제를 풀면 된다. 그럼 여기서 두 사람 사이에 키가 큰 사람이 없다는 것은 어떤 의미일까? 잘 생각해보면 A와 B의 사이가 아닌 곳에는 키가 큰 사람이 있어도 된다는 뜻이다. 아래 그림을 한번 보면 A와 B 사이에 키가 큰 사람이 없으므로 A와 B는 볼 수 있다. 이를 이용하면 A의 왼쪽에는 키가 큰 사람이 와도 전혀 영향이 없다는 사실을 알 수 있다. 이제 문제를 푸는 방법은 다음과 같.. 2024. 4. 11.
[백준/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.
반응형

티스토리툴바