본문 바로가기

알고리즘 & PS69

[프로그래머스] n^2 배열 자르기 (Lv 2) 1차 시도배열을 펼치는 방법으로 접근하였다. 하지만 TLE!n이 너무 크다. 이런 방식으론 안되지만, 1차 풀이에서 아이디어를 얻을 수 있다.def solution(n, left, right): array = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): array[i][j] = max([i, j]) + 1 # 2D -> 1D 로 펼치는 방법 알아두자! array_join = [] for cur_arr in array: array_join += cur_arr return array_join[left:right+1]2차 .. 2024. 10. 28.
[프로그래머스] 석유 시추 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr bfs 극복중이다.이번 문제의 핵심은, 연결된 부분의 넓이를 구하는 방법이다."새로 만나는 좌표"의 개수를 세 주면 되는 방식이다.따라서, 시작점도 not_visited를 항상 체크해줘야 한다. 잊지 말자. 아, 그리고 연결성을 활용하여 석유 시추하는 부분의 col 값의 최소/최대만 가져와도 나머지는 모두 연결성이 보장되어 있어 그 부분의 석유 값을 추가해주는 방식으로 구현하였다. from collections import dequemv_li.. 2024. 10. 27.
[프로그래머스] 거리두기 확인하기 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/81302# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 아, 진짜 너무 심각하게 bfs가 약하다.심지어 내가 인턴 코테로 푼 기출인데... 왜이리 헤맨건지... 진짜 코테 연습 많이 해서 감 좀 올려야겠다.아마 당시에는 다른 방법으로 그냥 계산때린거 같다.조금 쓰는 법을 바꿔서 돌면 안되는 케이스를 continue로 빼줘야 이해하기 쉬울거 같다.from collections import dequemv_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]def bfs(place.. 2024. 10. 27.
[프로그래머스] 마법의 엘리베이터 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이의 핵심은 "5"에 있다. 기본적으로 올림 또는 내림이다. 그런데, 5의 경우는 에 영향을 미친다.다시 말해, 십의자리가 5보다 크거나 같을  경우, 올림을 하면 다음 번에 올림을 하며 버튼 누르는 횟수를 줄이게 된다.십의 자리가 5보다 작을 경우, 버림을 하면 다음번에 버림을 하며 버튼 누르는 횟수를 줄이게 된다.이를 고려해야 모든 경우를 고려, 매 턴마다 최저 턴수로 넘기는 그리디한 선택을 할 수 있다.약간의 수리사고력이 필요한 문제.. 2024. 10. 27.
[프로그래머스] 구명보트 코테 다시 복습중! 11월달에 코테를 볼 수도 있어서. 감각 다시 끌어올리는 중이다.https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 어렵게 생각할 것 없는 그리디+투포인터 문제다.무거운 놈의 빈 자리에 가벼운 놈을 태울 수 있는가를 체크한다.즉 무거운 애 + 가벼운 애 pair가 최솟값임은 명백하다.투포인터를 쓰면 매우 깔끔하게 O(n)으로 해결 가능한 쉬운 문제다.아, 배열 정렬 하고 들어가는건 잊지 말자. 그거땜에 사실 O(nlogn)이다. d.. 2024. 10. 21.
[프로그래머스] 과제 진행하기 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/176962# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Idea/Tip.기본적으로 스택을 이용한다. 단, 스택에서 뺄지 안 뺄지를 시간을 통해 결정해야 한다.이를 위해 현재 시간을 계산하는 변수를 이용해야 한다. 다음 과제가 오기까지 충분한 시간이 있을 경우, 남은 과제를 한다.과제는 없는데 시간이 더 남으면, "다음 과제 시간으로" 바로 넘어가야 한다. 아니어도 그 시간을 간다.즉, 다음 과제 전까지의 과제 처리 여부와 상관없이 현재 시간만 조절해주.. 2024. 10. 16.

티스토리툴바