본문 바로가기

알고리즘 & PS69

[프로그래머스] 시소 짝꿍(Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우선 무게 배열 크기가 10만까지이다. O(n^2)일 경우, 100억으로 TLE 확정이다. (TIP : 1억까지가 확정) 즉, 반복문을 돌려서 풀 수 없는 문제이다. 잘 생각해보면, 무게당 몇명인지만 알면 인원수의 계산이 가능하다. 같은 무게일 경우에는 2명씩만 짝지으면 되고 다른 무게끼리는 인원수끼리 곱하는 경우의 수 문제. def solution(weights): answer = 0 weig.. 2023. 12. 31.
[프로그래머스] 리코쳇 로봇 (Lv 2) 솔직히 2단계 치고는 조금 어렵지 않나 싶다. https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS 문제이다. 이동 불가능할때까지 넣으면 된다. 핵심은 도달하는 순간 끝내고 답 내주면 된다. 그렇기에 도달 기록을 가진 visit에 아예 count를 저장해두면 편하다. 미끄러지는 것을 구현을 이렇게 복잡하게 할 이유는 없긴 하지만 직관적인 방향이라 이 방법대로 갔다. 정통적인 bfs 방법으로도 깔끔하게 될 거 같은데, 행간의 이해는 이게 더 .. 2023. 12. 31.
[프로그래머스] 무인도 여행 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기초적인 BFS 문제이다. 별 거 없이 방문여부, 현재 좌표, 최대 길이, 지도 전체 등등 다 넘겨버리면 그만. BFS 사용 자체가 간만이라 기초 연습문제로 몸풀기. # bfs 풀이가 필요함 from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(maps, i, j, n, m, visit): queue = deque.. 2023. 12. 27.
[프로그래머스] 숫자 변환하기 (Level 2) Problems https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Idea 일단은, 수학적으로 일반해를 구하는 것은 좋지 않습니다. 사실 언제 더해주는 것이 좋을지 모르니까요. 다만 중요한 아이디어는, 값은 무조건 단조적으로 strictly하게 증가한다 입니다. 따라서, 이미 목표값을 넘는 것에 대해서는 더 연산을 시도해볼 이유가 전혀 없습니다. 이에 따라, 특정 수에 n을 더하거나, 2배, 3배 했을 때 목표값인 y 이하인 값들만 담아주면 됩.. 2023. 12. 26.
[프로그래머스] Lv 2 2개 이하로 다른 비트 문제 풀이 링크 https://programmers.co.kr/learn/courses/30/lessons/77885 문제 설명 주어진 수보다 큰 수들 중 다음 조건을 만족하는 가장 작은 수 찾기 조건 : 2진법으로 바꿨을 때 1~2자리만 차이가 날 것. 풀이 방법 몇 가지 실험을 해보자. 1) 4의 경우, 100 -> 101 뒤의 자리만 바꾸면 된다. 맨 끝이 0이면 1을 하면 된다. 2) 5의 경우, 101 -> 2의 자리의 0을 바꾸고 일의 자리를 줄일 수 있다. 110 3) 11의 경우, 1011 -> 4의 자리를 1로 바꾸고, 그 다음에 2의 자리를 바꾸면 2개 차이가 나고, 가장 숫자 증감을 막았다. 4) 15의 경우, 1111-> 이것의 경우는 16의 자리를 1로 만들고, 증가를 가장 줄일려.. 2022. 1. 19.
[프로그래머스] Lv2 - 튜플 * 간만에 코딩테스트를 볼 일이 생겨서, 문제 풀이를 다시 연습해보았다. https://programmers.co.kr/learn/courses/30/lessons/64065 풀이법은 간단하다. 주어진 집합은 문자열로 한글자씩 들어오므로 숫자만 찾아준다. 수들이 몇개 있는지 세준다. 먼저 들어온 수부터 정렬을 해주면 깔끔하게 원하는 튜플을 얻게 된다. 다시 말해 맨 처음 들어 온 수가 가장 많은 개수만큼 들어올 것이니까. import string def solution(s): tuple = {} i = 0 while i < len(s): if s[i].isnumeric(): start = i end = start + 1 while s[end].isnumeric(): end += 1 cut = s[star.. 2021. 10. 8.

티스토리툴바