728x90 Algorithm/PS24 BOJ - 23291번 어항 정리 문제 문제 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 이번 문제는 백준 사이트의 삼성 SW 역량 테스트 기출문제집에 있는 문제로, 구현 유형의 문제입니다. https://www.acmicpc.net/workbook/view/1152 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net 저는 어항을 접어서 시뮬레이션하는 과정이 막혀, 다른 분의 풀이를 참고해서 풀이하게 되었습니다. 풀이 과정 참고 https:.. 2023. 10. 6. BOJ - 2302번 극장 좌석 문제 (C++) dp를 이용한 풀이 회고 들어가면서.. 문제 설명을 처음 읽고, 전체 문제를 작은 단위의 문제로 쪼갠 뒤 그 결과를 조합해서 전체 문제를 해결해야겠다는 느낌은 받을 수 있었으나 아이디어가 명확하게 떠오르지는 않았습니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 그렇게 몇 번 풀이를 미루다가 오늘 이 문제를 다시 풀게 되었습니다. 다른 방식의 풀이를 보아하니 fibonacci 방식으로 수열이 이어지고, 이를 곱하는 결과로 계산을 한 풀이가 대부분이었는데, 저는 다른 방식으로 .. 2023. 8. 30. BOJ - 10282번 해킹 문제 Java를 이용한 dijkstra 풀이 요즘 코딩테스트에서 백 엔드 직군의 경우 Java 언어를 사용하도록 C++와 같은 언어 사용에 제약을 두는 분위기인 것 같아서 Java를 이용한 코딩테스트 연습을 이어가고 있습니다. 이번 문제는 그 중에서도 다익스트라(dijkstra) 알고리즘을 이용해 풀이해야 하는 문제였는데, 아무래도 오랜만에 푸는 유형이기도 하고, C++를 사용했을 때와는 다른 포인트에서 신경을 써야 하는 경우도 더러 있어 이번 기회에 정리해보려 합니다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 .. 2023. 8. 9. [Java] Softeer 슈퍼바이러스를 풀면서 (분할 정복과 이것 저것 정리) 들어가면서.. 요즘 Java 언어로 코딩테스트를 대비하기 시작하면서, Softeer에 등록된 연습 문제들을 풀며 자바 폐관 수련을 이어나가고 있습니다.. 그러던 중 오랜만에 분할 정복을 통해 풀어야 하는 문제를 풀이하는데, 풀이 방법을 떠올리지 못해서 분할 정복 풀이 방식에 대해 정리해 볼 겸.. 공부하면서 깨달은 여러 가지를 끄적여보려고 합니다. Softeer Level 3 슈퍼바이러스 문제 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 바로 이 문제가 글을 쓰게 만든 원인입니다. 문제 자체는 설명만 보면 굉장히 쉬워 보이지만, linear 하게 곱셈 연산을 N번 하게 되면 10의 16승 번의 연산을 진행하게 되어 제 시간을 절대 지킬 수 없습니다. 이러한 경우 이.. 2023. 8. 3. BOJ - 2638번 치즈, BFS를 이용한 풀이 정리 이번 문제는 BFS 혹은 DFS와 같은 그래프 탐색 알고리즘을 이용하여, 이후 상황에 대한 시뮬레이션 과정을 구현하는 문제였습니다. 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 위와 같이 주어진 모눈종이에서 외부 공기와 2개의 면 이상이 닿아있는 치즈는 녹는 상황에서 치즈가 모두 녹는데 걸리는 시간을 구하는 문제입니다. 간단한 그래프 탐색 문제처럼 단순하게 순회를 해서 해결되는 문제가 아니었고, 시간의 흐름을 측정할 수 있어야 했습니다. 그 이유는 그 시간대에서 녹을 위치에 있는 치즈가 모두 .. 2023. 2. 1. BOJ - 10868번, 최솟값 문제 Segment Tree를 이용한 풀이 이번 문제는 주어진 N개의 정수들에 대해 M번의 구간 최솟값을 묻는 질의에 올바른 답을 반환하는 알고리즘을 구현하는 것이 목표입니다. 물론, 구간의 최솟값을 확인하기 위해 linear한 탐색 방식을 취할 수 있겠지만, 이렇게 하는 경우 - worst case 100,000(N의 최댓값) x 100,000(M의 최댓값) = 10^12번의 연산 위와 같이 연산의 횟수가 너무 커서 시간 초과를 결과로 받게 될 것입니다. 따라서 지난번에 정리한 세그먼트 트리의 개념을 구간 합을 구하는 대신 최솟값을 구할 수 있도록 변형해서 이번 문제를 풀이하는 방식을 채택해 봤습니다. https://kkkdh.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%E.. 2023. 1. 18. 이전 1 2 3 4 다음 728x90
