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

Algorithm/Baekjoon

[백준] 후보 추천하기 / 1713번 / 파이썬 / Python / defaultdict

💡solutions ) 💬 defaultdict 사용 -> collections 모듈의 defaultdict는 딕셔너리와 거의 비슷하지만 key값이 없을 경우 미리 지정해 놓은 초기(default)값을 반환하는 특징이 있다. -> 그래서 조건문을 통해 get()메소드로 키값이 있는지 확인하지 않아도 되는 편리함이 있다. 💬 반복문에서 추천 리스트의 요소들을 하나씩 뽑아서 사진틀 리스트(photo)에 있는 지 먼저 확인하기 💬 비어있는 사진틀 유무에 따라 분기 처리 -> 비어있는 사진틀이 없다면 photo 리스트에 가장 적은 추천을 받은 번호의 학생을 찾기 -> 해당 번호의 학생 photo 리스트에서 삭제, 동시에 r_dic에서도 삭제하여 추천횟수 초기화(0) 🎫code ) from collections ..

→2020.10.21

Algorithm/Baekjoon

[백준] 회의실 배정 / 1031번 / 파이썬 / Python / 정렬 / 그리디

그리디 알고리즘(Greedy Algorithms)이란? 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 것을 결정하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 💡solutions ) 💬 sorted() 정렬 메소드를 사용했다-> 정렬기준은 종료시간, 시작시간 순으로 정렬 💬 이전 회의의(before) 종료시간을 rooms[0][1]로 잡고, 반복문을 통해 그 다음 회의의 시작시간과 비교하여 시작시간이 이전 회의의 종료시간보다 늦거나 같으면 가능회의 수를 (cnt)+=1 하고 before 값을 갱신해준다. 💬 처음 구현한 코드..

→2020.10.20

Algorithm/Baekjoon

[백준] 1541 / 잃어버린 괄호 / 파이썬 / Python / 문자열

이번 문제는 런타임에러가 계속 나서 고생을 좀 했습니다.. 😂 쉬운 문제 같았는데 계속 틀리더라구요! 결론적으로 문제에서 주어진 조건에 따른 반례를 고려하지 못해서 틀렸습니다. 예를 들어 '수는 0으로 시작할 수 있다.' 나 연산자 없이 숫자 하나만 입력받는 경우 등이 있습니다. 문제에서 우리가 알 수 있는 테스트케이스는 55-50+40 밖에 없으므로, 런타임에러가 나는 분들은 반례가 될 수 있는 것들을 찾아서 넣어보시길 추천드립니다! 💡solutions ) 💬 크게 세 부분으로 나눠서 로직 구현 👇 💬 주어진 식에 '-' 연산자 있는 경우 / '-'없이 '+' 연산자만 있는 경우 / 연산자 없이 숫자 하나만 입력받는 경우 💬 '-' 연산자가 있는 경우 : 최초의 마이너스 연산자를 기점으로 f, b으로 ..

→2020.10.19

Algorithm/Baekjoon

[백준] 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

Algorithm/Baekjoon

[백준] 최단경로 / 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.09

Algorithm/Programmers

[프로그래머스] 예상 대진표 / 파이썬 / Python / round()

💡solutions ) 💬 파이썬의 반올림 round( ) 함수를 사용해서 그 다음 라운드 진출 시 부여받는 숫자 번호를 구해내는 로직. 💬 이때 주의해야 할 점은 반올림한 자리의 앞자리 숫자가 짝수이냐 홀수이냐에 따라 반올림한 값이 달라진다는 점이다. 따라서 앞자리 숫자가 짝수인 경우는 반올림한 값에 +1씩 더해준다. 💬 아래 파이썬의 반올림 규칙을 참고하자. 🔶 파이썬의 round()함수는 사사오입 원칙을 따른다. 반올림 자리의 수가 5일 때 앞자리가 짝수 -> 내림 -> e.g.) round(4.5) = 4 앞자리가 홀수 -> 올림 -> e.g.) round(3.5) = 4 🎫code ) def solution(n, a, b): answer = 0 while a != b: answer += 1 r_..

→2020.10.07

Algorithm/Programmers

[프로그래머스] 짝지어 제거하기 / 파이썬 / Python

💡solutions ) 💬 처음 작성했던 코드에서 슬라이싱으로 문자열을 업데이트 했는데 시간초과 나서 통과하지 못했다. 💬 다음으로 구현한 코드는 stack을 만들어서 문자를 하나씩 append()로 넣어주고 짝을 만난 경우에는 pop()으로 제거해주었다. 💬 마지막 문자열의 길이를 재고 0이면 1리턴, 0이 아니면 0을 리턴한다. 🎫code ) 🔶 효율성 테스트에서 시간 초과로 통과하지 못한 코드 # 시간 초과 코드 def solution(s): if len(s) % 2 == 1: return 0 idx = 0 while True: if len(s) == 0: return 1 if idx > len(s) - 2: return 0 if s[idx] == s[idx + 1]: if idx == 0: s =..

→2020.10.06

Algorithm/Programmers

[프로그래머스] 땅따먹기 / 파이썬 / Python / 동적 프로그래밍(DP)

💡solutions ) 💬 동적프로그래밍 문제이다. 💬 1행(i+1이니)부터 시작해서 각 행열 요소마다, 그 이전 행에서 자신과 열이 같지 않은 열들 중 최댓값을 더해준다. 💬 마지막 행의 최댓값이 결과값이 된다. 🎫code ) def solution(land): for i in range(len(land)-1): land[i+1][0] = max(land[i][1:4]) + land[i+1][0] land[i+1][1] = max(land[i][0], max(land[i][2:4])) + land[i+1][1] land[i+1][2] = max(max(land[i][0:2]), land[i][3]) + land[i+1][2] land[i+1][3] = max(land[i][0:3]) + land[i+1..

→2020.10.05

Algorithm/Programmers

[프로그래머스] 가장 큰 정사각형 찾기 / 파이썬 / Python / 동적 프로그래밍(DP)

💡solutions ) 💬 동적 프로그래밍(DP)를 활용해서 문제를 풀것. 브루트 포스 알고리즘으로 풀면 효율성 테스트를 통과하지 못함 💬 동적 계획법(Dynamic Programming)이란? 동적 프로그래밍은 “전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식” 이다. 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있다. 💬 분할 정복과 동일한 점은 전체 문제를 작은 단위로 문제로 푼다는 것지만, 차이점은 중복의 유무이다. 분할 정복은 작은 문제끼리 중복이 없고, 동적 프로그래밍은 중복이 있다. 🎫code ) def solution(board): r = len(board) c = len(board[0]) for i in range(1,..

→2020.10.04

Algorithm/Programmers

[프로그래머스] 행렬의 곱셈 / 파이썬 / Python

💡solutions ) 💬 예를 들어, AXB 행렬과 BXC 행렬의 곱셈 -> 두 행렬에서 B의 자리가 같은 숫자일 때만 곱셈이 가능하며 -> 곱셈의 결과는 AXC행렬이 된다. 💬 아래 코드에서 answer은 곱셈의 결과가 되는 AXC행렬이고, 💬 i가 A / j가 C / k가 B로 삼중 반복문으로 행렬의 곱셈을 구현했다. 🎫code ) def solution(arr1, arr2): r = len(arr1) c = len(arr2[0]) answer = [[0]*c for _ in range(r)] for i in range(r): for j in range(c): for k in range(len(arr1[0])): answer[i][j] += arr1[i][k]*arr2[k][j] return ans..

→2020.10.03

Algorithm/Programmers

[프로그래머스] N개의 최소공배수 / 파이썬 / Python

💡solutions ) 💬 주어진 숫자 리스트를 오름차순으로 정리한 후 가장 큰 값인 max를 구한다. 💬 나머지 숫자들이 max의 약수인지 먼저 확인하고, 약수가 아닌 경우 max의 그 다음 배수를 확인하는 과정을 반복한다. -> 나머지 숫자들이 모두 약수가 되는 경우가 모든 숫자에 대한 최소공배수가 된다. (max의 배수는 max가 이미 약수가 된다.) 🎫code ) def solution(arr): answer = 0 arr.sort() max = arr[-1] answer = max while True: for i in range(len(arr)-1): if answer % arr[i] != 0: break else: return answer answer += max 📌 description ) ..

→2020.10.02

티스토리툴바