열심히해보겠씁니다

오락실에 있는 고전 뱀 게임이다. 사과 먹으면 뱀 길이가 길어지는데 벽이나 자신의 몸에 부딪히면 죽는다. 게임이 총 몇 초(몇 회)만에 끝나는지 구하면 된다. 이 문제는 뱀의 처음 위치(1,1)에서 시작하며, 오른쪽으로 출발한다. 가장 헷갈리게 만든 점은 X 초 후에 방향을 90도 꺾는다는 정보였는데, 방향을 바꾸고 나서 그 다음 X 초 후에 꺾는다는 소린 줄 알고 삽질하다가, 게임 경과 시간이 X초 일 때 방향을 전환한다는 것이라는 것을 겁나 늦게 깨닫고 고쳤다. ㅋㅋ 여하튼 주의하자. 1. 위치는 (행, 열) 로 주어진다 = (y, x)로 생각하면 편함 2. 게임은 반드시 끝난다. (X는 10000까지 이므로 10000초가 넘어가면 언제든 벽에 머리 박고 죽는다) 3. 본인이 바라보는 방향 기준 왼쪽..

오늘은 BFS의 살~~~~~~~~~~~~~~~~~~짝 응용판이다. (1,1) => (N, M)까지 도착하는 최단경로이고 맵이 1000x1000이기 때문에 DFS로 접근하기엔 크다. 고로 BFS 로 접근해 보자. 양방향 탐색으로 조금 더 빠르게 풀 수도 있겠지만 머리 아프므로 그냥 BFS로 풀어보자. 조금 어려운 부분은 벽을 한 번 부술 수 있다는 점이다. 아무리 벽으로 막혀있어도 한 번은 부수고 지나갈 수 있으니 벽을 부순다는 점을 기록할 판을 하나 추가로 마련하자. 그래서 내가 이동한 횟수를 기록하는 dp 배열을 만들건대, 벽을 한 번도 부수지 않은 상태와 벽을 한 번 부순 상태는 다르기 때문에 한 번도 부수지 않은 상태는 dp [x][y][0]에 저장하고 부수고 지나온 상태는 dp [x][y][1]에..

https://forswdev.tistory.com/entry/%EB%B0%B1%EC%A4%80-19236-%EC%B2%AD%EC%86%8C%EB%85%84-%EC%83%81%EC%96%B4-C 백준 19236 청소년 상어 - C++ 간단한 시뮬레이션 문제이다. 보통 상어가 나오는 문제 (마법사 상어, 아빠 상어...) 는 삼성 공채 SW검정 기출문제인 경우이다. 삼성이 목표라면 꼭 풀어봐야할 문제이므로 한 번 보자. 요즘 트렌 forswdev.tistory.com 청소년 상어가 진화했다. 마찬가지로 삼성스타일의 문제이므로 길고 자세한 시뮬레이션을 요구한다. 문제를 읽고 나면 역시나 규칙이 자세하고 복잡하여 머리가 어지럽지만 한 번 정리해보자. 1. 상어는 자신의 자리에 k 시간 유지되는 냄새를 남긴다...

간단한 시뮬레이션 문제이다. 보통 상어가 나오는 문제 (마법사 상어, 아빠 상어...) 는 삼성 공채 SW검정 기출문제인 경우이다. 삼성이 목표라면 꼭 풀어봐야할 문제이므로 한 번 보자. 요즘 트렌드는 복잡한 알고리즘을 요구하지 않지만 문제 자체가 길고 꼼꼼하게 읽어야 엣지 케이스를 맞출 수 있으므로 천천히 하나하나 읽으면 된다. 문제를 잘 읽었으면 구현시 어려울 것 같은 부분이 보인다. 1. 상어는 물고기의 이동이 모두 끝난 후 이동한다. 2. 다른 물고기가 있는 칸으로 이동할 때 서로의 위치를 바꾸는 방식으로 이동한다. 3. 상어는 여러 칸을 이동할 수 있으나 이동하면서 지나가는 칸에 있는 물고기는 먹지 않는다. 4. 최대로 먹을 수 있는 물고기를 구해야한다. 다행히도 같은 칸에 여러 물고기가 존재하..

참 재미있는 문제이다. 손으로 풀면 한참 걸릴 것이란게 예측되는가? 그렇다면 손으로 푸는 방식을 컴퓨터에게 시키면 금방 풀어줄 것이다. J군은 처음에 아무거나 하나 뽑을 수 있고, 하나를 뽑은 후에는 J군과 I양 모두 가져간 조각 옆에 있는 조각만 가져갈 수 있다. J군은 당장 왼쪽 케이크가 오른쪽 케이크보다 작더라도 총합이 크다면 왼쪽 케이크를 선택할 수 있다. J군의 자유의지를 통해서 바보 같이 큰 것만 가져가는 I양보다 훨씬 큰 이득을 챙겨보자. 언뜻 보기에는 이해가 안 갈 수 있다. 하지만 이 문제는 전형적인 DP(Dynamic Programming) 문제이다. 어떤 조각을 처음으로 뽑았을 때 J가 가져갈 수 있는 가장 큰 총합만 알면 되기 때문이다. 이를 재귀를 통해 구현한다. 재귀는 말로 푸는..

뿌요뿌요 같은 게임이다. 폭발 문자열이 폭발하면서 사라지면 나머지 스트링이 합쳐지면서 새로운 문자가 완성되고 거기에 또 폭발 문자열이 있다면 또 폭발하면서 새로운 문자열이 만들어지는 식이다. 모든 폭발이 끝났을 때 어떤 문자열이 남는지 확인해보자. 간단하게 스트링 패키지를 이용해보자. input을 입력 받고 한 번의 순회만으로 연산을 마쳐보자. 1. input 이 폭발 문자열이 없다고 가정하고 result에 추가한다. 2. result에 문자가 쌓이고 나면 마지막 글자를 폭발 문자열의 마지막 글자와 비교하여 폭발 가능성이 있는지를 빠르게 판단한다. 3. 폭발 가능성이 없다면 계속 input을 result에 추가한다. 4. 폭발 가능성이 있다면 폭발 문자열과 비교한 뒤 폭발한다면 result에 저장된 스트..

얼핏 보면 순회문제처럼 보인다. 하지만 이 문제에는 치명적인 함정이 있다. 그것은 바로 "비행기의 종류"를 세는 문제라는 것! 무슨 뜻이냐면, A 나라에서 B 나라로 한 번에 날아간다고 가정하자. 그러면 A B 를 아무리 왕복해도 종류는 1가지 뿐이다. 또한 문제에서 항상 연결 그래프를 이루고 있다는 것이 보장되어 있기 때문에 우리는 비행기를 몇 번 타느냐가 아니라 몇 종류를 타느냐에만 집중하면 된다. 그렇다면 몇 종류를 타야할까? 만약 당신이 중국 일본 한국 대만을 가야하고 모든 노선이 항상 존재한다고 한다면 비행기를 몇 종류 타야할까? 아무리 적어도, 아무리 많아도 3번은 타야 모든 나라를 갈 수 있을 것이다. 그렇지 않은가? 따라서 이 문제의 정답은 딱히 입력을 받지 않더라도 N개의 국가일 때 N-..

목차 21.11 ~ 22.09 내 소중한 토요일을 모두 바쳐가며 공부했던 Expert 가 마무리 되었다. 감상과 회고 SCSA16기로 합격하여 공채 SW검정 수준인 Advanced를 준비하면서 친구들과 스트레스 오지게 받던게 엊그제 같은데 뿌듯하다. SCSA 6개월 과정 중, 고향집 침대에 누워서도 끊임없이 문제만 생각하고 고민했던 시간들이 새록새록 떠올랐다. 아침 8시부터 머리를 돌리면서 점심/저녁 시간에 잠시 숨을 돌리고, 다시 야간 자율학습을 시작하여 12시, 1시까지 알고리즘을 풀었었다. 거의 고3임 그게 한 3주 정도 됐었나? 다른 교과과정이 있어서 C, JAVA, NETWORK 등등 배우면서 알고리즘을 계속 풀었던 것이라서 더더욱 쉽지 않았다. 대학교 4년에 해당하는 내용을 (실제로 4년어치는..

KMP 알고리즘의 응용 문제. 문제를 잘 읽고 다시 생각해보면 전체가 될 수 있는 부분 문자열 중 최소 길이를 구하라는 뜻과 같다. 즉 s = abcabcabcabc 문자열이 있다면 답의 후보는 abc, abcabc 가 되고, 그 중 더 짧은 abc 를 구하라는 얘기이다. KMP 알고리즘은 찾고 싶은 문자열의 접두사/접미사 중 최대 길이의 Index를 미리 구해놓는데, 그 연장선이다. 인덱스를 부여하는 것과 이 문제를 연관시켜보자. 1. 부분 문자열은 항상 index 0 부터 시작해야 한다. -> abcabcabcabc 라면 부분 문자열은 bca 형태로 만들어질 수 없고 항상 a 부터 시작해야 한다. 2. 부분 문자열의 중간을 건너뛸 수 없다. -> abcabcabcabc 에서 ab(c)abc 형태로 만..

KMP 알고리즘의 입문 문제이다. 문제에 친절하게 KMP 알고리즘에 대한 설명이 있으니 천천히 읽어보면 좋을 것 같다. KMP 알고리즘은 크게 두 가지 단계를 거친다. 1. 찾으려는 문자열(P)의 겹치는 접두사와 접미사를 찾아 그 위치를 기록하기. 2. 본 문자열(T)에서 찾으려는 문자열 찾기. 위 두 단계는 유사한 과정을 거치며, 접두사와 접미사가 중복되는 것을 이용하여 불필요한 탐색 횟수를 건너뛰려는 것이 궁극적인 목표이다. KMP 알고리즘을 이용하면 for 문 한 번에 모두 검색이 가능하므로 찾으려는 문자열의 길이를 M으로 두면, 1번 단계에서 O(M) 본 문자열의 길이를 N 으로 두면, 2번 단계에서 O(N)의 시간복잡도가 요구된다. 1,2 의 공통적인 핵심 아이디어는, 중복을 건너뛴다는 것이다...