분류 전체보기

Algorithm/Baekjoon
[백준] 문자열집합 / 14425번 / 파이썬 / Python / 딕셔너리
💡solutions ) 💬 쉬운 문제라고 생각하고 빠르게 풀어서 제출했더니 시간초과.... pypy로 제출해도 시간초과.. 💬 다른 방법이 있을까 하고 찾아보다가 첫 풀이와 비슷하게 딕셔너리를 사용하지만 이중 for문을 사용하지 않아 훨씬 효율적으로 풀 수 있었다. 💬 M개의 문자열 각각이 N개의 문자열로 이루어진 S집합에 존재하는지 확인하기만 하면 되기 때문에 -> 딕셔너리 자료형에 N개의 문자열을 각각 key값으로 저장한 후에 -> M개의 문자열을 반복문을 통해 key값이 존재하는지 확인하면 된다. 👨‍💻code ) 🐥첫 번째 풀이 -> 시간 초과💥 import sys input = sys.stdin.readline n, m = map(int, input().split()) s_dict = {} fo..
→2021.11.06
Algorithm/Baekjoon
[백준] 케빈 베이컨의 6단계 법칙 / 파이썬 / python / BFS 알고리즘
💡solutions ) 💬 처음 adj라는 인접행렬을 만들어 각 유저 간의 연결 상태를 나타내고 -> 덱 자료구조를 사용해서 BFS 알고리즘으로 구현하면 문제를 쉽게 해결할 수 있다. 💬 첫 시도에서 스택 자료구조를 사용해서 DFS 알고리즘 구조로 풀었더니 채점결과 실패했다. 이유는 해당 문제에선 출발지에서 각 노드까지의 최단 거리를 찾는 개념이기 때문에 DFS로 찾게 되면 최단 거리가 아닐 수 있기 때문이다. BFS와 DFS로 거리 구할 때의 차이 해당 문제에서 테스트케이스가 아래처럼 주어지는 경우 DFS로 거리를 찾는다면 ->1에서 2까지의 거리가 1, 3까지의 거리가 2가 나온다. 이와 비교하여 BFS에서는 1에서 2까지 그리고 1에서 3까지 모두 거리가 1이 나오므로 최단거리가 된다. 3 3 1 ..
→2021.11.05
Algorithm/Baekjoon
[백준] 괄호의 값 / 2504번 / 파이썬 / Python / Stack 자료구조
💡solutions ) 💬 이번 문제는 구현 문제로 자료 구조 스택(stack)을 활용해서 해결하였다. 💬 첫 번째 if 조건문은 입력값이 ')' 또는 ']'로 시작하는 경우가 -> 올바르지 못한 괄호열로 판별하기 위한 것이다. 처음에 이 조건문을 달지 않아서 채점 중간에 실패했다. 💬 sys모듈의 exit()는 프로그램 종료함수이다. -> 따라서 올바르지 못한 괄호열일 때는 print(0)을 해주고 exit(0)로 해당 프로그램을 바로 종료한다. ✔ sys모듈의 exit() 종료함수에 대한 설명 👇 참고 블로그 💬 올바른 괄호열인지 판별하는 것은 어렵지 않았으나, 괄호열의 값을 구하는 로직을 구현할 때 어려움을 느꼈다. 닫는 괄호가 나오면 그 이전에 stack 맨 끝(top)에 숫자가 있는지 확인하고 ..
→2021.11.04
Algorithm/Baekjoon
[백준] 빗물 / 14719번 / 파이썬 / Python / 구현 / 시뮬레이션
💡solutions ) 💬 기본적인 시뮬레이션 문제 💬 for반목문을 돌며 가장 높은 블록의 높이(max_height)와 인덱스(max_index)를 저장해두고, 블록들의 전체 높이의 합을 저장한다(block_sum) 💬 왼쪽 끝에서부터 max_index까지(좌에서 우→) 그리고 오른쪽 끝부터 max_index까지 (우에서 좌←) 탐색하여 블록의 높이를 비교하여 가장 높은 블록의 위치값(tmp)을 total에 더해준다. 💬 마지막에 total값에서 전체 블록들의 높이의 합인 block_sum을 빼주면 고이는 빗물의 총량을 구할 수 있다. 👨‍💻code ) import sys input = sys.stdin.readline h, w = map(int, input().split()) block = list(..
→2021.11.03
Algorithm/Baekjoon
[백준] 맥주 마시면서 걸어가기 / 9205번 / 파이썬 / python / BFS 알고리즘
💡solutions 💬 BFS 알고리즘으로 문제 해결하였다. 💬 주어진 좌표들을 사용하는데 -> 상근이네집(home_x, home_y)에서부터 탐색을 시작한다. 💬 편의점 좌표를 돌아가며 방문 가능 유무를 확인한다 -> 두 가지를 확인하는데 ①이미 방문했는지 ② 20개의 맥주로 이동할 수 있는 거리인지를 확인한다. 💬 q에서 popleft하여 다음으로 이동할 좌표가 락 페스티벌 좌표(rock_x, rock_y)이면 행복하게 페스티벌에 갈 수 있으므로 'happy'를 출력하면 된다. 👨‍💻code import sys from collections import deque def bfs(x, y): q = deque([[x, y]]) visit = [[x, y]] while q: x, y = q.popleft..
→2021.11.02
Algorithm/Baekjoon
[백준] 게으른 백곰 / 10025번 / 파이썬 / Python / Sliding Window / 슬라이딩 윈도우
💡solutions ) 💬 슬라이딩 윈도우 알고리즘(Sliding Window)을 활용하여 문제를 해결하였다. 💬 먼저 얼음 양동이들을 나타내는 ice 배열을 최대 크기만큼 만들어준다. -> ice = [0]*1000001 💬 입력을 주어진 양동이 좌표에 해당하는 얼음의 양을 넣어준다. 💬 윈도우의 고정된 범위를 next = 2*k +1(한 좌표에서 앞뒤로 k만큼씩 떨어지는 있는 범위를 모두 포함하므로)로 두고, for 반복문을 돌려 한칸씩 이동하며 맨 뒤에 있는 값 ice[i]은 윈도우값에서 (+)더해주고 맨 앞에 있는 값 ice[i-next]은 (-)빼준다. 💬 window값 업데이트할 때마다 answer도 최대값으로 업데이트해주기 📚 슬라이딩 윈도우 알고리즘(Sliding Window)이란? 윈도우..
→2021.11.01
Algorithm/Baekjoon
[백준] 주몽 / 1940번 / 파이썬 / Python
💡solutions ) 💬 처음에 문제 풀 때 별 생각없이 풀어서,, 주어진 재료들 중 두 재료씩 묶을 수 있는 모든 경우의 수를 itertools의 combinations을 통해 구했다가 시간초과가 났다. 주어진 재료 개수의 범위가 N(1 ≤ N ≤ 15,000)인 것을 감안하면 시간 초과가 나는 게 당연하다. 참고로 파이썬의 초당 2,000만번의 연산이 가능하다고 한다. 💬 두 번째 시도 -> 해당 문제는 투포인터 문제 유형이다. 먼저 정렬을 한 후 두 가지 인덱스 값(left는 맨 처음, right는 맨 끝 재료를 나타내기 위함)을 정의한다. 💬 left, right가 가리키는 두 재료의 합이 m과 같으면 answer += 1, m보다 작으면 left += 1, m보다 크면 right -= 1을 해..
→2021.10.31
Algorithm/Programmers
[프로그래머스] 디스크 컨트롤러 / 파이썬 / Python / heapq 사용
💡solutions ) 💬 참고 : 디스크 컨트롤러 문제에서 요구하는 작업 처리 방식은 FIFO(First In First Out)가 아니라 SJF(Shortes Job First)방식이다. 즉, 요청된 작업들 중 가장 짧은 작업시간을 요구하는 작업부터 우선적으로 처리하는 방식이다. -> 이런 방식으로 진행하면 각각의 요청된 작업들의 대기 시간을 줄일 수 있다는 장점이 있다. (비선점형 스케줄링 방식에서 평균 대기 시간이 가장 짧다) 💬 heapq 모듈을 통해 최소 힙 사용하였음 -> heap에 작업의 소요시간, 작업이 요청되는 시점 순서로 값을 넣으면 (이번 예제에선 heap = [[3, 0], [6, 2], [9, 1]] 순으로 들어가는 셈) -> heappop할 때 작업의 소요시간을 기준으로 가장 ..
→2021.10.29
Algorithm/Programmers
[프로그래머스] 실패율 / 파이썬 / python / 2019 KAKAO BLIND RECRUITMENT
💡solutions ) 💬 이번에 구현한 로직이 효율성면에서는 좋지 못한 코드다. 특히 for문 안에서 매번 count()를 하기 때문에 시간 복잡도가 O(N²)이고, remove() 메소드까지 있기 때문에 맨 처음 stages.sort()를 하지 않으면 몇가지 테스트 케이스에서 시간초과로 통과하지 못하는 문제가 있었다. 💬 참고로 첫 시도에서 1,6,7,9,13,23,24,25 테스트 케이스는 런타임에러가 났고, 질문하기를 통해 어떤 것이 문제인지 확인해보니 -> for문 안에서 전체 남아있는 total_user가 0인 경우 fail_user/total_user로 계산하게 되면 ZeroDivisionError가 발생하는 것이 문제였다. 💬 혹시 필자와 같은 테스트케이스가 런타임에러 나는 경우 아래 테스..
→2021.10.28
Algorithm/Programmers
[프로그래머스] 비밀지도 / 파이썬 / python / 2018 KAKAO BLIND RECRUITMENT/ 카카오 코테
💡solutions ) 💬 arr1과 arr2에서 주어진 정수들을 bin()을 사용해 이진수로 변환한 후 주어진 n크기에서 부족한 만큼을 0으로 채워주기 위해 zfill()사용 -> e.g.) 9를 이진수 1001 변환했을 때 -> 지도 한변의 크기가 5(n= 5)라면 -> 01001로 바꿔주기 👨‍💻code ) def solution(n, arr1, arr2): answer = [''] * n for i in range(len(arr1)): a1 = bin(arr1[i])[2:].zfill(n) a2 = bin(arr2[i])[2:].zfill(n) for j in range(n): if a1[j] == '0' and a2[j] == '0': answer[i] += ' ' else: answer[i] ..
→2021.10.27
Algorithm/Programmers
[프로그래머스] 베스트앨범 / 파이썬 / Python
💡solutions ) 💬 딕셔너리 자료형을 활용하여 문제를 해결함 💬 total_play_times 딕셔너리에 장르별 총 재생횟수를, song_dict에는 장르를 key값으로, 각 곡들의 재생횟수와 고유번호(나중에 정렬할 기준 순서로)를 리스트 형태로 value에 담았다. 💬 sort()를 이용하여 정렬 -> reverse = True로 내림차순 정렬, 정렬하는 기준을 lambda로 표현 고유번호는 작은 게 먼저 나와야 하므로 -음수로 만든 후 내림차순 정렬함. 💬 작년에 동일 문제를 다른 해결 방법(heapq 모듈 사용)으로 풀었던 게 있어서 참고용으로👇 [프로그래머스] 베스트앨범 / 파이썬 / Python / 해시 💫solutions ) 💬 defaultdict, heapq 모듈 사용 👩‍💻 cod..
→2021.10.26
Algorithm/Programmers
[프로그래머스] 위클리 챌린지 / 12주차 / 파이썬
💡solutions ) 💬 permutations 내장 모듈을 사용하여 주어진 던전들을 수행할 순서의 모든 경우를 구한다. 💬 먼저 해당 던전이 최소 필요 피로도를 만족하는지 확인한 후 소모 피로도만큼 initial_k에서 빼준 후 던전의 수를 카운트 해준다 -> cnt += 1 💬 마지막 max내장함수를 통해 cnt 셌던 것과 max_v를 비교하여 최대값을 저장한 후 마지막에 max_v 출력 👨‍💻code ) from itertools import permutations as permu def solution(k, dungeons): max_v = 0 for p in permu(range(len(dungeons)),len(dungeons)): cnt = 0 initial_k = k for i in p:..
→2021.10.25

• 이전
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• ···
• 19
• 다음