썸네일 [프로그래머스] 가장 많이 받은 선물(파이썬, 구현, 2024 KAKAO WINTER INTERNSHIP) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. 변수 설정 문제 설명에 위와 같이 주고받은 선물과 선물 지수를 표로 나타내주는데, 이걸 그래도 구현하면 됩니다! table은 주고받은 선물의 개수를 담을 2차원 리스트이고, gift_index는 선물지수를 저장할 리스트입니다. answer는 다음 달에 각각 받을 선물 개수를 담을 리스트이다. 즉, answer 리스트에 있는 최댓값이 정답이 됩니다. table = [[0 for _ in range(len(friends))] for __ in range(len(friends))] gift_..
썸네일 [BOJ] #15486 퇴사2 (Python, Dynamic Programming, 시간 초과 해결) 🌱 문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 퇴사일과 각 일마다 상담에 소요되는 일수와 받을 수 있는 금액이 주어질 때, 얻을 수 있는 최대 이익을 출력하는 문제입니다. 백준 14501 퇴사 문제와 같은 문제인데, 시간복잡도를 줄여서 제출해야 맞출 수 있습니다. 🌱 풀이 1 - 시간 초과 dp = [0 for _ in range(n + 1)] for i in range(n): for j in range(i + meetings[i][0], n + 1): # i일 상담 진..
썸네일 [BOJ] #4179 불! (Python, BFS) 🌱 문제 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 🌱 풀이 지훈이가 미로에서 탈출할 수 있는 최소 거리를 구하는 문제인데, 불도 같이 사방으로 확산하기 때문에 움직이는 객체가 2개인 BFS 문제입니다. 1. 미로 정보와 지훈이와 불의 초기 위치 정보 우선 미로 정보를 graph에 저장합니다. 그리고 graph에서 지훈이의 초기 위치("J")와 불의 초기 위치("F")를 각각 jihoon_start와 fire_start에 저장합니다. h, w = map(int, input().split(..
썸네일 [BOJ] #2758 로또 (Python, Dynamic Programming) 🌱 문제 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 🌱 풀이1 - 백트랙킹 풀이(시간 초과) m개의 자연 수 중에서 n개를 고르는 문제라 당연히 백트랙킹이라고 생각하고 처음에는 백트랙킹으로 풀었습니다. def backtracking(n, m, lotto): if len(lotto) == n - 1: global answer answer += (m - (lotto[-1] * 2) + 1) return for i in range(lotto[-1]*2, m + 1): tmp = i for j in range(n - l..
썸네일 [BOJ] #15649) N과 M(1) (Python, Back tracking) 🌱 문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력 수열은 사전 순으로 증가 🌱 풀이 1) 파이썬 라이브러리 사용 백트랙킹 알고리즘의 대표적인 문제라고 해서 풀어본건데 문제 읽자마자 그냥 permutations 쓰면 되는 것 아님 ? ! ? 그래서 순열 뽑아주는 permutations 라이브러리 써서 제출하니까 정답,, 💙 from itertools import permutations n, m = map(int, input().spli..
썸네일 [BOJ] 11729 하노이 탑 이동 순서 (Python, Recursion) 🌱 문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 🌱 풀이 바킹독님의 알고리즘 강의 영상의 풀이법을 참고했습니다. 우선, 아래 그림처럼 n번째 원판을 1번 장대에서 3번 장대로 옮기기 위한 과정을 생각해보겠습니다. 1. n-1개의 원판을 1번에서 2번 장대로 옮긴다. 2. n번 원판을 1번에서 3번 장대로 옮긴다. 3. n-1개의 원판을 2번에서 3번 장대로 옮긴다. 이를 귀납적으로 설명하면, 원판 n-1개를 장대 a번에서 장대 b번으로 옮길 수 있다면, 원판 n개를 장대 a'에서 장대 b'..
썸네일 [프로그래머스] 광물 캐기 (Python, 구현) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작업을 끝내기까지 필요한 최소한의 피로도를 구하는 문제 광물을 모두 캐거나 곡갱이를 모두 사용하면 작업 끝남 어떤 광물을 어떤 곡갱이로 캐는지에 따라 소모되는 피로도가 다름 하나의 곡갱이로 5개의 광물을 캘 수 있음 🌱 풀이1 완전 탐색 → 시간 초과 처음에는 곡갱이(picks)의 개수가 최대 15개 이고, 광물(minerals)의 길이는 최대 50이라 완전탐색으로 풀 수 있겠다고 생각하였습니다. 왜냐하면 곡갱이 1개당 광물 5개를 캘 수 있으므로 최대로 필요한 곡갱이 수는 10개입니다. 또, 곡갱이..
썸네일 [프로그래머스] 과제 진행하기(Python, Stack, Implementation) 🌱 문제 https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. 문자열로 받는 시간 정보를 처리 후, 정렬 for plan in plans: hh, mm = plan[1].split(":") plan[1] = int(hh) * 60 + int(mm) plan[2] = int(plan[2]) plans.sort(key=lambda x: x[1]) plans에 시작 시간과 소요 시간이 모두 문자열로 주어지므..
썸네일 [프로그래머스] 전력망을 둘로 나누기 (Python, BFS, 완전탐색) 🌱 문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 n은 2 이상 100 이하인 자연수이고 wires는 길이가 n-1인 2차원 배열로, 시간복잡도가 $O(100^2)$을 넘지 않으므로 (n-1 배열 탐색($O(N)$) * BFS 시간복잡도($O(N)$)) 완전 탐색을 이용해서 풀이합니다. 1. 전력망(graph) 정보를 2차원 리스트 형태로 표현하기 graph = [[] for _ in range(n + 1)] for wire i..
썸네일 [프로그래머스] 퍼즐조각 채우기 (Python, BFS, 구현) 🌱 문제 BFS/DFS 문제이지만 개인적으로 BFS 찔끔 쓰고, 완전 빡쎈 구현인 것 같았던.. 문제입니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. game_board의 빈 공간과 table의 퍼즐 정보를 저장 우선, game_board에서 빈공간과 table에서 퍼즐들의 정보를 알아야 합니다. 즉, game_board에서는 0의 위치, table에서는 1의 위치를 알아야합니다. game_board의 인접한 0들은 하나의 퍼즐이 들어갈 수 있는 하나의 빈공간으로 취급하고, table에서 인접한 1은 하나의 퍼즐이므로 BFS 알고리즘을..
썸네일 파이썬으로 구현하는 다양한 소수 판별 알고리즘 (완전탐색부터 에라토스테네스의 체까지) 파이썬으로 소수를 찾는 알고리즘 3가지에 대해 알아봅시다. 1. 완전 탐색 방법 첫번째 방법은 완전 탐색 방법으로 소수인지 판별하는 방법입니다. 소수는 1과 자기 자신만을 약수로 갖는 수이기 때문에 2부터 자기 자신보다 1작은 수까지 모두 나누어보며 나누어 떨어지는지 확인하면 소수인지 알 수 있습니다. # 1. 완전 탐색 방법 def is_prime_number(x): for i in range(2, x): if x % i == 0: return False return True 이 알고리즘을 사용하면 시간복잡도는 $O(N)$입니다. 2부터 N-1까지 반복문을 돌면서 판별하기 때문입니다. 2. 제곱근까지만 확인해보자 두번째 방법은 약수끼리 대응시켜 곱했을 때 결국 자기 자신이 나온다는 점을 이용한 알고리즘..
썸네일 [BOJ] #1697 숨바꼭질 (Python, BFS, 메모리 초과 문제 해결) 💡 문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💡 풀이 처음에는 단순히 간단한 BFS 문제라고 생각하여 아래와 같이 코드를 작성했더니 메모리 초과가 났습니다. 그 이유는 n과 k가 100,000까지 될 수 있는데, while문을 돌면서 queue가 계속 3배가 되기 때문입니다. # !/usr/bin/env python # -*- coding: utf-8 -*- # boj 1697 숨바꼭질 import sys from collections import deque input ..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바