출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 오른쪽과 아래로만 움직임 # 물웅덩이의 좌표가 주어짐 # 좌상단 집, 우하단 학교 # 집에서 학교까지 갈 수 있는 최단 거리의 개수 % 1000000007 더보기 먼저, 생각해야 할 부분 1. m x n 좌표가 바뀌어있다. 이건.....알았는데..........문제 내의 모든 좌표가 바뀌어 있다. 그러니까 물웅덩이 좌표도 바뀌어 있다. 하필 예제가 [2, 2]인걸 보면 그냥 당하라고..
출처 : 이것이 취업을 위한 코딩테스트다 with Python 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. DP 유형에서 핵심은 현재 -> 다음이 아니라, 이전 -> 현재이다. 다시 말해, 내가 현재 상태에 있을 때 이전에 내가 있을 수 있는 곳들의 후보를 찾는 것이 핵심이다. 문제에서 나는 현재 위치에서 우상, 우, 우하로 이동할 수 있다고 적혀있지만, 점화식을 추론하기 위해서는 현재 위치일 때, 이전에 내가 있을 수 있는 곳을 추론해야한다. 이 경우, 좌상, 좌, 좌하에서 현재..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준에도 동일한 문제가 있다. # I 숫자 -> 큐에 숫자 삽입 # D 1 -> 최댓값 삭제 # D -1 -> 최솟값 삭제 # 큐가 비어있다면 삭제 명령 무시 # [최댓값, 최솟값] return # 만약 큐가 비어있다면 [0, 0] return 더보기 먼저, 생각해야 할 부분 1. min_heap, max_heap 2개가 필요하다는 것까진 생각했을 것이다. 그렇다면 max_..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 작업들이 (요청 시간, 작업 소요 시간) 리스트로 들어온다. # 디스크는 1개에 1개의 작업만 가능 # 평균 (요청 시간 ~ 작업 종료) 시간이 가장 짧게 프로세싱할 경우 평균 (요청 시간 ~ 작업 종료) 시간을 return 더보기 먼저, 생각해야 할 부분 1. jobs가 정렬되어 들어온다는 말이 없다. 진짜 치사한데, 맞는 말이다. 정렬되어 들어온다는 말이 없으므로 정..
출처 : 백준, https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 메모리 제한이 4MB로 굉장히 작다 -> 비트마스킹 2. 반복문을 통해 입력 받을 수 있는 명령어의 개수가 최대 3,000,000개이다. -> sys.stdin.readline().rstrip() 풀이 import sys n = int(input()) my_set = 0b0 for _ in range(n): instrction = sys.stdin.readline().rstrip..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n명의 권투 선수들은 1부터 n까지 번호를 가짐 # results는 경기 결과 배열 # 경기 결과 A B는 A가 B를 이겼음을 표시 # 순위를 매기려 하는데 몇몇 경기 결과 분실 # 알고있는 경기 결과를 통해 순위를 확실히 알 수 있는 선수의 수를 return 더보기 풀이 def solution(n, results): answer = 0 INF = float('inf')..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n개의 노드가 있는 그래프에서각 노드는 1~n으로 주어짐 # 가장 멀리 떨어진 노드란 최단경로로 이동 했을 때 간선의 개수가 가장 많은 노드 # 1번 노드로부터 가장 멀리 떨어진 노드의 개수 더보기 먼저, 생각해야 할 부분 1. 1번 노드로부터의 최단 경로를 찾고 있다 -> 다익스트라 알고리즘 2. BFS를 이용한 풀이 역시 가능하다. 다익스트라를 이용한 풀이 from ..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 숨바꼭질 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 다익스트라 풀이 import sys from collections import Counter from heapq import heappop, heappush INF = float('inf') def solution(n, pass_list): #1번으로부터 최단 거리가 가장 먼 노드를 찾음. ad_matrix = [[INF for _ in range(n)] for _ in range(n)] # 인..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 화성 탐사 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. 한 곳에서 다른 곳까지 이동할 때 최소 비용을 구하는 문제이다. (최단 거리 문제) 단, 이동 시 가중치가 다 다르다 -> 다익스트라로 풀어야한다. 2. 가중치 그래프 설정 방법 - 하나의 칸에 있는 값을 칸을 나가기 위한 값으로 설정한다 - 칸에 도착할 경우에도 에너지가 소모되므로, 이 경우 최단 거리 return 시 마지막 칸의 값을 별도로 더해주어야한다. 풀..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 정확한 순위 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. n명 중 정확한 순위를 알 수 있다는 것은 내 아래로 A명과 내 위로 B명을 더했을 때 n-1 명이라는 것과 같다. 2. 내 점수보다 아래 혹은 위임을 알 수 있는 방법은 해당 노드를 방문할 수 있는지 여부를 통해 알 수 있다. 3. r = 점수가 낮은 학생, c = 점수가 높은 학생으로 정했을 때, 1번 행은 1보다 1번 학생보다 점수가 높은 학생들의 방문 가..
출처 : 백준, https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # n개의 도시 사이를 운행하는 m개의 버스가 있음 # A B C -> A 도시에서 B 도시로 가는 비용 C # 가격이 다른 동일 노선이 존재할 수 있음. # 각 도시에서 다른 도시로 가는 최소 비용을 출력 # 갈 수 없을 경우 0 출력 더보기 먼저, 생각해야 할 부분 1. 가격이 다른 동일 노선이 존재할 수 있다. 2. 모든 도시에서 모든 도시로 가는 최소 비용을 구해야한다. -..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 비내림차순 정렬(점점 증가하는 수열)이 주어질 때 # 시작idx와 길이가 가장 작으면서 내부 요소 총합이 k인 부분 수열의 [시작 idx, 끝 idx]를 return 더보기 먼저, 생각해야 할 부분 1. 조합으로 풀기에는 sequence가 1,000,000개까지 존재할 수도 있다. 수열의 부분합을 빠르게 구할 수 있는 다른 방법은 무엇이 있을까? Two Pointer를..
