본문 바로가기

PS/BaekJoon

(105)
[C++/22252] 정보 상인 호석 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.이 문제는 우선순위 큐와 맵을 사용해 문제를 푸는데, Input 조건을 잘 봐야했습니다.무엇이 문제냐, Q가 100,000개이고, 만약 갖고 있는 정보의 가치가 전부 100,000이라면?  그 개수의 합은 얼마가 될까? 당연히 인트로 10,000,000,000 을 잡을 수 있을까요? long long으로 변환을 해서 문제를 해결할 수 있습니다.정답 코드는 이렇습니다. 그래도 map에 priority_queue도 넣어보고 아주 재미난 문제여서 작성해봅니다. 그리고 우선순위 큐는 기본적으로 내림차순을 갖고있기 때문에, 오름 차순을 하고자 한다면? -를 넣어서 바꿔주던지 아니면 greater였나.. 그..
[C++/27438] 행렬 연산 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.꽤나 재밌는 문제를 풀었습니다. 일단 입력값이 가로 세로의 곱이 500,000이며 주어지는 명령이 500,000개가 나올 수 있습니다. 당연히 500,000만큼의 이차원 배열을 만들 수 없습니다. 하지만, 가로와 세로의 길이는 1 그렇다면? 우리는 어떻게 풀어야할까? 그렇다면 처음에 풀이를 했던 방법을 설명하겠습니다. 첫번째는 배열을 생성하는 것보다는? 그냥 map에 좌표를 key로 등록해서 value값을 늘려주는 방식을 채택했습니다. 그렇게 한다면? 우리의 문제였던 배열을 50만 만큼 할당하지 못했던 문제를 해결할 수 있습니다. 하지만 이는 시간초과의 문제를 발생시킵니다.왜냐하면 배열이 없지만,..
[C++/26168] 배열 전체 탐색하기 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.이분탐색으로 문제를 해결합니다. 7월에는 블로그에 글을 안올렸지만, 사실 문제는 꾸준히 쉬운 레벨이여도 생소한 문제를 보면 바로 문제를 풀었습니다. 이 문제는 오랜만에 이분탐색을 풀면서 중복되는 값의 첫번째 값과 마지막 값을 구할 수 있다는 것을 처음 알았습니다(?) 이분 탐색 문제는 아주 오랜만에 풀어서 굉장히 시간이 오래걸렸습니다.아래는 정답코드입니다. 이 문제는 추후에 다시 해결하면서 다시 이분탐색을 자유자재로 써볼 수 있게 구현해봐야겠습니다.#include#include#define MAX 100100using namespace std;// 끝과 끝일떄 문제 26168 int n,m;lon..
[C++/18115] 카드놓기 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.각 명령에 따라서 구현을 진행하면 되는 문제입니다. 하지만, 문제를 천천히 읽어보면? 카드는 [5,4,3,2,1]로 쌓여야합니다. 그리고 각 명령이 앞에서도 빼고 뒤에서도 빼고 중간에서도 빼는 그러한 문제이기 때문에 자료구조는 deque을 사용하기로 했습니다. 문제를 해결하면서 주어진 입력대로 하면 될것 같지만? 카드를 되돌리기 위해선? 거꾸로 진행을 해야하지 않나 생각을 했지만, 일단 정방향대로 문제를 해결하려했습니다. 하지만, 그렇게되면? 뒤에서 뽑아온 숫자들은 순서가 반대가 되기 때문에 뽑아왔던 순서에서 반대로 진행하면서 다시 원상복귀를 시켜야합니다. 생각을 할 수 있겠죠? 거꾸로 하면 그대..
[C++/28066] 타노스는 요세푸스가 밉다. ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.컨베이어 벨트처럼 차례대로 정리하고 정리하지 않은 박스는 맨 뒤로 보내는 작업입니다. 링크드 리스트를 직접 구현해서 문제를 해결할 수도 있는 문제네요. 하지만, 그렇게까지 고생은 하고싶지 않기 때문에, 간단하게 배열로 해결하려고 했지만, N의 개수가 1,000,000개입니다. K가 극단적으로 적다면? (1,000,000 + 1)을 500,000번 반복해야 하기 때문에 시간 초과가 발생할 수 밖에 없습니다. 그래서 queue를 이용해 푼다면? 쉽게 풀리는 문제입니다.아래는 정답코드입니다.#include#include#include#define MAX 1000100using namespace std;..
[C++/28256] 초콜릿 보관함 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.범위도 3x3으로 정해져 있고, 가운데를 제외한 나머지 초콜릿이 그룹을 어떻게 이루어져 있는지 파악하는 문제입니다. 구현할게 은근히 많지만 그래도 기본적인 구현공부를 했던 사람이라면? 충분히 풀어낼 수 있는 문제입니다.하지만, 나는 여기서 한 번 틀리고 마는데 이유는 무엇이냐면? 화면에 표시된 숫자의 개수인 n이다. n은 0 부터 4 까지이며 그리고 다음 문제는 이것이다. 정답을 틀리게 줄 수 있는 것이다. 개수가 같아도 틀릴 수 있고, 등등 여러가지 조건이 붙어 있다. 아래는 정답 코드이다.#include#include#include#include#include #define MAX 4using..
[C++/2115] 갤러리 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.가로 세로 줄마다 벽이 어느정도 이어져 있는지 파악하면 되는 문제입니다. 정답률이 굉장히 높기 때문에 도전했습니다. 저번에는 정답률이 20~30%정도의 문제만 풀었는데, 이런 문제도 풀어야하지 않을까요? 해서 풀었습니다. 근데 매번 낮은 문제만 풀다보니 정답률이 높아도 의심이 가더라고요 그래서 심사숙고해서 문제를 풀었습니다.해당 문제에서는 벽2칸에 그림 하나를 걸 수 있는데, 그런 벽이 몇개 있는지 알아야합니다. 그래서 연속적으로 어떻게 벽이 이루어져 있는지 파악하는 문제입니다. 그래서 구현을 깔끔하게 해줘야합니다.입력값도 1#include#include#define MAX 1010using na..
[C++/23796] 2,147,483,648 게임 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.2,147,483,648 게임이란, 2048 게임과 같고, 숫자의 범위만 int의 마지막값입니다. 그래서 unsigned int로 범위를 정해놓고 문제를 해결했습니다. 물론 입력값으로 저 값이 나오진 않지만 혹시나 몰라서 타입을 unsigned로 정해놨습니다.문제를 해결할때, U,L,D,R 로 4가지를 구현하는 것 또한 좋은 방법입니다. 하지만, 해당 문제를 해결하면서 4가지를 전부 구현하는 것 보다는 배열을 시계방향으로 돌려가면서 하나의 방식으로만 이동을 시킨다면? 좀 더 문제 해결에 문제가 없을 것 같았습니다. 구현시 어느 부분에서 문제가 발생했는지 4개를 살피는 것보다는 더 나으니까요. 해당..