열심히해보겠씁니다

이 문제는 그 유명한 외판원의 순회와 비슷하다. 문제에도 대놓고 적혀 있는 만큼, 문제를 효율적으로 푸는 것이 중요한 것이 아니다. 비트 마스킹과 DP를 이용하면 조금 더 빨리 풀 수 있지만, 가벼운 완전탐색으로도 풀리는 문제이다. 가독성을 위해 거리를 구하는 함수를 따로 뺐고, 구현의 간편함을 위해 dfs로 구현한다. #include #include using namespace std; int T, N; int x[12], y[12]; bool used[12]; int tmpMax; int absDist(int x1, int y1, int x2, int y2) { int ret = 0; ret += x1 > x2 ? x1 - x2 : x2 - x1; ret += y1 > y2 ? y1 - y2 : y2..

삼성의 대표 시뮬레이션 문제이다. 모의 SW 역량테스트에도 나온 만큼 최신 트렌드 시뮬레이션에 맞는 문제라고 할 수 있으며, 그만큼 문제를 제대로 읽고 제한 조건을 정확히 구현하는 연습에 아주 좋은 문제이다. 여기서 SW 역량테스트는 삼성 공채 SW 검정을 뜻한다. 구현하기 힘든 포인트는 다음과 같다. 1. 생명력 수치가 X인 세포는 X시간 동안 비활성화고 X시간이 되었을 때 활성된다. 2. 세포는 활성화된 후 X시간 살아있으며, 죽으면 그 자리를 그대로 차지한다. 3. 동시에 같은 셀에 번식하면 생명력 수치 X가 높은 줄기 세포가 혼자 차지한다. 4. 배양 용기 크기는 무한하다. 우선 1번, 생명력 수치X는 고정되어 있어야 하므로 (한 번 1이면 영원한 1!) 생명력 수치 X 와 세포의 나이 X` 을 ..

가장 긴 증가하는 부분 수열 시리즈 중 난이도가 높은 5이다. 일반적인 방법으로 풀 수 없는 제한 조건이 있다. 수열의 크기가 100만이고, 숫자가 -10억부터 10억까지이므로 기존에 2에서 쓰던 방법들은 시간이 너무 오래 걸린다. 배열을 한 번 순회하면서 O(N) 논리적으로 저장하는 방식이 O(logN)이라면 NlogN ~ 2천만 회 정도로 1초 안에 풀이가 가능하다. 사용할 방법은 백트레킹이다. 이름이 어려워 보이지만, 단순히 내가 한 행동을 저장해 놓고 나중에 다시 꺼내보겠다는 얘기이다. 방식은 다음과 같다. 1. 주어진 수열(A)을 순회한다. 2. 가장 긴 부분 수열을 저장하는 수열(B)에 저장한다. 3. 가장 긴 수열이 저장되었다면, 저장한 값이 A에서는 몇 번째인지 백트레킹으로 추적한 후 저장..

오락실에 있는 고전 뱀 게임이다. 사과 먹으면 뱀 길이가 길어지는데 벽이나 자신의 몸에 부딪히면 죽는다. 게임이 총 몇 초(몇 회)만에 끝나는지 구하면 된다. 이 문제는 뱀의 처음 위치(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-..