알고리즘/프로그래머스

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 피타고라스의 원리만 알면 풀 수 있는 문제. 근데, 피타고라스 원리 그대로 반복문을 2번 돌려서 풀면 시간초과가 뜬다. 틀린 풀이def solution(k, d): dist = (d ** 2) // (k ** 2) cnt = 0 same_cnt = 0 i = 0 while i  이렇게 풀면 시간초과가 뜨므로, 반복문을 한 번만 돌려서 풀 수 있게 풀이를 변경했다. 풀이 코드 def solution(k, d): dist = (d ** 2) // (k ** 2) ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 광물을 캘 곡괭이를 선택하면서 최소 피로도인 경우를 찾아 최소 피로도를 리턴하면 되는 문제. 백트래킹을 활용해서 풀었다.풀이 코드answer = int(1e9) # 최소 피로도def backTracking(dia, iron, stone, minerals, result): global answer # print(dia, iron, stone, minerals, result) if dia == 0 and iron == 0 and stone == 0: # 더 사용할 곡괭이가 없다면 최솟값 갱신 ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  DP 테이블을 활용해서 풀 수 있는 문제. 풀이 코드def solution(k, ranges): result = [] arr = [k] # arr[i] = i번째 값 n = 0 # 작업 횟수 while k > 1: if k % 2 == 0: k //= 2 else: k = k * 3 + 1 n += 1 arr.append(k) dp = [0] * (n + 1) # dp[i] ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구현 문제. import mathdef solution(w,h): answer = 0 # 전체 사각형 개수 all_square_cnt = w * h # 먼저 w, h의 최대공약수로 w, h를 나눈다. # 나눈 값까지만 사용할 수 없는 정사각형 개수를 계산하고 그 이후는 똑같은 패턴이므로 최대공약수를 곱해주면 된다. gcd = math.gcd(w, h) w //= gcd h //= gcd # h가 더 큰 경우 h / w를 기울기, 0 ~ w까지의 값을 ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 쉽지 않았던 문제.처음에는 이거 백트래킹으로 풀어야하나? 라는 생각이 들어서 백트래킹으로 코드를 한 번 작성해봤다. 첫 풀이 -> 백트래킹 사용 -> 오답 및 시간초과 import syssys.setrecursionlimit(10**6)maxim = 0def backTracking(n, k, enemy, answer): global maxim if n == 0: return answer if n = len(enemy): return len(enemy) if n >= ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 야근 지수가 최소화되도록 일을 하는 방법을 구하면 된다.야근 지수를 최소화시키려면 리스트 안 원소의 제곱의 합을 최소화시키면 되는데, 그러려면 제일 큰 수부터 작게 만들어야 한다는 생각이 들었다.그래서 뭔가 최댓값을 뽑아줘야하므로 정렬 관련된 로직이 필요하다는 생각이 들었다.최댓값을 뽑아 특정 값을 해당 최댓값에서 빼주고, 다시 또 최댓값을 뽑아서 특정 값을 해당 값에서 빼주고... 이 과정을 반복해야 하는데,매번 정렬하게 된다면 시간복잡도가 증가하므로, 적절한 자료구조가 없을까 생각해보다가 문득! 머리에 우선순..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 기본 하노이 탑 문제.정말 오랜만에 풀었다. 풀이 코드answer = [] # 방법을 저장하는 리스트def hanoi(num_disk, start, end): if num_disk == 0: return hanoi(num_disk - 1, start, 6 - start - end) # num_disk - 1개의 원판을 start -> start, end외 다른 원판으로 이동 answer.append([start, end]) # 가장 큰 원판을 start -> end로 이..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에는 각 칸에 대해 length를 1부터 1씩 증가시키면서 정사각형이 안 되는 경우에는 다음 칸으로 넘어가도록 구현했는데, 바로 효율성 검사에서 시간 초과가 나부렸다.뭔가 사각형 여부를 구할 때마다 계속 같은 연산을 하는 느낌이 들긴 했는데, 이걸 어떻게 개선해야 할 지 모르겠어서 다른 사람의 풀이를 참고했다. 풀이 코드def solution(board): n = len(board) m = len(board[0]) dp = [[0] * (m+1) for _ in range(n+1)] ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr BFS를 활용하면 되는 문제.기본 BFS 문제 로직과 거의 유사하지만 다른 점이 한 가지 있다.로봇이 한 칸씩 이동하는 게 아니라, 장애물에 부딪히거나 맵의 끝에 도달할 때까지 한 방향으로 계속 이동하고, 멈췄을 때까지 시간을 1로 친다는 것이다.그 부분을 반복문을 통해 구현해줬다. 풀이 코드from collections import dequedef solution(board): n = len(board) # 행 길이 m = len(board[0]) # 열 길이 visited = [..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 단순하게 구현해도 풀 수 있는 문제. BFS를 따로 활용할 필요 없이 조건문을 통해 구현할 수 있는 문제다. 풀이 코드# person(P의 좌표)에서 맨해튼 거리가 1, 2인 좌표들을 담은 리스트 close_list에 있는 좌표들이 실제로 거리두기가 지켜지고 있는지 확인하는 함수# 거리두기가 지켜지고 있다면 1 리턴, 그렇지 않다면 0 리턴def is_safe(place, person, close_list): x = person[0] y = person[1] # close_list가 비어있..
happenundo
'알고리즘/프로그래머스' 카테고리의 글 목록