본문 바로가기

🍒공부/알고리즘17

[백준] 1647번 : 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 전체 그래프를 2개로 나누는데 그 나눠진 그래프 안에서는 서로 다 연결이 돼 있어야 한다는 얘기..... (근데 대체 원숭이🙊 얘기는 왜 나온거지???) 📖접근 방법 크루스칼 알고리즘을 이용해서 최소신장 트리를 하나 만듬 그 중에서 가장 비싼 간선을 하나 없앤다 (그래야 최소 비용이 되니까!) 그러면 자연스럽게 그래프가 2개로 분리된다! 그리고! import .. 2021. 9. 25.

[프로그래머스 Lv.2] 2개 이하로 다른 비트 https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 처음에는 2진수로 바꿔서 1과 0의 갯수를 세는 방법을 시도했으나... 예제는 통과하는데 제출했더니 점수도 엉망이고 시간초과도 나서 비트로 푸는 법을 알아봤다ㅠㅠ 🙋‍♀️ 작성한 코드 코드 내의 주석은 지운 상태! 위에 설명이 있으니까용... 더보기 def solution(numbers): answer = [] def cal(n): last = (~n) & (n+1) #최하위비트 0이 있는 위치 return (n|last) & ~(last>>1) for n in numbers: if n%2 == 0 : answer.append(n.. 2021. 5. 18.

[프로그래머스 Lv.3] 기지국 설치 programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr ceil이 시간을 많이 잡아먹는다는 글을 봐서 그걸 고쳐주었으나...! 역시 시간초과가 떴다. 실패한 코드 (시간초과) → 전파가 닿지않는 아파트를 하나하나 배열에 추가해준 것이 문제였다! 더보기 def solution(n, stations, w): answer = 0 apts = [0] * (n+1) for s in stations: # print(s) .. 2021. 4. 28.

[프로그래머스 Lv.3] 숫자 게임 programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 처음에는 그냥 sort해서 풀면 되는거 아닌가? 하다가 효율성에서 걸리겠지? 하고 걍 내봤는데 답도 틀렸다고해서 ? 싶었다ㅠㅠ 계속 오름차순으로 정렬하려고 한게 삽질의 원인인듯🤔 푸는 방법을 검색해봤더니! 1. min(A) >= max(B) 이면 하나도 이긴게 없다는 말이니까.. 바로 0 리턴 2. A와 B를 내림차순 정렬. A[0]와 B[0]를 비교하여 지거나.. 2021. 4. 27.

[프로그래머스 Lv.3] 풍선 터트리기 programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 처음에는 이걸 어쩌라는거야.. 싶었다😂 그래서 일단 한번 검색해서 접근법을 알아낸 후 계산해봤다...!!! 접근법은 지금 숫자를 기준으로, 왼쪽/오른쪽에서 최솟값을 확인하여 비교하는 방법이다. 입출력예제 2를 보면 표처럼 정리 할 수 있다! 왼쪽, 오른쪽의 최소값을 저장할 small_nums 라는 배열을 생성한 다음 for문을 돌면서 하나씩 넣어준 것이다. 58과 -68을 예로 들어 설명하면... 58을 기준으로 왼쪽(-16, 27, 65, -2) 에서 최소값은 -16이고, 오른쪽(.. 2021. 4. 20.

이전 1 2 3 4 다음

티스토리툴바