Kim Jisong

I am an amazing person.

Backjoon Algorithm 2-1: Greedy

Introduction

그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다.

어떠한 문제 상황에 가장 최적인 방법을 찾는 것.

basic

동전

https://www.acmicpc.net/problem/11047

import sys
input = sys.stdin.readline

N, K = map(int,input().split())

coins = []
for _ in range(N):
    coin = int(input())
    if K >= coin:
        coins.append(coin)

coins.sort(reverse=True)
cnt = 0
for c in coins:
    cnt += K//c
    K = K%c
    if K== 0:
        break
print(cnt)

회의실 배정

https://www.acmicpc.net/problem/1931

첫번째시도

시간초과

반복문 범위를 줄이는 것이 필요해 보인다.

import sys
input = sys.stdin.readline

N = int(input())

conference = []
for _ in range(N):
    s, e = map(int,input().split())
    conference.append((s,e))

conference.sort()

max_cnt = 0
for i in range(N):
    cnt = 1
    time = conference[i][1]
    for j in range(i+1,N):
        if time <= conference[j][0]:
            cnt+=1
            time = conference[j][1]
        else:
            pass
    if max_cnt < cnt:
        max_cnt=cnt
print(max_cnt)

두번째시도

시간초과

반복문을 사용하지 않고 탐색하는 방법을 찾아야 할 것 같다.

import sys
# input = sys.stdin.readline

N = int(input())

conference = []
for _ in range(N):
    s, e = map(int,input().split())
    conference.append((s,e))

conference.sort()

max_cnt = 0
for i in range(N):
    if max_cnt > N-i:
        break
    cnt = 1
    time = conference[i][1]
    for j in range(i+1,N):
        if max_cnt > cnt+N-j:
            break
        if time <= conference[j][0]:
            cnt+=1
            time = conference[j][1]
        else:
            pass
    if max_cnt < cnt:
        max_cnt=cnt
print(max_cnt)

ATM

https://www.acmicpc.net/problem/11399

필요한 시간의 합의 최솟값을 구하기 위해서는 정렬한 뒤,

정렬된 인덱스 times[:], times[:N], times[:N-1], …, times[0]을 모두 더해주면 된다.

import sys
input = sys.stdin.readline

M = int(input())
times = list(map(int,input().split()))

times.sort()

result = sum(times)
for i in range(len(times)-1,-1,-1):
    result += sum(times[:i])
print(result)

Practice

수묶기

https://www.acmicpc.net/problem/1744

  • plus는 plus끼리, minus는 minus 끼리 묶어서 곱했을 때 값이 커진다.
  • plus는 역순으로 정렬, minus는 정순으로 정렬하여 0과의 거리가 먼 순서대로 곱해준다.
  • 1일경우, 곱했을 때보다 서로 더하는게 더 크다.
import sys
input = sys.stdin.readline

N = int(input())

plus = []
minus = []
numbers = []
for _ in range(N):
    number = int(input())
    if number > 0:
        plus.append(number)
    else:
        minus.append(number)
plus.sort(reverse=True)
minus.sort()

result = 0
for i in range(0,len(plus),2):
    if i+1 != len(plus):
        if  plus[i] != 1 and plus[i+1] != 1:
            result += (plus[i] * plus[i+1])
        else:
            result += (plus[i] + plus[i+1])
    else:
        result += plus[i]

for i in range(0,len(minus),2):
    if i+1 != len(minus):
        result += (minus[i] * minus[i+1])
    else:
        result += minus[i]

print(result)

대회 or 인턴

30

https://www.acmicpc.net/problem/10610

메모리 초과

import sys
from itertools import permutations
input = sys.stdin.readline

N = input().rstrip("\n")

per = sorted(list(permutations(N,len(N))),reverse=True)

result = -1
for p in per:
    string = ''
    for n in p:
        string += n
    if int(string)%30 == 0:
        result = string
        break
print(result)

2022

Stack

1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑