백준

문제 내용문제 링크 우리가 아는 그 주사위가 있다. 또, (N*M)의 지도가 있다. 주사위의 초기 숫자는 모두 0이며, 놓여진 위치는 x,y로 주어진다. 규칙은 다음과 같다.주사위가 이동할 때, 이동한 (지도의) 칸이 0이라면 주사위 바닥면에 쓰여 있는 수가 칸에 복사된다.0이 아니라면 칸에 쓰여있는 수가 주사위의 바닥면으로 옮겨진다. (칸은 0이 된다)주사위는 지도 바깥으로 이동할 수 없다. (즉 바깥으로 이동하는 명령은 무시한다.)주사위의 초기 좌표, 지도가 주어졌을 때 각 명령에 대해, 명령대로 이동한 다음 주사위 윗 면의 수를 출력한다.  문제 풀이역시나 삼성 코딩테스트 기출 문제인 만큼 구현에 집중하자. 본인은 주사위의 인덱스에 집중했다. /* 초기값 인덱스 * X 1 X X 0..

문제 설명문제 링크 집은 격자판 (R*C)로 나타낸다. 로봇청소기는 항상 첫 번째 열에만 위치하고, 두 개의 행을 차지한다. 다시 말해, (2*1)의 크기이다.  또 각 칸에 있는, 0초 시점의 미세먼지가 주어진다. 미세먼지는 확산 가능한데, 이는 매초마다 이뤄지며 동시에 일어난다. (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산되고, 인접한 방향이 공기청정기나 벽으로 막혀있다면 확산이 발생하지 않는다. 확산되는 양은 A(r,c)/5이고 소수점은 버린다. (r,c)에 남은 양은 기존 미세먼지 양에 확산된 총량을 제한 크기이다. 미세먼지가 확산되고 나서, 공기청정기가 작동한다. 공기청정기에서는 바람이 나오는데, 위쪽 공기청정기는 반시계 방향, 아래쪽 공기청정기는 시계방향으로 순환한다. 바람의 방향대로..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 최소비용 구하기 1에서 최소비용의 경로까지 출력하는 문제이다. 다익스트라 알고리즘에서 최소비용을 갱신할 때마다 나에게로 향하는 노드가 무엇인지 저장해준 후 역순으로 출력해주면 된다. 위와 같은 그래프에서 우리는 1번 노드에서 4번 노드로 갈 것이다. 다익스트라 알고리즘을 위 상황에 적용시켰을 때, 각 노드에서 갱신되는 "1번 노드부터의 거리 배열"이다. 문제에서 요..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 주어진 두 배열에서 같은 숫자로 이어진 구역을 나누고(구역은 상하좌우로 이어져있어야 한다), 두 배열의 모든 구역의 모양이 같아야 하고 숫자가 다른 구역이 1개 이하이면 YES, 구역의 모양이 다르거나 숫자가 다른 구역이 2개 이상이라면 NO를 출력해주는 문제다. 문제의 예제와 같이 위와 같은 두 배열이 있다고 하자. 우리는 새로운 구역을 찾을 때마다 모..

https://www.acmicpc.net/problem/5710 5710번: 전기 요금 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지 www.acmicpc.net 구현과 이분탐색을 적절히 섞어놓은 문제였습니다. 아이디어로는 상근이가 아예 전기를 안쓴 경우(0 Wh)부터 전기를 전부 썼을 경우(A Wh) 사이를 이분탐색으로 구하는 것입니다. 이분탐색의 규칙으로는, 중앙값을 상근이가 사용한 전기의 양, 총사용량에서 중앙값을 뺀 값이 이웃이 사용한 전기의 양이고 이웃-상근이의 값이 B이면 이때의 상근이의 전기요금을 반환, 아니면 이분탐색을 하도록 ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 아리스토텔레스의 체로 소수 벡터를 구하고, 투포인터로 답을 구하는 문제였습니다. 문제를 처음 접하고, N의 범위가 400만까지 가는 것을 보고 아리스토텔레스의 체로 구하면 시간이 괜찮을까..? 싶어서 소수판별 관련된 이것저것 찾아봤는데, 아리스토텔레스의 체의 시간복잡도는 Nlog(logN)) 으로 생각보다 좀 많이 빨랐습니다. 머쓱 소수 벡터를 구한 이후로는 여타 투포인터 문제풀이를 하듯, 앞에서부터 포인터 2개로 둘 사이의 총합을 구해가며 총합이 n인 경우의 수를 구하면 됩니다. #include #include u..

https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 크기가 N인 배열이 주어지고, 각 칸에는 1 이상 N 이하인 정수가 들어갔을 때, 만들 수 있는 모든 사이클의 노드 개수와 노드를 정렬하여 출력하는 문제이다. 문제를 처음 접하였을 때, 모든 사이클이 아닌 가장 큰 사이클을 찾는 것이라 착각했는데, 경험의 부족인듯 하다(...) 루프 또한 사이클이므로 입력단계에서 미리 처리해주고 루프가 아닌 사이클을 모두 찾는 순서로 구현하였다. #i..