728x90 Algorithm36 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. LIS (Longgest Increaseing Subsequence)에 대해 이것 저것 정리 글을 쓰게 된 이유 이번 글은 친구의 "이 문제 LIS로 풀어야 하는 거 아니야??"에서 시작되었습니다. 해당 문제를 보니까 2년 전에 풀이한 문제이더라고요... (그리고 LIS가 무슨 뜻인지도 까먹고 있었습니다.) 문제랑은 상관이 없는 알고리즘이었으나, LIS(가장 긴 부분 수열 구하기) 알고리즘을 다시 공부하면서 기존에 알고 있었던 dynamic programming 방식(O(N^2))과 이를 시간 복잡도 측면에서 이분 탐색을 가미해 개선한 방식(O(NlogN))을 정리해보려 합니다. LIS가 대체 무엇인가?? 먼저 LIS에 대해서 간단히 정리해야 될 것 같습니다. LIS는 Longgest Increasing Subsequence의 약자로, 가장 긴 증가하는 부분 수열을 의미합니다. 간단하게, 어떤 .. 2023. 8. 24. 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. 이전 1 2 3 4 ··· 6 다음 728x90
