본문 바로가기

PS

 (193)
[기출문제] 고대 문명 유적 탐사 for(int i = 0; i 이 문제는 캐시를 활용해서 좀 더 쉽게 구현이 가능할 것 같은데, 캐시보다 내가 직접 구현하는게 마음이 편해서 그냥 구현했다. 물론 캐시를 이용하면 코드의 양이 줄고 실수가 줄을 텐데... 사실은 캐시를 제출하고 생각하게 됐다. 캐시를 하게 되면 다시 rotate를 하지 않아도 될텐데!그리고 이 문제는 어느 특정 위치에서 rotate를 할때 발생하는 착오가 굉장히 많이 생겨난다. 오늘은 그것을 정리해볼 것이다.특정 위치에서 시계방향 또는 반시계방향을 돌리는 것이 이 문제 해결의 주요 쟁점이 될 것이다.천천히 정리를 해보겠습니다.일단 기본적인 시계방향 전환입니다. 시작 위치는 (0,0)이고 배열의 범위는 n - 1 입니다.void cw() { int temp[MAX][MAX..
[기출문제] 마법의 숲 탐색 코드트리 기출문제에 있는 문제를 풀었다. 왜냐하면, 극한의 구현 문제이기 때문이다. 집중을 빡하고 풀어줘야지 실력도 상승하고 긴장감도 유지할 수 있기 때문이다. 그렇기에 해당 문제를 해결해보았다.문제 유형은 정말 4~5가지의 알고리즘 문제를 한문제에 합쳐둔것 처럼 어렵다. 하지만 차근차근 문제를 풀어나가다 보면 어느순간 해결이 되어있는데 그 짜릿함이 있다. 그래서 오랜만에 구현문제들로 풀어보았다. 요즘은 다른 유형이 생겨났던데 굉장히 어려워서 그거는 풀지 않았다.해당 문제는 범위를 늘려줘야하는 것에 키포인트가 있다고 생각한다. 골렘이 초반에 필요한 열은 3칸이다. 행은 뭐 신경쓸 필요는 없고, 그래서 열의 길이보다 +3칸 늘려줘서 거기서부터 시작하는 것이 좋다.그래야 생각도 편해진다. 대신 열의 길이를 ..
[C++/14402] 야근 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.야근 듣기만해도 오늘 내가 일을 못했구나 하는 느낌입니다. 야근하지 않기 위해서는 일에 몰입해야겠죠. 또는 일이 너무 많아서 야근을 하게 된다면 일단 최선을 다해야된다고 생각합니다. 왜냐면 어쨌든 저는 조직 소속이니까요.이 문제는 야근을 한 인원이 몇명인지 파악하는 문제입니다. 조건은 아래와 같습니다. " 만약, 들어간 기록은 없는데, 나온 기록이 있다면 회사에서 야근을 한 것으로 기록된다. 또한 회사에 들어갔는데, 퇴근시간까지 나오지 않는다면, 이 또한 야근을 하는 것으로 기록된다. 출입기록에 따라서 두 기준 다 만족할 수도 있는데, 이는 야근을 두 번 한 것으로 인정된다. "들어간 기록은 없는..
[C++/26042] 식당 입구 대기 줄 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.정답 비율이 33퍼센트정도 되길래, 와 문제 어려운 문제구나 실버 5인데도 이정도 정답률이면 배울 점이 많을 수 있겠다 싶어서 도전을 하게 되었습니다. 일단 기본적으로 입력값 10만으로 시작하기 때문에 특정 자료구조를 사용해야겠구만 하는 찰나에 큐가 생각이 났고, 그리고 읽어보면서 딱히 어려운 점이 없길래 그대로 구현을 시작했습니다.그 결과 "맞았습니다"를 받게 되었고? 왜 어려웠을까 질문 게시판과 난이도 기여를 들어가보았더니 글을 잘못읽고 실수하신 분들이 많았습니다. 저는 운 좋게 한번에 이해를 해서 쉽게 풀이했습니다. 아래는 정답 코드입니다.//https://www.acmicpc.net/pro..
[C++/8891] 점 숫자 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.휴가를 알차게 보내고 오느라 모든걸 놓고 놀았습니다. 휴가 복귀후에 감이 떨어졌나 확인할 겸 쉬운 문제 하나 풀어봤습니다. 문제 고르는 능력이 좀 부족하다고 생각이 됩니다. 고를때마다 처음보는 유형인 문제를 고르는 것 같습니다.어쨌든, 해당 문제는 아래와 같이 풀었습니다.한줄을 레벨이라고 표현해보겠습니다. 한 레벨이 늘어날 때마다 1개 2개 3개 4개 ... n - 1개 n개로 늘어나는 것을 먼저 파악했습니다. 총 개수가 계속해서 늘어나고 있으며, 마지막 숫자는 그 레벨의 마지막 값이 될 것입니다.그리고 위 내용을 저장하는데, 배열을 사용했습니다. 배열의 인덱스에 맞춰서 1은 마지막 숫자 1,  ..
[C++/2594] 놀이공원 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.요즘들어 알고리즘 문제 풀기가 힘드네요. 그래도 꾸준히 하나씩은 쉬운거라도 풀어야 감각을 잃지 않을 것 같습니다. 그래서 실버3 문제 ㅋ 20분이내로 천천히 풀겠거니 하고 건드렸다가 대략 1시간 가까이를 뺏겼네요. 아오 시간은 분으로 바꿔서 구하는게 쉽다는걸 알면서도 매번 까먹습니다. 그리고 00분부터 59분까지가 60분인데 자꾸 그것도 바보처럼 풀었네요. 그래서 시간이 오래걸렸습니다. 항상 시간문제는 무조오오오오건 분으로 치환해서 또는 초로 치환해서 풀도록 생각해야겠습니다. 아래는 정답 코드입니다.#include#include#define MAX 2201using namespace std;int..
[C++/16958] 텔레포트 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.플로이드 와샬로 풀었지만, 이동할 수 있는 도시를 전부 계산한 후에 텔레포트로 이동이 가능한 곳에서 다시 이동이 가능한지 파악하면 문제를 해결할 수 있을 것이라고 본다.근데 문제 해결할 때는 플로이드 와샬로 문제를 해결했는데, 생각해보면 N 3제곱이기 때문에 10억이라는 값이 나와서 시간초과가 되는게 당연했는데 문제가 풀렸다? 이유는 단순 계산은 시간을 넉넉히 준다는 것이라는데 이유는 정확히 모르겠다. 아마 시간초과 됐으면 텔레포트되는 곳을 찾아서 문제를 해결했을 것 같습니다. 아래는 정답 코드입니다.#include#define MAX 1010using namespace std;struct inf..
[C++/27210] 신을 모시는 사당 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.천천히 문제를 그려나가보니, 입력값도 작고(N = 100,000) 두방향(1인지 2인지) 판단을 해보면서 어느 범위가 가장 많은 값을 얻을 수 있을 것인가 생각해보는 문제라고 생각한다. 그렇게 어려운 방법은 아닌데, 아마 새로운 방법이 있지 않을까 생각이 됩니다. 정리하자면, 1을 기준으로 차례로 금을 칠하면서 어느 범위까지 값이 가장 큰지 차례대로 dp[i-1]과 현재 값을 비교하면서 최고의 깨달음과 2를 기준으로 위의 내용과 같이 진행해서, 그 두개의 dp 테이블에서 가장 큰 값을 구하면 됩니다.아래는 정답 코드입니다.#include#include#define MAX 100000using na..

티스토리툴바