구현

문제https://www.acmicpc.net/problem/2477 여담처음에는 이동하는 발자국만 생각해서 2차원 배열에 방문한 위치를 표시하고 BFS 탐색을 수행하는 방식으로 진행했다.("전체 크기 - 사각형에 포함되지 않는 영역"을 구하면 된다고 생각했었다. 대체 뭔 생각으로 했는지...?) 두 번째는 큰 사각형에서 포함되지 않는 사각형을 빼면 될 것 같다고 생각했다. 최대 가로/세로, 최소 가로/세로 길이를 구해서 계산을 했는데 이는 너무 단편적으로만 생각을 해서 틀렸다. (포함되지 않는 작은 사각형이 포함되는 작은 사각형보다 클 수 있음..!)  결국 다른 풀이를 참고했는데 이렇게 쉽게 풀 수 있는 것을 틀린게 너무 아쉽다..🤦🏻‍♀️ 풀이주어진 밭에서 자라는 참외의 수는 (육각형의 넓이 *..

문제https://www.acmicpc.net/problem/14719 여담좀 복잡하게 풀었다는 생각이 들어 다른 풀이를 참고했더니 역시 더 쉬운 방법이 있었다...^^ 시간 차이는 크게 나지 않았지만 다른 방법으로 풀어보니 확실히 내가 풀었던 방법이 더욱 복잡했다는 것을 깨달았다. 언제쯤 정석 풀이로 풀까..ㅎㅎ 그래도 풀었다는 것에 의의를 둬야지! 풀이간단한 버전이 정석으로 푸는 방법 같아서, 간단한 버전에 대해서만 설명을 진행하겠다. 빗물이 고이려면 현재 블록의 높이보다 높은 블록들로 둘러쌓여야 한다. 따라서 현재 블록의 왼쪽과 오른쪽을 탐색해야 한다. 즉, 빗물이 고이기 위해서는 다음의 조건을 모두 만족해야 한다.현재 블록의 왼쪽에 자신보다 높은 블록이 존재하는 경우현재 블록의 오른쪽에 자신보다 ..

문제https://www.acmicpc.net/problem/16926 여담저번에 풀려다가 복잡해 보여서 넘어갔던 문제..! 어려워 보였는데 차근차근 푸니까 나름 괜찮았다. 달팽이 문제와 비슷한 느낌?! 풀이회전을 1번하는 풀이 과정은 다음과 같다.회전시켜야 하는 그룹의 수(k) 구하기k = min(N, M) / 2min(N, M) mod 2 = 0이므로 가능한 것(0, 0), (1, 1), ... (k, k)를 시작점으로 선택해서 시계 반대 방향(↓ → ↑ ←)으로 회전하기시작점으로 돌아오면 반복을 종료하기우선 하나의 방향을 고정해서 배열을 회전시키다가, 범위를 벗어나거나 이미 기록한 위치면 회전 방향을 변경하기범위를 벗어난 경우: nx = N || ny >= M이미 기록한 위치: rotateArr[n..

문제https://www.acmicpc.net/problem/1713 여담문제를 읽은 후, HashMap과 우선순위 큐를 사용해야 되겠다고 생각했다. 그치만 중복된 경우를 우선순위 큐에서 어떻게 처리할지 헷갈려서 계속 고민했다. 결국 사진을 삭제할 때만 우선순위 큐를 사용하도록 했고, 다행히 이 방법으로 문제를 풀 수 있었다! 풀이이 문제는 주어진 조건에 따라 단순하게 구현을 하면 되는 문제이다. 주어진 조건을 정리하면 다음과 같다.사진틀에 게시될 수 있는 학생의 사진은 최대 N 개비어있는 사진틀이 없는 경우, 아래의 순서에 따라 게시된 사진을 삭제하고 새로운 사진을 게시하기추천받은 횟수가 가장 적은 학생의 사진 삭제학생들 중 게시된 지 가장 오래된 사진 삭제학생 정보와 그 학생의 추천 정보(게시 순서,..

문제https://www.acmicpc.net/problem/5212 여담두 번째 예제가 틀리게 나와서 문제를 다시 읽어보니 "지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다"라는 문장이 있었다. 이를 사용한 예제가 있어서 다행이지 아니었으면 놓칠 뻔했다..! 왜 자꾸 끝을 안 읽냐 끝이 중요하다고.. 풀이50년이 지나면 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠긴다고 한다. 즉, BFS 탐색을 통해 땅 주변에 위치한 바다의 수를 센 후 조건에 따라 지도를 변경해야 한다. 따라서 다음과 같은 과정을 수행하면 된다.땅의 위치를 큐에 저장한다.큐에서 땅의 위치를 poll() 한다.인접한 칸(=상하좌우)에 위치한 바다의 수를 구한다.이때, 지도를 벗어나는 칸도 모두 바다이다.바다인 경..

문제https://www.acmicpc.net/problem/2615 여담오랜만에 "틀렸습니다"를 많이 마주했다^^... 처음에는 육목을 고려하지 않아서, 두 번째는 "검은색 또는 흰색이 이겼을 경우에는 가장 왼쪽에 있는 바둑알의 가로줄 번호와 세로줄 번호를 순서대로 출력" 이라는 문장을 크게 신경 쓰지 않고 풀었기 때문이었다. 특히, 두 번째 반례를 찾아내지 못해서 많은 시간을 소요했다. 제발 문제를 풀기 전에 조건들을 다 정리하고 풀자... 🤦🏻 풀이N = 19이므로 이중 반복문을 사용해도 시간 초과가 발생하지 않는다. 따라서 완전탐색으로 같은 색의 바둑알이 연속해서 5개 나오는지 확인하면 된다. 이때, 2가지를 주의해서 풀어야 한다. 첫 번째는 같은 색의 바둑알이 연속해서 6개 나오는 경우이다...

문제https://www.acmicpc.net/problem/15787 여담처음에는 순수 구현으로 풀었다. 그치만 비트마스킹으로도 풀 수 있다길래 비트마스킹에 대해 간단하게 공부한 뒤 다시 풀었다. 이때까지 비트마스킹이 어려울 것 같아서 계속 미루고 있었는데, 이 문제를 통해 비트마스킹에 대해 알아볼 수 있는 기회가 되었다! 그리고 비트마스킹을 사용하면 더 빠른 시간, 더 적은 메모리를 사용하는 효과가 있다고 들었는데, 실제로 확실히 차이가 나는 것을 확인할 수 있었다. 비트마스킹을 잘 익히면 유용하게 써먹을 수 있을 것 같다!  풀이기차의 상태를 구한 뒤, HashSet을 이용해서 중복을 거른 후 저장된 수를 출력하면 된다. 기차의 상태를 구하는 방법은 구현과 비트마스킹, 총 2가지로 나눌 수 있다. ..

문제 https://www.acmicpc.net/problem/16937 여담 어떻게 풀지 감이 안 잡혀서 다른 분의 풀이를 참고했다. 양심상 풀이를 참고하더라도 완전히 코드를 따라 치지 않으려고 하기 때문에, 풀이 방식을 토대로 다시 생각하고 문제를 풀었다. 풀이를 보기 전에는 엄청 막막해서 풀기 싫었는데, 풀이를 보고 난 뒤에는 생각보다 쉽게 풀 수 있어서 다시 집중해서 풀었다. 이러한 일이 종종 있었는데 "어 이거 좀 어려운데..?"라는 생각이 들면 내가 풀지 못한다고 생각하고 더 이상 생각을 안 하는 것 같다. 진짜 안 좋은 습관인데... ㅎㅏ.. 진짜 6월 내로 꼭 고치자 풀이 이 문제에서 가장 중요한 포인트는 다음과 같다. 두 개의 스티커만 붙일 수 있으며, 두 스티커가 겹치면 안된다. 스티커..

문제https://www.acmicpc.net/problem/17276 여담시계 방향으로 회전하는 것과 반시계 방향으로 회전하는 것을 나눠서 풀었는데, 해당 블로그를 보고 반시계 방향을 따로 구현하지 않아도 된다는 것을 알았다..! 처음에 제대로 정리를 하지 않고 풀었더니 좌표를 이동시키는 과정에서 조금 헷갈렸고, 중간값에 -1을 해주지 않아서 조금 헤맸다..ㅎ  제발 문제를 풀기 전에 잘 정리하고 풀라고... 풀이이 문제는 단순 구현이기 때문에 문제에서 주어진 조건대로 구현하면 된다. 이때, 반시계 방향은 d + 360도 시계 방향으로 회전시키는 것과 같기 때문에 시계 방향으로 회전하는 것만 구현하면 된다.  문제에서 주어진 조건은 다음과 같다.X의 주 대각선을 ((1,1), (2,2), …, (n, ..

문제https://www.acmicpc.net/problem/22858 여담문제 이해만 하면 쉽게 풀 수 있는 문제였는데 문제 자체를 이해하지 못해서 시간을 좀 날렸다..ㅎㅎ 독해력 대체 무슨일이야풀이문제에 따르면 "Di번째 카드를 i번째로 가져오는 것이 셔플"이라고 한다. 개인적으로 이 문장을 이해하는게 조금 어려웠기 때문에 예제로 주어진 입력에 설명을 덧붙여보겠다. i가 1인 경우D1번째 카드를 1번째로 가져와야 함 (D[1] = 4)즉, 4번째 카드를 1번째로 가져와야 함S[1] = P[D[1]] = P[4] = 3i가 2인 경우D2번째 카드를 2번째로 가져와야 함 (D[2] = 3)즉, 3번째 카드를 2번째로 가져와야 함S[2] = P[D[2]] = P[3] = 5...i가 5인 경우D5번째 카드..