Be a developer

예제가 많아서 조금 짤렸다.. 오랜만에 시간 안에 푼 문제이다. 1시간 40분 정도 걸려서 푼 것 같다. 처음부터 손으로 정리를 하고 풀었더니 문제가 쉬운 건지 모르겠으나 비교적 쉽게 풀었던 것 같다. 1. 오른쪽으로 쭉 감시 방향을 체크하는 함수, 왼쪽, 위, 아래로 감시하는 함수를 각각 만들었다. 처음에는 하나의 dfs 함수에 다 구현하려 했으나 너무 같은 코드가 반복되어 함수로 따로 만들어 주었다. 그랬더니 cctv의 종류에 따라 맞는 함수만 골라 쓰면 되어서 편하게 구현할 수 있었다. 2. 재귀로 구현되기 때문에 종료 조건이 있어야 한다. 선택한 cctv의 개수가 총 cctv의 개수와 일치하면 사각지대의 수를 ans vector에 넣는다.(나중에 최소값을 찾기 위해 사각지대 수를 넣어둔다.) 이 ..

사진은 너무 많아서 일부만 가져왔다.. 오늘도 돌아온 반성의 시간.. 뭘 잘못했는지 알아보자. 1. 나름대로 생각해서 어떻게 풀지 정한다음 코딩을 시작했다. 하지만 그 문제를 푸는 방식부터 잘못되었다. 즉, 생각은 했으나 그 방법으로 풀릴지 검증을 하지 않고 코딩을 시작한 문제이다. 처음에는 각 가로 사다리를 2차원 배열의 한 원소로 잡는 것이 아니라, 세로선과 가로선이 만나는 부분을 한 원소로 잡으려고 했다. 그래서 인접한 두 원소가 true이면 사다리가 있는 것으로 하려 했다. 하지만 이는 오른쪽으로 연속된 두 사다리를 체크할 때 힘들다. 1111과 같은 경우 사다리가 2개 있는 것인데 이를 구분할 방법이 없다. 그래서 생각한 것이 중간에 사다리가 있고 없고를 구분하기 위해서 111000과 같이 두어..

정말 삽질을 많이 해서 배울 것이 많았던 문제이다.. 정답률이 높아서 쉬울 거라고 생각했는데, 첫 접근부터 이상했기 때문에 4시간 동안 생각하고도 풀지 못해서 결국 인터넷에 검색해서 참조했다. 삽질 목록 1. 문제에 대한 접근이 잘 못 되었다. 세대가 증가하면서 그려야 하는 방향이 역 방향으로 가는 구조임(현재 끝점이 3으로 왔고, 바로 앞의 점이 2 방향으로 왔다면, 다음에 그릴 점의 방향은 0이 되고, 그 다음 그릴 점의 방향은 3이 됨.)을 알았다. 하지만 그 전에 그리는 드래곤 커브를 vector에 일일히 저장하는 방식으로 풀려고 하다보니, stack을 사용하려 하지 않고, 어떻게든 만들어 놓은 vector를 사용하여 풀려고 했다. 그러다보니 코드가 복잡해졌고, 멘탈이 나가게 되었다. => 풀다가..

치킨 배달 풀다가 치킨 먹고 싶어서 시켜먹음.. 먹고 다음날 마저 풀었다.. 처음에 거리를 구하기 위해서 bfs로 짜다가 잘못되었음을 알고 바로 지웠다. 왜냐하면 집과 치킨 사이의 거리만 알면되기 때문이다. 최소 거리라고 적혀있어서 아무 생각없이 풀었던게 문제였다. 그냥 집과 치킨집 사이의 거리를 vector에 넣고 최소 거리만 찾으면 되는 거였다. 그리고 치킨집 중에서 m개를 골라야 하기 때문에 순열로 풀려고 했으나, M이 최대 13이므로 13!은 시간 초과가 뜰 것이라 생각해서 재귀함수로 풀었다. 치킨집 하나를 추가하고 빼는 것에 주의해야 하고, 또 다음에 선택할 번호인 idx가 vector에 있는 치킨집의 수(vector의 사이즈)를 넘을 경우 재귀가 종료된다는 것에 주의해야 한다. idx가 m일 ..

이번에도 예제가 너무 많아서 사진은 다 넣지 않았다.. 인구 이동 문제도 앞선 2문제와 같이 시뮬레이션 문제이다. 주어진 조건을 만족하도록 코딩하면 된다. 시뮬레이션 문제는 사용하는 언어를 얼만큼 숙련도 있게 다루는가가 중요한 것 같다. 아직 c++이 익숙하지 않아서 조금 힘들었다. vector배열을 많이 사용해보지 않아서 저장하고 가져오는 방법이 혼란스러웠다. 또한, bfs를 사용하는데 visit를 설정하는 조건이 조금 까다로웠던 것 같다. 인구수가 l과 r사이에 없을 때, 연합 목록에 넣지는 않아도 visit는 true로 설정했었는데, 모든 배열을 돌기 위해서 l과 r사이에 없을 때 visit를 false로 두는 조건이 까다로웠다. 제시된 예제는 다 맞았는데 답안을 제출할 때 틀렸다고 나와서 디버깅하..

예제가 너무 많아서 사진은 조금 생략.. 앞에 풀었던 아기 상어 문제가 시뮬레이션 문제라는 것을 풀고 나서 알았다.. 주어진 조건에 맞게 풀면 되는 문제가 시뮬레이션이라고 한다. 이번 문제도 시뮬레이션 문제이다. 주어진 조건에 맞춰서 풀면 된다. 사람마다 당연히 코드는 다르겠지만, 뭔가 코드가 보기 힘들게 짜여진 것 같긴하다. 앞으로 보완해야 겠다. 처음에 입력받는 A배열을 겨울에 더해주어야 하는데 처음부터 더해주어서 계속 틀렸다. 문제도 꼼꼼히 읽어봐야 겠다. 나무는 추가되고 삭제되기 때문에 편하도록 vector로 저장했다. 특히, 3차원 vector를 만들어주었다. 3차원 vector는 처음 써보아서 눈에 잘 익혀둬야 할 필요성을 느꼈다. 삭제로는 erase 함수를 사용했는데, 해당 인덱스 원소가 지..

코딩 테스트를 5일 앞두고 기출 문제를 조금씩 풀려고 한다. 푸는데 성공하면 글을 쓰겠지만, 못 풀면 이 문제 이후로 업데이트가 없을 수도.. 알고리즘 2를 수강하면서 한 번 풀어보았던 문제여서 그래도 풀 수 있었던 것 같다. 한 번 이동이 가중치 1이고, 계속해서 가장 가까운 물고기를 찾아야 하기 때문에 bfs를 통해 풀 수 있다. n의 크기가 최대 20이기 때문에 시간 복잡도도 충분하다. 무한 루프를 통해서 bfs를 계속 돌면서 먹을 수 있는 물고기를 찾는다. 만약 먹을 수 있는 물고기가 더이상 없으면 무한루프를 종료한다. 먹을 수 있는 물고기를 vector에 추가하고, 여러 마리가 있을 경우 row와 col을 비교하여 처리하는 것이 조금 귀찮은 문제인 것 같다. 물고기를 먹고 나면 dist 배열을 ..

앞서 풀었던 숨바꼭질 문제처럼 최소 비용을 구하면 된다. 최소 비용으로 가는 방법의 수는 다이나믹 프로그래밍 기법을 이용한다. 즉, 만약 처음 방문하는 거면 최소 비용으로 도달한 것이기 때문에 바로 앞의 위치까지 가는 방법의 수를 그대로 넣어준다. 이미 방문했던 곳에 최소 비용으로 다시 도달하게 되면, 방법이 더 있는 것이므로 바로 앞의 위치까지 가는 방법의 수와 이전에 현재 위치까지 오는 최소 비용 방법의 횟수를 더해준다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include using namespace std; ..