알고리즘2022. 2. 27. 22:01
728x90

* 정렬은 출제 빈도높고, 평균 점수높다고 한다. (출처 : 프로그래머스)

 

--------------------------------------------------------------------------------------------------------------

 

[ 문제 ]

https://programmers.co.kr/learn/courses/30/lessons/42748

 

코딩테스트 연습 - K번째수

[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

programmers.co.kr

 

[ 코드 ]

def solution(array, commands):
    answer = []
    # com을 읽어온다. ex.[2, 5, 3]
    for com in commands:
        a, b, c = com
        ''' (위와 같은 코드)
        a = com[0]   ex. 2
        b = com[1]   ex. 5
        c = com[2]   ex. 3
        '''
        
        # 리스트 슬라이싱을 [시작:끝] 이렇게 했다면 시작~끝-1까지 담김
        arr = array[a-1:b] #2~5번째임. 인덱스에서는 1~4.
        sort_arr = sorted(arr) # 정렬
        
        # answer리스트에 추가해줌
        answer.append(sort_arr[c-1])
        
        #(참고) 이런 식으로 바로 쓰기도 가능!
        #answer.append(sorted(arr)[c-1])
    return answer

 

 

[ 참고자료 ]

파이썬 리스트 슬라이싱, append 가 헷갈린다면 아래 글이 도움될 것!

https://mminky.tistory.com/121

 

[ Python ] 리스트 추가, 삭제, 슬라이싱

* 리스트 추가 .append() * 리스트 원소 삭제 .pop .remove del * 리스트 슬라이싱 1) 이용방법 이렇게 이용하면 (시작)~(끝-1)까지의 항목들이 담긴다. 리스트명[시작:끝] 이런 리스트가 있다고 가정해보자

mminky.tistory.com

 

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 27. 21:47
728x90

[ 문제 ]

https://programmers.co.kr/learn/courses/30/lessons/42578

 

코딩테스트 연습 - 위장

 

programmers.co.kr

 

 

[ 코드 ]

def solution(clothes):
    dic={}
    c = 1
    
    # ["yellowhat", "headgear"] 이러한 items를 읽어옴
    for items in clothes:
        if items[1] in dic: # "headgear"가 이미 dic={} 안에 있다면
            dic[items[1]] += 1 # "headgear": +1
        else:               # "headgear"가 처음 나왔다면
            dic[items[1]] = 1  # "headgear" : 1
    
    #print(dic)	 #결과 {'headgear': 2, 'eyewear': 1}
    for v in dic.values(): # 여기서 2, 1을 의미
        c = c* (v+1)  # 안 쓴 경우까지 고려하기 위해 v+1
        # ex. headgear의 경우 "yellowhat", "bluesunglasses", "안 씀" (총 3가지)
        
    #for k, v in dic.items(): #(참고) 이렇게 key,value 이용 가능
    #    print(k," ",v)
    
    return c-1 # 최소 한 개 이상은 입음. 다 안 입는 경우 -1

 

경우의 수를 계산하는 법을 알아야 한다!

 

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 26. 23:47
728x90

[ 문제 ]

https://programmers.co.kr/learn/courses/30/lessons/42577

 

코딩테스트 연습 - 전화번호 목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조

programmers.co.kr

 

 

[ 코드 ]

def solution(phone_book):
    dic = {}
    for num in phone_book:
        dic[num] = 1 #기본 값
    
    # 각 폰 번호에 대해
    for n in phone_book: # ex. 123
        str_num = ''   
        for i in n:     # ex. 1/ 2/ 3
            str_num += i
            # 하나씩 자른게 딕셔너리에 있는지 확인 (단, 본인은 아닌거)
            if (str_num in dic) and (str_num != n):
                return False #처음에 answer=True 하고 return answer해도 되지만 이게 더 빠름
    return True
반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 26. 21:39
728x90

* 해시는 파이썬의 딕셔너리로 구현한다.

즉, 해시 문제'딕셔너리'를 이용하기!!

 

* 출제 빈도높고 점수보통 이라고 한다. (출처: 프로그래머스)

 

 

[ 문제 ]

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/42576

 

코딩테스트 연습 - 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수

programmers.co.kr

 

 

 

[ 풀이 ]

def solution(participant, completion):
    dic = {} # '해시' : 딕셔너리 이용
    
    # 참가자 이름별로 세기 (동명이인 두 명이면 2)
    for i in participant:
        if i in dic.keys():
            dic[i] += 1
        else:
            dic[i] = 1
    #return dic #결과값 {"leo":1,"kiki":1,"eden":1}
    
    # 완주자 명단에 있으면 -1
    for j in completion:
        if j in dic.keys():
            dic[j] -= 1
    #return dic #결과값 {"leo":1,"kiki":0,"eden":0}
    
    for k in dic:
        if dic[k] == 1: # != 0 이 더 정확할 것 같다. (0이 완주이기 때문)
            return k

 

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 23. 23:25
728x90

[ 문제 ]

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

 

[ 내가 푼 코드 ]

문제가 풀리기는 했으나 Greedy 알고리즘을 이용하지는 못했음

더보기
n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)

for i in a:
    if k >= i:
        if k%i ==0:
            coin += k//i
            break
        coin += k//i
        k = k%i

print(coin)

 

 

[ 해결 아이디어 ]

 

* 그리디(탐욕) 알고리즘

: 눈 앞의 이익만 우선 추구하는 알고리즘

( greedy : 탐욕스러운, 욕심이 많은 )

 --> knapsack문제, 동전 문제(각 동전은 작은 동전의 배수)

 

 

입력에 보면 Ai는 Ai-1의 배수 라는 조건이 있다.

즉, 동전이 1, 5, 10, 50, 100 .. 이런 식으로 큰 동전은 작은 동전의 배수가 된다.

이러한 유형은 GREEDY 알고리즘으로 해결 할 수 있다.

 

 

[ 해결 코드 ]

n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)

# GREEDY
for i in a:
    coin += k//i
    k = k%i
print(coin)

 

 

[ 결과 ]

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 23. 17:02
728x90

[ 문제 ]

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

 

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 

 

[ 코드 ]

n = int(input())
p = list(map(int,input().split()))
p.sort()

total = 0
for i in p:
    total += i*n
    n -= 1

print(total)

 

 

[ 결과 ]

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 23. 15:53
728x90

[ 문제 ]

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

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

 

 

[ 코드 ]

n = int(input())
bag = 0

while 1:    # 계속 반복함
    if n%5 == 0:    #5의 배수이면
        bag += n//5 #몫 만큼 bag에 더함
        break       #n이 5의 배수이면 몫 만큼의 가방만 필요하므로 끝!
                # (예) n=10이라면 n//5 = 2 -> 2개의 가방만 있으면 됨
    # 예외처리
    if n<3:
        bag = -1
        break
    # 3kg은 빼주면서 가방 하나씩 더함
    n -= 3
    bag += 1

print(bag)

 

 

[ 결과 ]

반응형
Posted by mminky

댓글을 달아 주세요

알고리즘2022. 2. 23. 15:48
728x90

코딩테스트를 준비하기 위해 백준사이트를 이용하려고 하는데

어떻게 이용해야할지 고민이었다.

그러다 검색을 통해 결론을 도출했다.

 

1. 백준 사이트

그리디, 탐색, 다이나믹(동적) 프로그래밍 문제 풀기

2. 프로그래머스

코딩테스트 연습 ( https://programmers.co.kr/learn/challenges )

 

( 한 문제당 소요시간은 45분으로 잡는다! )

 

 

--------------------------------------------------------------------------------------------------------

 

우선, 백준 사이트에서 원하는 알고리즘 별로 문제를 연습하는 방법이다.

문제 > 알고리즘 분류 로 들어간다.

 

여기서 원하는 알고리즘을 선택한다.

 

원하는 문제를 클릭하고 풀면 된다!

 

ex) 백준 - 그리디 알고리즘 모음

https://www.acmicpc.net/problemset?sort=ac_desc&algo=33 

 

문제 - 1 페이지

 

www.acmicpc.net

 

반응형
Posted by mminky

댓글을 달아 주세요