본문 바로가기

2025/12

Algorithm/프로그래머스 2025. 12. 5. [프로그래머스/Python] PCCP 기출문제 2번 / 석유 시추 문제 PCCP 기출문제 2번 - 석유 시추 풀이 💡 입력들의 범위를 살펴보자 “시추관을 세울 열 j”를 0부터 m−1까지 반복 (i, j max 500)각 열마다 “이 열을 통과하는 석유 덩어리들을 찾기 위해 전체 땅을 BFS/DFS로 스캔” — 즉, O(n·m) 탐색→ 총 연산 복잡도: O(m·(n·m)) = O(n·m^2)n = m = 500인 경우 연산량: 500×(500×500)=125,000,000 번 (1.25억) 뻔한 BFS 문제를 주어진 연산량 안에서 어떻게 각 열마다 석유 덩어리의 양을 더해줄 것인가?land를 순회하면서 석유 덩어리를 발견하게 되면 덩어리의 크기를 세어주는데,이 과정에서 덩어리가 포함하고 있는 열들을 몽땅 구한 뒤, 각 열들에 대해 덩어리 크기를 누적해준다. 💡..
Algorithm/프로그래머스 2025. 12. 4. [프로그래머스/Python] PCCP 기출문제 1번 - 붕대 감기 문제 PCCP 기출문제 1번 - 붕대 감기 풀이 💡 입력들의 범위를 살펴보자 전반적으로 숫자 범위가 작으니 구현에만 집중해도 될 것 같다는 생각이 들었다.구현 문제는 오랜만이라... 한 시간 안에 풀려고 노력했다. 처음에는 time = 0으로 두고, 1초씩 증가시키면서 아래 링크에 있는 풀이처럼 풀려고 했는데연속 성공이랑 공격 여부 관리가 귀찮아질 것 같아서 최대한 attacks 배열로만 접근할 수 없을까(공격을 당하는 시간만 고려)... 고민하게 되었다.https://school.programmers.co.kr/questions/86486 첫 번째 시도TC 반만 맞고 반은 틀렸다.놓친 부분이 어디일까.... " t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. ..
Algorithm/프로그래머스 2025. 12. 3. [프로그래머스/Python] PCCP 기출문제 2번 - 퍼즐 게임 챌린지 문제 코딩테스트 연습 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 | 프로그래머스 스쿨 풀이 💡 입력들의 범위를 살펴보자1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,0001 ≤ diffs[i] ≤ 100,0001 ≤ times[i] ≤ 10,0001 ≤ limit ≤ 10^15 level 값의 범위가 되는 diffs 배열의 크기가 100,000이었기 때문에 O(n log n)으로 풀어야겠다고 생각했다.이제서야 좀 시간복잡도 관련된 지능이 생긴 것 같다.특정 범위 안에서 '숙련도의 최솟값'을 찾는 문제라서 이분 탐색을 바로 떠올렸다.(백준에서 여러 번 탐독한 보람이 있었따 v) 풀다 보니 "퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev..

티스토리툴바