본문 바로가기

전체 글

 (254)
파이썬)수들의 합5 -BOJ https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 처음 이 문제를 보았을때, dp를 사용해야 하나 싶었다. 그러나 dp로는 단순히 연속된 수들만 구할 수 있었고, 그 다음으로 생각한 것이 브루트 포스였다. 하지만 n이 10,000,000개라는 점에서 브루트 포스 또한 초과가 나올 것이 분명했다. 그래서 투포인터로 풀어야겠다 생각했다. n = int(input()) arr = [i for i in range(1, n+1)] a..
파이썬) https://www.acmicpc.net/problem/1963 import sys, math from collections import deque def findPrime(): # 에라토스테네스의 체(제곱근 범위까지 조사) for i in range(2, 100): # 소수인 상태에서 소수의 배수를 체크해줘야 함 if prime[i] == True: # 소수의 배수 체크 for j in range(2*i, 10000, i): prime[j] = False def bfs(): q = deque() q.append([start, 0]) visited = [0 for i in range(10000)] visited[start] = 1 while q: now, cnt = q.popleft() strNow =..
파이썬)광물캐기 -프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/172927# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(picks, minerals): answer = 0 pickable_minerals = minerals[: sum(picks) * 5] tools_len = 0 for i in picks: tools_len += i * 5 # print(tools_len,len(minerals)) # print(tools_len < ..
파이썬) 과제 진행하기 https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(plans): answer = [] q = deque() for i in range(len(plans)): # 시간을 분으로 변환 = 시간 * 60 + 분 time = plans[i][1].split(':') new_time = int(time[0]) * 60 + int(time[1]) plans[i][1] = new_..
파이썬) 택배 배달과 수거하기 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(cap, n, deliveries, pickups): deliveries = deliveries[::-1] pickups = pickups[::-1] answer = 0 have_to_deli = 0 have_to_pick = 0 for i in range(len(deliveries)): have_to_deli+= deliveries[i] have_to_pick += pi..
파이썬)이모티콘 할인행사 https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from itertools import product def solution(users, emoticons): answer = [0,0] sales = [10, 20, 30, 40] # 이모티콘의 할인율 for case in product(sales, repeat=len(emoticons)): plus = 0 money = 0 for user in users: total = 0 for idx, ..
파이썬)리코쳇 로봇- 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(board): answer = 0 R = len(board) C = len(board[0]) rx, ry = 0, 0 for i in range(R): for j in range(C): if board[i][j]=='R': rx, ry = i, j dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] de..
파이썬) 인구이동 -BOJ https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이 문제를 읽었을 때 좀 쉬워보였다. 그러나 머지않아 문제를 발견했다. bfs를 통해 얻은 값들 중 최초 visit[i][j] == False인 i,j값을 어떻게 할까, 또 visit[i][j] == False지만 주변국가들이 모두 만족하지 않았을 때였다. 그러나 고민은 곧 해결되었다. 애초에 contries 배열에 i,j를 append시키고 만약 contries의 길이가 1이라면 ..
파이썬) 게임 -BOJ https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net import math X, Y = map(int, input().split()) Z = (Y * 100) // X if Z >= 99: print(-1) else: right = X left = 1 answer = 0 while left
파이썬)음식물 피하기-BOJ https://www.acmicpc.net/problem/1743 from collections import deque n, m, trash_count = map(int, input().split()) arr = [[0 for _ in range(m)]for _ in range(n)] visit = [[False for _ in range(m)]for _ in range(n)] trash_position = deque() for i in range(trash_count): x, y = map(int, input().split()) x -= 1 y -= 1 trash_position.append((x, y)) arr[x][y] = 1 max_trash = 0 dx = [0, 0, -1, 1] dy = [-..
파이썬) 치즈 - BOJ https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 어디서 많이 본 문제다 생각했다. 바로 같은 이름을 가진 백준에 있는 "치즈"라는 문제다. https://junheelab.tistory.com/105 파이썬)치즈 junheelab.tistory.com 이번 치즈 문제도 비슷하다. 하지만 전에 푼 문제와 다른 점이있다면, 공기(0)와 2면 이상이 접촉한 경우에만 치즈가 녹아없어진다. from copy import deepcopy fr..
파이썬) 케빈 베이컨의 6단계 법칙 BOJ https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net from collections import deque n, m = map(int, input().split()) arr = [[] for _ in range(n+1)] answer = [99998999999999999999999999999999999999999999, 0] # for i in range() for i in range(m): a, b ..
파이썬) 퇴사 -BOJ https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 이해는 상당히 쉽다. 읽어보면 한 번에 이해가 되므로 문제 이해는 건너 뛰고, 이를 어떻게 풀 것인가를 나는 곰곰히 생각해보았다. 우선 n은 15 이하이다. 즉, 브루트포스를 이용해 풀어도 손쉽게 풀 수 있는 문제이다. 하지만 어떤 상담을 선택하고, 어떤 상담을 선택하지 않을지에 대해 다시 생각했다. 브루트 포스와 선택과 선택 안함. 이 문제는 어디선가 보았던 문제와 상당히 비슷했다. https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자..
파이썬)A -> B -BOJ https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net from collections import deque a, b = map(int, input().split()) r = 1 def bfs(a, b): q = deque() q.append((a, 1)) while q: a, count = q.popleft() if a == b: print(count) return if a * 2
파이썬)고양이 카페- BOJ https://www.acmicpc.net/problem/28353 28353번: 고양이 카페 첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 5\,000;$ $1 \leq K \leq 10^9)$ 둘째 줄에는 각 고양이의 무게를 의미하는 $N$개의 정수 $w_1, w_2, \dotsm, w_N$이 공백으로 구분되어 주어 www.acmicpc.net n, k = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() cnt = 0 start = 0 end = n-1 while start < end: cat_1 = arr[start] cat_2 = arr[end] if cat_1 + c..

티스토리툴바