내맘대로블로그

https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 나중에 문자열을 가공해서 산출하는 것과 같은 알고리즘 문제풀이에서 숫자 관련 응용문제가 나올 때 다져두면 좋을 것 같은 문제. 알고리즘 풀이를 하면서 느낀건 일단 알고리즘들을 이용해서 풀이하는 것도 중요하지만 일단 풀고 보는 것 구현이 제일 중요하다고 생각한다. 배열을 다루는 거나 그리디 같은 것도 기본적으로는 구현에서 시작한다고 생각하기 때문이다. 이 문..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net DFS를 이용해서 풀이해줘야 하는 문제. 원형이라 생각하여 어떻게 구현해야 하나 막막했지만 마주하는 부분의 값이 같을 때 회전하지 않고, 마주하는 부분이 다를 때 계속 회전하는 부분을 잘 생각해서 풀이하면 된다. 1. 계속해서 파고 들어가는 점에서 깊이 우선 탐색(DFS)해야 한다. 2. 종료 조건은 톱니를 벗어날 때(인덱스가 -1 이하거나 4 이상인 경우)와 마주하는 부분(N-N, S-S)이..

이전의 풀이보다 훨씬 깔끔하게 푼 거 같아서 추가 포스팅. 이번 풀이의 포인트는 인접한 나라를 관리할 때, 여기저기 변수 만들기가 헷갈리기도 하고 구역만 정해지면 독립적이라고 생각이 들어서 인접한 나라들을 다른 Queue에 넣어주었다. (Queue resultQueue) Queue에 넣어주면서 합계도 한 번에 하였고, Queue에 하나밖에 없으면 계산할 필요가 없기에 return 처리해 주었더니 이전 풀이에 비해 속도가 상당히 빨라졌다. 메모리는 똑같이 소모되는데 재탐색하는 과정이 없어서인듯하다. 풀이 방식을 정리하자면 일단 인접한 나라들을 전부 파악하며 두 나라들의 인구 차 범위를 확인해준다. (BFS, DFS 상관없음) 요구된 범위 안에 들어가 있다면, 다른 Queue에 넣어준다. 여기에 나는 fla..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 3개만 세울 수 있다는 것과 크기를 봤을 때, 백트래킹으로 모든 경우의 수를 구해서 풀이해도 될거라는 생각이 들었다. 따라서 백트래킹을 이용하여 모든 조합을 구해주었고, 그 값들을 벽으로 바꾼 후, BFS를 이용하여 전부 탐색을 해주었다.(DFS도 상관없음) 벽으로 바꾼 값들은 다시 돌려주어서 다른 경우에도 사용할 수 있도록 해주어야한다. 안전 지역을 파악하는 것때문에 전체 for문을 돌려서 안전한 곳만..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 먼저 boolean타입의 2차원 배열을 이용하여 청소한 부분을 확인해주고 계속해서 현재 위치를 끌고 나갔다. 청소가 안 되었다면 청소를 해주고,(marked = true) 왼쪽 방향(현재 방향을 기준으로 반시계 방향)에 청소를 해야한다고 할때, 새로운 좌표가 청소를 안 한 상태에 청소를 할 수 있다면 새로운 좌표로 다시 탐색 해주었다. 반대로 청소를 완료했거나 청소를 할 수가 없다면(벽이라서) ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 주어진 조건을 잘 거르고 양방향 설치가 가능하다는 점에 유의하면 된다. 시작점은 위거나 제일 왼쪽에서 시작. 나의 경우엔 배열을 일일이 만들어줘서 공통 메서드(route)에서 풀이하였다. 배열에서 인덱스값이 커지는 순서대로 파악하되, 앞뒤 값의 차가 1이면 경사로를 설치할 수 있는 길이가 되는지 확인한다. 앞뒤 차가 0이면 계속 탐색, 2 이상이면 경사로를 지을 수 없다. 경사로는 양방향이 가능한데 이 부분이..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 삼성전자 21 상반기 ce/im 기출문제 요구 사항대로 하면 되는 문제인데 조건들이 너무 세분화되어있어서 까다롭다고 느꼈다. 나무 재테크랑 비슷한 유형이라고 생각된다. 이 문제는 기본적으로 구현해야할 부분이 4단계이다. 근데 하나하나 유기적으로 연결되어 있어서 예외처리를 주의해줘야한다. 친구들 정보를 입력받는데, 친구들 입력 정보들은 마지막에 좋아하는 학생들이 주변에 얼마나 있는지 확인..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 이 문제는 세세한 사항이 많아서 정밀하게 하지 않으면 통과하기 어렵다고 생각한다. 큰 틀만 보면 BFS를 2번 돌리는데, 거리도 표시해주어야한다. 현재 위치에서 최단 거리 승객을 찾기위한 BFS 승객을 목적지까지 최단 거리로 데려다주기 위한 BFS 1. 에서 승객을 찾을 때 가장 가까운 승객, 가까운 승객이 많다면 행이 작은 순서, 열이 작은 순서대로 찾는다..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS를 두번 돌리면 되는 문제! 시간을 알아야하기 때문에 별도의 temp Queue를 둬서 계속해서 변하도록 하였다. 물이 생길 예정이 곳에 갈 수 없기에 먼저 물이 생길 법한 곳을 만들어 주고, 이동을 하였다. 이동은 간 곳 또 갈 수 있기에 방문 표시를 하지않았고, 물이 생길 곳은 방문표시를 하여 시간 초과가 나지 않도록 하였다. 또한, 시간을 알아야하기 때문에 나의 경우는 시간을 별도로 파악할 테이블을..

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 요청 사항에 따라 배열을 돌리는 문제! 나는 이런 배열을 돌리는 문제에서 주로 Deque를 이용해서 문제 풀이를 한다. 돌리는 방향에 맞게 for문 4개를 이용해서 순서에 맞게 해당 값을 모두 queue에 넣어준다. 이동하는 횟수에 맞게 앞의 값을 뒤로 다시 넣어줌으로써 순서를 맞춰준다. 이후 처음 값을..