본문 바로가기

Data Structure & Algorithm

[Programmers] 백준허브 이미 풀었던 문제 등록 자동화 백준허브에 프로그래머스에서 이미 풀었던 문제를 올리기 까다로워서, 자동화 프로그램을 만들어보았다. 사용법은 다음과 같다.1. 프로그래머스 로그인2. 상단 메뉴 [코딩테스트] 클릭3. 필터링에서 "상태"에 "푼 문제" 체크4. 개발자도구 열기 (윈도우는 F12, 맥북은 cmd + shift + i)5. [콘솔] 탭 선택6. 아래 코드 붙여넣고 엔터7. 다될때까지 기다리기 async function waitForPageLoad(newPage) { return new Promise((resolve) => { const interval = setInterval(() => { if (newPage.document.readyState === 'complete') { .. 더보기
[BOJ] 백준허브 이미 풀었던 문제 등록 자동화 백준 허브를 뒤늦게 알아버린 1인.. 이미 1000문제 넘게 풀어서 언제 다 추가하지 했는데, 다행히 이미 풀었던 문제의 "내 제출" 페이지에 들어가면 자동으로 올려준다고 한다! 이를 이용해서 파이썬 자동화 코드를 짜보았다.import webbrowserimport timeuser_id = '' // 본인 아이디solved_problems = '' // 해결한 문제 목록 (공백으로 구분)delay_time = 0.3 // 간격 시간problem_arr = solved_problems.split(' ')for p in problem_arr: webbrowser.open_new(f'https://www.acmicpc.net/status?from_mine=1&problem_id={p}&user_id.. 더보기
[BOJ] [2563] 색종이 (Python) 내 해답) canvas = [[0 for _ in range(100)] for _ in range(100)] # 0으로 채워진 도화지 for _ in range(int(input())): x, y = map(int, input().split()) for i in range(x, x+10): for j in range(y, y+10): canvas[i][j] = 1 # 기준 지점으로부터 가로 세로 10만큼 1로 채우기 print(sum([sum(line) for line in canvas])) # 다 더하기 0으로 채워진 가로 세로 길이가 100인 도화지(2차원 배열)을 준비하고, 입력 받은 지점을 기준으로 가로 세로 길이가 10인 사각형 부분에 색종이(1)를 붙인다. 그리고 마지막에 1인 부분만 전부 세.. 더보기
03. 그리디 알고리즘(Greedy Algorithm) Q. 주어진 거스름돈을 가장 적은 수의 동전으로 거슬러주는 알고리즘을 고안하라. (이후로 후보군 집합을 C, 해결책 집합을 S라고 명명함.) A. 그리디 알고리즘에서 필요한 세 가지 함수 1. Select() - 조건에 맞는 원소를 선택 2. Feasible() - S 집합에 들어갈 수 있는지 판단 3. Solution() - 문제가 해결되었는지 확인 * 최적화 문제 대상 함수 $f$를 제약 조건(Condition or Constraint) C에 맞게 최적화(대체로 최대화 또는 최소화) 하는 것. 가능(feasible)한 해결책 : C를 만족하는 아무 결과 최적의 결과 : 대상 함수를 최적화하는 해결책 * 그리디 알고리즘(Greedy Algorithm) 현재 갖고 있는 정보만을 가지고 결정을 내리는 것... 더보기
02. 알고리즘 분석 알고리즘의 효율성 분석을 위한 만능 공식은 없음. 대신, 몇몇 기본적인 방법들이 존재함. 알고리즘 분석은 대체로 안에서 바깥쪽으로 진행됨. 1. 순차적 규칙(Sequencing Rule) P1과 P2가 알고리즘의 두 부분이라고 한다면, 각각은 하나의 명령어이거나 복잡한 서브-알고리즘일 것임. 추가로, t1과 t2를 P1과 P2의 실행에 걸리는 시간이라고 했을 때 순차적 규칙에 의하면, P1과 P2의 실행에 거리는 시간은 단순히 t1+t2임. 최대 규칙(Maximum Rule)에 따르면, 이 시간은 θ( max{t1, t2} )임. 2. for 반복문 for i ← 1 to m, do P(i); 이 반복은 큰 알고리즘의 일부이고, 사이즈 n짜리 인스턴스에서 동작함. 2-1. P(i)에 걸리는 시간이 i와 .. 더보기
01. 알고리즘이란 * 문제와 해결방법 2 + 3 = ? 3 + 5 = ? 5 + 2 = ? ... 위와 같은 상황일 때, 알고리즘의 측면에서 문제는 한 개임. 일반적으로 말하는 문제를 여기선 인스턴스라고 함. 즉, 위에는 인스턴스가 3개인 것임. 해당 과목에서 "문제(Problem)"와 "인스턴스(Instance)"는 구분되어 사용됨에 유의할 것. - 한 문제는 많은(대체로 무수히 많은) 인스턴스를 가짐. 예를 들어, 두 양의 정수가 주어졌을때, 최대공약수(GCD, Greatest Common Divisor) 구하기라는 "문제"가 있을 때, 461,952 와 116,298 의 최대공약수를 구하기 (정답 = 18) 와 같은 "인스턴스"가 얼마든지 생성 될 수 있음. * 일반화 문제 P ) f : D -> R 인 f를 구해라.. 더보기
[BOJ] [25314] 코딩은 체육과목 입니다 (Python) 내 해답) print("long "*(int(input())//4)+"int") long 한번에 4바이트라고 했으니, 입력으로 들어온 숫자를 4로 나눈 몫 만큼 "long"을 출력하고 뒤에 "int"를 붙여주면 된다. 리뷰) 오랜만에 들어가니 단계별로 풀어보기에 새로운 문제들이 생겼다. 길고 이쁘게 코딩해도 되지만, 빨리 빨리 하고 넘어가고 싶어서 숏코딩으로 풀어보았다. 더보기
[BOJ] [5557] 1학년 (Python) 내 해답) import sys; ip = sys.stdin.readline N = int(ip()) nl = list(map(int,ip().split())) #입력 받기 before = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0,13:0,14:0,15:0,16:0,17:0,18:0,19:0,20:0} after = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0,13:0,14:0,15:0,16:0,17:0,18:0,19:0,20:0} before[nl[0]] = 1 #초기 세팅 for i in range(1,N-1): #N번 반복 q = [k for k,v in before.items() if .. 더보기

티스토리툴바