썸네일 [프로그래머스] 퍼즐조각 채우기 (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 ..
썸네일 [프로그래머스] 아이템줍기 (Python, Graph, BFS) 💡문제 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 아래와 같이 여러개의 사각형 정보(좌하단 좌표와 우상단 좌표)가 주어졌을 때 테두리를 따라 다각형 모양 지형이 만들어지고, 그 위에 캐릭터의 위치와 아이템의 위치가 주어졌을 때 아이템까지의 최단 거리를 구하는 문제입니다. 💡풀이 문제를 풀기 위해서는 두가지 과정이 필요합니다. 1. 테두리를 따라 게임 맵을 만들어야하고, 2. 그 테두리를 따라 최단거리를 구하면 됩니다. ..
썸네일 [프로그래머스] 문자열 계산하기 (Python, 문자열) 👩🏻‍💻 문제 https://school.programmers.co.kr/tryouts/85890/challenges 👩🏻‍💻 풀이 문자열로된 계산식이 "숫자(공백)연산자(공백)연산자.."로 매우 정형화되어있어 어렵지 않게 풀 수 있는 문제입니다. 계속 pop()해가면서 끝까지 계산! 👩🏻‍💻 코드 def solution()# !/usr/bin/python3 # -*- coding: utf-8 -*- # programmers 문자열 계산하기 def solution(my_string): str = my_string.split(" ") answer = int(str.pop(0)) while str: tmp = str.pop(0) if tmp == "+": answer += int(str.pop(0)) eli..
썸네일 [프로그래머스] 옹알이(1) (Python, 문자열) 🌱 문제 https://school.programmers.co.kr/tryouts/85889/challenges 🌱 풀이 babbling의 단어가 "aya", "ye", "woo", "ma"로 완벽하게 만들어질 수 있어야 하므로 맨 앞부터 4개의 옹알이 중 하나라도 일치하는 것이 있는지 검사합니다. 검사하면서 4개의 옹알이 중 하나와 일치하는데, 남은 글자가 해당 옹알이의 글자 수와 일치한다면 babbling의 단어가 4개의 옹알이 단어들로 모두 만들어진다는 것을 의미하므로 answer를 1 증가시킵니다. 🌱 코드 # !/usr/bin/python3 # -*- coding: utf-8 -*- # programmers 옹알이 def solution(babblings): answer = 0 for babbl..
썸네일 [프로그래머스] 공원 산책 (Python) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 이 문제는 단순 구현 문제로, 문제에서 요구하는 설명을 그대로 코드로 작성하면 해결할 수 있는 문제입니다. 우선, S의 위치를 저장합니다. 이동하는 명령들(routes)을 하나씩 돌면서 해당 명령을 수행할 수 있는지 검사합니다. 해당 명령을 수행할 수 있는지 검사할 때에는 한 칸씩 이동하며 범위를 벗어나지 않는지, 장애물이 있지 않은지 검사해야 하기때문에, 한칸씩 이동하는 좌표값을 저장할 수 있는 변수(nx, ny)를 사용하였습니다. 중간에 break되지 않고 해당 명령을 끝까지 수행할 수 ..
썸네일 [BOJ] #2437 저울 (Python, Greedy) 🌱 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 🌱 풀이 0. 접근하기 문제 예시에서 추가 1, 1, 2, 3, 6, 7, 30일 때, 정답이 21입니다. 이를 추의 배열이 [1, 1, 2, 3, 6, 7, 30]일 때 앞에서부터 차례대로 더한 값의 배열은 [1, 2, 4, 7, 13, 20, 50]입니다. 정답이 21임을 아는 상태에서는 1-20까지의 무게는 무조건 만들 수 있다고 판단할 수 있습니다. 이 때 1부터 20까지는 무조건 만들 수 있으므로 31부터 50까지도 무조건 만들 수 있음을 알 수 있습니다..
썸네일 [BOJ] #11000 강의실 배정 (Python, 우선순위 큐, 그리디) 🌱 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🌱 풀이 우선순위 큐 자료구조를 활용하여 푸는 그리디 문제입니다. 1. 시작 시간을 기준으로 정렬하기 class_times = [list(map(int, input().split())) for _ in range(n)] class_times.sort(key = lambda x: x[0]) 우선 순위 큐에 삽입 하기 이전에 우선, 입력 받은 강의 시간을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다. 그 이유는 아래 예시를 통해서 설명하도록 하겠습니다. 아래에서 정렬 없이 큐에 삽입한 경우, 첫 번째..
썸네일 [BOJ] #16724 피리 부는 사나이 🌱 문제 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 🌱 풀이 0. 기본 로직 safe_zone = [] idx = 1 for i in range(n): for j in range(m): if visited[i][j] == False: dfs(board, i, j, visited) idx += 1 방문하지 않은 노드를 돌면서 dfs 탐색을 합니다. dfs 함수에서 무조건 하나의 사이클이 찾아지므로 dfs함수를 수행하고 나오면 idx 값을 증가시킵니다. 1. dfs 함수 d..
썸네일 [BOJ] #1027 고층 건물(Bruteforce, Python) 🌱 문제 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 🌱 풀이 1. 기울기 계산 def calc_gradient(x1, y1, x2, y2): if x1 == x2: return 0 gradient = (y2 - y1) / (x2 - x1) return gradient 건물이 보이는지 여부는 기울기에 따라 결정되므로 기울기를 계산하는 함수를 작성합니다. 1. 완전탐색 (Bruteforce) results = [] for idx in range(len(buildings)): cnt = 0 min_gradie..
썸네일 [BOJ] #1450 냅색문제 (이분 탐색, Python) 🌱 문제 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 🌱 풀이 1. 기존 Bruteforce로 풀 수 없는 이유 이 문제는 물건의 개수(n)가 최대 30개 주어집니다. 만약 이 문제를 완전 탐색으로 푼다면 물건 하나하나마다 넣을지 안넣을지 모든 경우를 세면 최대 $2^{30}$번의 연산을 하게 되는데, 이는 10억이 넘는 값으로 무조건 시간 초과가 발생합니다. 기존 Bruteforce로 푼다면 코드가 다음과 같을 것입니다. import sys from itertools import combinations ..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바