백준

문제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/16932 여담시간 초과가 진짜 많이 발생했다. 오랜만에 골드 BFS 문제를 푸니까 좀 어지럽다. 계속 쉬운 문제만 푸려고 하는 습관을 버려야지 진짜.. 암튼 처음에는 map[i][j] 값이 0일 때마다 BFS 탐색을 수행하면 되겠다고 생각했다. 그치만 위와 같이 시간 초과가 발생했다. 시간을 줄일 수 있는 방법으로 고쳐나갔는데도 계속 시간 초과가 발생해서 결국 다른 분의 아이디어를 참고했다.  항상 문제를 풀 때 시간 초과를 고려해서 푸는 습관을 들이도록 노력해야지..! 풀이위에서 언급했듯이, map[i][j]의 값이 0이면 BFS 탐색을 수행해서 모양의 최대 넓이를 구하는 방식을 사용하면 시간 초과가 발생한다. 따라서 다음과 같은 순서대로 ..

문제https://www.acmicpc.net/problem/9375 여담모든 조합을 계산하는 방법에 대해 계속 고민하다가 풀이를 참고했다. 복잡하게만 생각했었는데 풀이를 보고 이렇게 간단하게 계산할 수 있구나..? 하고 놀랐다.. 이럴 때마다 머리의 한계를 느껴.. 생각한 방법이 아닌 것 같으면 시야를 넓혀보는 습관을 가지자 제발! 풀이문제에 따르면, 같은 종류끼리는 입을 수 없다. 따라서 우선 종류별로 옷의 개수를 센다.headgear - 2개 (hat, turban)eyewear - 1개 (sunglasses) 그 후, 입을 수 있는 모든 방법의 수를 구해야 한다. 따라서 한 종류만 입는 경우, 두 종류만 입는 경우, ..., N 종류를 입는 경우와 같이 모든 경우를 계산해야 한다. 한 종류만 입는..

문제https://www.acmicpc.net/problem/2504 여담덧셈과 곱셈을 어떻게 나눠서 계산할지 몰라서 결국 풀이를 참고했다. 처음에는 이해가 안 돼서 계속 써보다가 분배법칙을 이용하면 된다는 말을 보고 이해했다.. 다시 풀 때도 풀이 로직을 알아서 쉽게 풀었지, 몰랐다면 끝까지 못 풀었을 것 같다. 다들 어떻게 이런 생각을 하는 걸까? 진짜 대단하다. 나도 분발해야지.. 풀이이 문제는 괄호를 기반으로 값을 구하는 것이기 때문에 스택을 이용해서 문제를 풀면 된다. 풀이 과정은 다음과 같으며, 자세한 내용은 코드를 참고하면 된다. 수학의 분배법칙을 생각하면 풀이 흐름을 쉽게 이해할 수 있을 것이다. (2 × (2 + 3 × 3) = (2 × 2) + (2 × 3 × 3)) ( 또는 [를 만나..

문제https://www.acmicpc.net/problem/16508 여담완전 탐색하면 for 문만 사용할 것이라는 고정관념에 사로잡혀 있었다. 그래서 결국 오늘도 풀이를 참고해서 풀었다..ㅎ 뭐 이렇게 계속 풀다 보면 실력이 늘겠지! 완탐은 재귀로도 풀 수 있다는 것을 기억하자! 풀이주어지는 책의 개수가 최대 16개이므로 완전 탐색과 백트래킹을 사용해서 풀이하면 된다. 이때, 현재 책을 고르는 경우와 고르지 않는 경우를 나누어서 탐색해야 하며, 자세한 내용은 다음과 같다.현재 책을 고르는 경우책에 포함된 알파벳의 배열 값을 1씩 증가하기count[book.name.charAt(i) - 'A']++total에 현재 책의 가격을 더해서 재귀 호출하기dfs(depth + 1, total + book.pri..

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

문제https://www.acmicpc.net/problem/10799 여담3개월 전쯤에 풀이를 참고하지 않고 풀었던 문제인데 이번에는 예전의 내 코드를 보고 풀었다... 나름 실력이 늘었다고 생각했는데 전에 풀었던 문제도 못 푸는 것 보면 그렇지 않은가 보다. 대체 코테 실력은 언제 늘까..? 너무 슬프다 풀이이 문제는 현재 문자가 (인 경우와 )인 경우를 나눈 뒤, 스택을 이용해서 문제를 풀면 된다. 현재 문자가 (라면 다음 문자를 통해 현재 문자가 쇠막대기의 오른쪽을 뜻하는지, 레이저를 뜻하는지 판별해야 한다.만약 다음 문자가 )라면 레이저를 뜻하므로 잘린 쇠막대기가 생기게 된다. 따라서 현재 잘린 쇠막대기의 수, 즉 스택에 담긴 수만큼 total에 더하면 된다. 다음 문자가 (라면 쇠막대기의 오른..