본문 바로가기

전체 글

 (256)
파이썬)숨바꼭질3 -BOJ https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 우선 이 문제는 BFS로 분류되어 있는 문제이기도 하고, "최소"시간을 구하는 문제이니 BFS가 효율적이라 생각했다. 하지만 어떻게 BFS를 구현할까 생각했다. from collections import deque n, k = map(int, input().split()) visit = [-1] * 100001 visit[n] = 0 q = deque() an..
파이썬) 가장 큰 정사각형 찾기 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 처음 접했을때 무조건 bfs혹은 dfs로 풀어야겠다 생각했다. 우선 가장 넓은 범위를 구하기 위해 bfs를 사용했다. 그리고 정사각형을 어떻게해서 찾을 것인지 생각해보았다. 단순이 상하좌우가 1인 것만 찾는다면 "정"사각형을 찾지는 못한다. 그래서 생각해낸 방법이 바로 위, 바로 왼쪽, 왼쪽 대각선이 모두 1인 경우를 정사각형이라 보고 그 왼쪽 대각을 q에 담는다. 아래는 위 생각을 그..
파이썬)수들의 합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 프로그래머스 코드 중심의 개발자..

티스토리툴바