내맘대로블로그

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)이..

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

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에 넣어준다. 이동하는 횟수에 맞게 앞의 값을 뒤로 다시 넣어줌으로써 순서를 맞춰준다. 이후 처음 값을..

요청사항에 따라 구현하였다. 구현 중에 주의해야할 부분은 구름은 경계를 넘나들어서 나머지 연산을 이용하여 올바르게 값을 넣어주어야하고. 바로 직전에 구름이 있던 자리엔 구름이 생기면 안 되기에 이 점도 유의해줘야한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107import java.io.*;import java.util.*; class Main { static int N;..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 중간 중간의 목적지를 분명하게 정하는 것이 중요한 문제! 1. 아기 상어의 위치에서 최단 거리 내 갈 수 있는 모든 물고기 위치의 경우의 수를 구한다. 2. 물고기가 두 마리 이상이라면 기준에 맞게 정렬한다. 3. 중간 중간 상어를 관리해주기 위해 자료형 shark를 만들었다. import java.io.*; import java.util.*; class Main { static int N..

16234번: 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 좀더 간결하게 풀이해서 포스팅 (링크) 이전엔 방문체크를 다른 배열을 둬서 했는데 그런 것 없이 한번에 풀이하여서 좀더 깔끔한 풀이가 됨 풀이 개요 BFS나 DFS 와 같이 완전 탐색 이용해서 풀이하면 되는 문제. 나는 BFS를 사용하였고, BFS 두 번 돌리면 시간 초과가 일어나기에 한번 BFS를 돌릴 때, 인구 이동시 필요한 값들을 다 저장해야한다. 문제 풀이시 약간 헷갈려서 같은 역할을 하는 방문 체크를 위한 배열이 2..