프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.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 쉽지 않았던 문제.처음에는 이거 백트래킹으로 풀어야하나? 라는 생각이 들어서 백트래킹으로 코드를 한 번 작성해봤다. 첫 풀이 -> 백트래킹 사용 -> 오답 및 시간초과 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 처음에는 각 칸에 대해 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가 비어있..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krBFS로 풀면 되는 문제. BFS 탐색 함수를 따로 구현해서시작지점 ~ 레버까지의 최단거리, 레버 ~ 도착지점까지의 최단거리를 각각 구한 후 더해주면 된다.만약 2가지 최단거리 중 하나라도 None이 나오는 경우에는 도착이 불가능한 경우이므로 -1을 리턴해준다. 풀이 코드from collections import deque# BFS 돌리기def bfs(maps, start_x, start_y, end_x, end_y, end_val): n = len(maps) m = len(maps[0]) ..
알고리즘 문제를 풀면서 BFS를 구현할 때, queue를 주로 사용할 것이다. queue를 초기화해주기 위해 보통q = deque([(start_x, start_y)]) # 탐색 시작 노드 큐에 넣기 visited[start_x][start_y] = 0 # 탐색 시작 노드 방문 처리 while q: x, y = q.popleft()이렇게 해주고는 하는데, 이 코드를 q = deque([start_x, start_y]) # 탐색 시작 노드 큐에 넣기 visited[start_x][start_y] = 0 # 탐색 시작 노드 방문 처리 while q: x, y = q.popleft()가끔 이렇게 작성하는 실수를 할 때가 있다. 이렇게 코드를 작성하..
알고리즘 문제를 풀 때, 깊은 복사가 필요할 때가 있다. 그냥 단순한 가변 객체(리스트, 셋, 딕셔너리)를 복사할 때는 얕은 복사 (copy 메소드)로도 주솟값이 다르고 값만 같은 객체를 복사할 수 있지만 만약에 리스트 안에 리스트가 있는 복잡한 경우에는 깊은 복사를 활용해야 한다. 이 때, copy 모듈의 deepcopy를 사용하면 쉽게 깊은 복사를 할 수 있지만 시간이 많이 걸린다는 단점이 있다. 이럴 때는 깊은 복사를 수행할 수 있는 다른 방법을 사용해서 구현하자. 아래 링크 참고 행렬 테두리 회전하기프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr단순 구..
