Do You Coding?

- 문제 출처 : https://www.acmicpc.net/problem/188081. 생각격자로 된 모눈종이에 스티커들이 있고, 이 스티커들을 노트북에 붙이는 문제이다. 방법은 다음의 규칙을 따르는데,1) 스티커를 붙일 수 있는 가장 좌상단에 스티커를 붙힌다. (상단이 우선, 같은 높이에서는 왼쪽이 우선)2) 붙일 수 있는 위치가 없으면, 90도 회전하고 다시 1번 방법으로 돌아간다.3) 0도 / 90도 / 180도/ 270도 모두 붙일 수 없으면, 해당 스티커는 버린다. 가능한 많은 스티커를 붙이는 경우의 수의 문제거나, 붙히는 순서가 고정되어있지 않았다면 훨씬 복잡했을 수도 있지만,순서가 정해져있고, 붙이는 위치도 좌상단으로 고정되어있어 편하게 규칙대로 짜면 될 것 같다고 생각했다. 하지만 생각..

- 문제 출처 : https://www.acmicpc.net/problem/25791. 생각DP 문제를 한번 풀어보고 싶어서 "계단 오르기" 라는 문제를 실버 문제여서 골랐는데,'연속된 세 개의 계단을 모두 밟아서는 안 된다.'는 조건 때문에 어떻게 해결할지 막막했다. DP 테이블을 일단 만들어보려 했는데, 단순히 이전 계단과, 전전 계단의 dp 배열 값으로는 해결하지 못했다.2. 난관 & 해결방법우선 DP에 저장될 값은, 해당 계단까지 오기까지 얻을 수 있는 점수의 최댓값이다.int[] stairs = new int[N + 1];int[] dp = new int[N + 1]; 그렇기 때문에 계단의 점수를 저장할 stairs 배열과 dp 배열은 모두 N 개의 계단을 가지도록 만들어준다.( N + 1은 0..

- 문제 출처 : https://www.acmicpc.net/problem/156831. 생각정형화되어있는 다익스트라 알고리즘만 잔뜩 풀다가,창의력이 필요한 구현(시뮬레이션) 문제를 좀 풀어보려고 '감시' 문제를 정했다. 총 5가지의 방향이 주어져있는 CCTV를 K개 가지고 있는 사무실에서,CCTV로 볼 수 없는 사각지대의 최소크기를 반환하는 문제이다. 직관적으로 생각했을 때 boolean 2차원 배열을 하나 더 만들고,감시 가능한 구역을 반복문으로 방향별로 true로 바꿔주고, backtracking 후, 원상복귀 시켜두는 맥락을 생각했다. 하지만 생각보다 너무 복잡해서 짜는 데에 어려움이 있었다.2. 난관 & 해결방법static class CCTV { int x; int y; int ..

- 문제 출처 : https://www.acmicpc.net/problem/1238 1. 생각저번 문제에 이어 이번에도 다익스트라 문제를 풀게 되었다. 기본 다익스트라와 다른 점은, 왕복으로 목적지를 갔다가 돌아오는 최소시간을 구하는 것인데,간선들이 양방향이 아니라 단방향이라는 점에서 단순하게 걸린시간을 2배로 하는 게 아닌 점에서 고민이 필요했다. 2. 난관 & 해결방법왕복을 처리하는 방법을 고민했을 때, 우선 dijkstra() 함수를 도착지인 X를 기점으로 1번 돌려서 모든 마을에 대해서 N에서 출발해서 도착하는 최소시간을 구해두고,각 마을에서 N으로 가는 최소시간을 dijkstra()를 각각 돌려 하나씩 구한 뒤, 두 결과를 더하면 되겠다고 생각했다. static int dijkstra(int s..

- 문제 출처 : https://www.acmicpc.net/problem/117791. 생각다익스트라 기본 문제를 풀어보기 위해 문제를 선택하였다. n개의 도시에 m개의 버스가 있고, A번 도시에서 B번 도시로 가는 최소비용과 경로를 출력하는 문제이다.(1 우선은 클래스를 하나 만들어서 목적지와 현재까지의 가중치를 저장할 변수를 담으려고 했고,그 가중치를 기반으로 PriorityQueue에 넣어 다익스트라에 적용하는 것으로 생각했다. 기존 다른 다익스트라 문제와 다른 점은, 출력 부분에 보면1) 최소비용 / 2) 최소비용 경로 포함 도시 개수 / 3) 최소 비용 경로 도시 순서 이렇게 구해야하는 것이 3개나 있었다.최소비용은 기존 처럼 min값을 누적해가면서 구하면 되는데,나머지는 생각이 좀 필요해보..

- 문제 출처 : https://www.acmicpc.net/problem/108161. 생각이번에도 map을 활용한 문제이다. 문제가 요구하는 사항 중에 이분탐색을 이용하는 것도 있었으나,이분탐색 알고리즘을 아직 해보지 않아서 map만 활용해서 해보도록 하겠다. 2. 난관 & 해결방법std::map m; 숫자카드의 숫자와 개수를 각각 key, value로 두기 위해 int, int로 map을 만들었다. for (int i = 0; i > num; auto it = m.insert({num, 1}); if (!(it.second)) it.first -> second ++;} 반복문에서는 insert로 값을 넣어주는데, 이 insert의 반환값이 pair 이라는 것을 알게 되어 ..