본문 바로가기

Algorithm144

[백준] 듣보잡 / 1764번 / 파이썬 / python 🎫code ) import sys input = sys.stdin.readline n, m = map(int, input().split(' ')) n_l = set() n_s = set() for _ in range(n): name = input().rstrip() n_l.add(name) for _ in range(m): name = input().rstrip() n_s.add(name) res = sorted(list(n_l & n_s)) print(len(res)) for i in res: print(i) 📌 description ) 문제출처 : www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 .. 2020. 10. 21.
[백준] 후보 추천하기 / 1713번 / 파이썬 / Python / defaultdict 💡solutions ) 💬 defaultdict 사용 -> collections 모듈의 defaultdict는 딕셔너리와 거의 비슷하지만 key값이 없을 경우 미리 지정해 놓은 초기(default)값을 반환하는 특징이 있다. -> 그래서 조건문을 통해 get()메소드로 키값이 있는지 확인하지 않아도 되는 편리함이 있다. 💬 반복문에서 추천 리스트의 요소들을 하나씩 뽑아서 사진틀 리스트(photo)에 있는 지 먼저 확인하기 💬 비어있는 사진틀 유무에 따라 분기 처리 -> 비어있는 사진틀이 없다면 photo 리스트에 가장 적은 추천을 받은 번호의 학생을 찾기 -> 해당 번호의 학생 photo 리스트에서 삭제, 동시에 r_dic에서도 삭제하여 추천횟수 초기화(0) 🎫code ) from collections .. 2020. 10. 21.
[백준] 회의실 배정 / 1031번 / 파이썬 / Python / 정렬 / 그리디 그리디 알고리즘(Greedy Algorithms)이란? 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 것을 결정하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 💡solutions ) 💬 sorted() 정렬 메소드를 사용했다-> 정렬기준은 종료시간, 시작시간 순으로 정렬 💬 이전 회의의(before) 종료시간을 rooms[0][1]로 잡고, 반복문을 통해 그 다음 회의의 시작시간과 비교하여 시작시간이 이전 회의의 종료시간보다 늦거나 같으면 가능회의 수를 (cnt)+=1 하고 before 값을 갱신해준다. 💬 처음 구현한 코드.. 2020. 10. 20.
[백준] 1541 / 잃어버린 괄호 / 파이썬 / Python / 문자열 이번 문제는 런타임에러가 계속 나서 고생을 좀 했습니다.. 😂 쉬운 문제 같았는데 계속 틀리더라구요! 결론적으로 문제에서 주어진 조건에 따른 반례를 고려하지 못해서 틀렸습니다. 예를 들어 '수는 0으로 시작할 수 있다.' 나 연산자 없이 숫자 하나만 입력받는 경우 등이 있습니다. 문제에서 우리가 알 수 있는 테스트케이스는 55-50+40 밖에 없으므로, 런타임에러가 나는 분들은 반례가 될 수 있는 것들을 찾아서 넣어보시길 추천드립니다! 💡solutions ) 💬 크게 세 부분으로 나눠서 로직 구현 👇 💬 주어진 식에 '-' 연산자 있는 경우 / '-'없이 '+' 연산자만 있는 경우 / 연산자 없이 숫자 하나만 입력받는 경우 💬 '-' 연산자가 있는 경우 : 최초의 마이너스 연산자를 기점으로 f, b으로 .. 2020. 10. 19.
[백준] ATM / 수 정렬하기 / 파이썬 / Python / 정렬 💡solutions ) 💬 sorted()를 이용해 오름차순 정리한 정렬의 기본 문제 🎫code ) # 11399번 ATM 문제 n = int(input()) arr = sorted((map(int, input().split()))) res = 0 next = 0 for i in arr: res += i + next next += i print(res) # 2750번 수 정렬하기 문제 import sys input = sys.stdin.readline arr = [] for i in range(int(input())): n = int(input()) arr.append(n) arr = sorted(arr) for i in arr: print(i) 📌 description ) 문제출처 : www.acmic.. 2020. 10. 12.
[백준] 최단경로 / 1753번 / 파이썬 / Python / Dijkstra 💡solutions ) 💬 이번 문제는 최단 경로를 풀 때 가장 대표적인 다익스트라 알고리즘을 통해 해결했다. 💬 heap 자료구조 사용하여 heappop()을 했을 때 가장 최단 경로가 나오게 한다. 🎫code ) import heapq import sys input = sys.stdin.readline def dijkstra(v, s, adj): dist = [INF] * (v + 1) # 최단경로 리스트 dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) # 최소힙 이용 for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c h.. 2020. 10. 9.

티스토리툴바