본문 바로가기

알고리즘/프로그래머스

 (9)
2020 KAKAO BLIND RECUITMENT 괄호 변환 이 문제에 적힌 그대로 구현하는게 중요하다. 간단한 조건도 잘 체크하자. 먼저 '(', ')'로만 이루어진 문자열이 있을 경우 '('의 개수와 ')'의 개수가 같으면 이를 균형잡힌 괄호 문자열이라 한다. 그러면 일단 여기서 체크할 부분은 빈 문자열은 균형잡힌 괄호 문자열이 아니다. 균형잡힌 괄호 문자열을 판별하는 함수를 작성해보자. 함수 이름은 checkIsBalancedString이 좋은 것 같다. 만약 균형잡힌 문자열이라면 true, 아니라면 false를 반환한다. function checkIsBalancedString(s) { if (s === "") return false // 빈 문자열은 균형잡힌 문자열이 아니다. let left = 0 // 왼쪽 괄호의 개수 let right = 0 // 오른..
2022 KAKAO TECH INTERNSHIP | 코딩 테스트 공부 문제를 읽으면서 그리디 알고리즘의 냄새가 났다. 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구하는 문제이다. 해결해야하는 문제는 (초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단시간을 구하는 문제이다. 이때, 목표 알고력을 넘는 알고력이나 목표 코딩력을 넘는 코딩력은 구현 방법에 따라 시간초과나 세그먼트 폴트와 같이 예상치 못한 런타임 오류를 일으킬 수 있다고 한다.(해설) 이 문제는 2차원 동적계획법 DP로 풀이가 가능하다. DP를 아래와 같이 정의한다. dp[i[j]: 알고력 i , 코딩력 j 상태에 도달하는데 필요한 최단 시간 이렇게 DP배열을 정의하면 문제에서 요구하는 답은 dp[목표 알고력][목표 코딩력]이다. dp[초기..
2022 KAKAO TECH INTERNSHIP | 두 큐 합 같게 만들기 문제는 두 큐가 주어졌을 때 enqueue, dequeue 연산만으로 두 큐의 합이 정확히 반씩 나눠지도록 연산을 수행하는 것인데, 최소로 수행해야한다고 한다. queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 탐욕법을 사용하여 해결 할 수 있다. - L > R 이라면, q1의 원소를 q2으로 넘긴다. - L R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정해보자. 이 경우 L = R을 만들기 위해서 언젠가 L을 감소시키고 R을 증가시켜야 하고 결국 q1의 원소를 q2로 넘겨주는 동작은 반드시 필요하다. 이 때 직접 큐 자료구조를 사용하지 않고 단순히 배열을 큐로 사용..
[2021 KAKAO BLIND RECURITMENT] 메뉴 리뉴얼 코스개수를 순회하면서 주문할 수 있는 개수에 따른 combination을 만들어주고 가장 많이 나온 아이를 answer에 넣어주는 방법. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: temp = [] for order in orders: combi = combinations(sorted(order), c) temp += combi counter = Counter(temp) if len(counter) != 0 and max(counter.values()) != 1: answer += [''.join(f) for ..
[2021 카카오 채용 연계형 인턴십] 거리두기 확인하기 주요 조건들을 체크하자. - 맨해튼 거리가 2이하이면 탈락 - 테이블도 이동에 포함 - 파티션은 이동에 포함하지 않음 bfs로 접근. from collections import deque def bfs(place): start = [] d = (1,0),(-1,0),(0,1),(0,-1) for i in range(5): for j in range(5): if place[i][j] == 'P': start.append((i,j)) q = deque() visited = [[False] * 5 for _ in range(5)] for s in start: q.append((s[0], s[1], 0)) visited[s[0]][s[1]] = True while q: x, y, dist = q.popleft(..
[Summer/Winter Coding(~2018)] 지형 편집 ⭐️ 지형 편집 문제를 처음 접했을 때 백준에서 풀어본 문제랑 거의 동일하다는 것을 느꼈습니다. 문제는 높이는 최소 1, 최대 300으로 제한하고 있습니다. 당연히 높이마다 탐색해서 최소값을 구하는 것 보다 최소 높이와 최대 높이를 정해서 이분탐색하는게 더 빠를 것 같습니다. def solution(land, P, Q): answer = 1e9 min_height = 1e9 max_height = 0 for i in range(len(land)): for j in range(len(land[0])): max_height = max(max_height, land[i][j]) min_height = min(min_height, land[i][j]) def find_value ( h, land): cnt =0..
[2022 KAKAO BLIND RECRUITMENT] 양과 늑대 ⭐️ 양과 늑대 heap을 사용해서 양과 늑대의 우선순위 즉 양은 0이므로 앞에 온다. 를 이용해서 빠르게 제출을 할 수 있었다. 27점이나 맞았네..? import heapq def solution(info, edges): graph = [[] for _ in range(len(info))] for a,b in edges: graph[a].append(b) # graph[b].append(a) visited = [False] * len(info) print(graph) def traversing(start, animal: int , sheep, wolf): visited[start] = True q = [] heapq.heappush(q, (animal,start)) # q.append(start) w..
[2021 카카오 채용연계형 인턴쉽] 표 편집 ⭐️ 표 편집 첫 제출에 8점을 받았습니다. ㅋㅋㅋㅋㅋㅋ 코드에서 문제가 뭐였고 개선할 점을 찾아서 나아가봅시다. def solution(n, k, cmd): # print(n, k ,cmd ) # n 행의수 k. 행의 위치 cmd 명령어 answer = '' cursor = k true_table = [i for i in range(n)] table = [i for i in range(n)] deleted = [] for i in range(len(cmd)): prefix = cmd[i][0] if prefix == 'U': cursor -= int(cmd[i][-1]) if prefix == 'D': cursor += int(cmd[i][-1]) if prefix == 'C': deleted_inde..

티스토리툴바