# Lv3

67개의 포스트
post-thumbnail

[알고리즘] 입국심사 (Python)

이 문제의 핵심은 모든 사람이 심사를 받는데 걸리는 시간 즉 return 해야하는 값을 기준으로 이분 탑색을 하는 것 이다.이분 탐색의 범위는 times배열의 최솟값 부터 최댓값 \* n이 될 것이다.이분 탐색의 기준은 해당 시간 즉 mid값 동안 입국심사를 마

2022년 5월 3일
·
0개의 댓글
post-thumbnail

Programmers - 합승 택시 요금

(문제링크)https://programmers.co.kr/learn/courses/30/lessons/72413프로그래머스 특성상 기본으로 지역변수를 사용하게 된다.global하게 사용되는 변수들을 미리 생각해 전역 처리를 한다.경로의 값을 최솟값으로 계속 바

2022년 4월 28일
·
0개의 댓글
post-thumbnail

[알고리즘] N으로 표현 문제 풀이 (Python)

문제보기딕셔너리에 키값으로 N을 사용한 갯수 값으로 해당 갯수로 나타낼 수 있는 수를 Set에 저장한다. 예를 들면, {1: {5}, 2: {55, 10, 0, 25, 1}, 3: {...}, ... }최솟값이 8보다 크면 -1을 return 합니다.라는 조건이 있기때

2022년 4월 26일
·
0개의 댓글
post-thumbnail

[알고리즘] [1차] 추석 트래픽 문제 풀이 (Python)

로그들의 리스트가 완료 순서대로 정렬되어 있고 1초간 처리량의 최대값을 구하는 문제이다. 요청이 완료되는 시점(해당 요청을 포함)부터 1초동안 처리 중인 요청의 수를 계산해서 최대값을 찾아 반환하는 방법으로 풀이를 했다.요청은 "2016-09-15 01:00:0

2022년 4월 19일
·
0개의 댓글
post-thumbnail

[알고리즘] 기둥과 보 설치 문제 풀이 (Python)

기둥과 보 설치 문제처음 문제를 읽고 생각한 풀이는 기둥 설치, 기둥 삭제, 보 설치, 보 삭제 네 가지 경우의 수로 분기 처리해서 각 경우마다 가능한지 판별하고 해당 작업을 수행하는 것이 였습니다. 하지만 이렇게 할 경우 구현해야할 것이 많고 예외

2022년 4월 12일
·
0개의 댓글
post-thumbnail

📹[프로그래머스] 단속카메라

문제 설명고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를

2022년 3월 24일
·
0개의 댓글

programmers - 표 편집

문제 링크효율성 테스트 마지막 네개를 통과하지 못했다.효율성 테스트 한개를 통과하지 못했다.이전에는 char\[]에 O, X를 담아서 사용했다면, 이번에는 이전 노드, 다음 노드, 인덱스, O/X 정보가 담긴 Node 배열을 활용하여 코드를 전개했다.즉, 노드와 노드를

2022년 3월 10일
·
0개의 댓글

programmers - 양과 늑대

문제 링크반례 두개를 찾지 못해서 틀렸다.지나온 경로를 문자열 형태로 저장하는 방식으로 풀었다. 맞았다.갈 수 있는 경로를 저장하는 방식으로 푸니 맞았다.핵심 제한 사항2 ≤ info의 길이 ≤ 17info의 max값이 상당히 작으므로, 모든 노드를 살펴봐도 시간 제한

2022년 2월 24일
·
0개의 댓글

programmers - 파괴되지 않은 건물

프로그래머스 링크핵심 제한사항1 ≤ board의 행의 길이 (= N) ≤ 1,000 1 ≤ board의 열의 길이 (= M) ≤ 1,000 1 ≤ skill의 행의 길이 ≤ 250,000skill마다 board의 요소를 하나하나 바꿔주는 방식은 비효율적인 방식이다.

2022년 2월 22일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 보석 쇼핑

보석 쇼핑정해진 목록 안에 모든 종류의 보석이 들어가야 한다. 이때 가장 짧은 목록을 구하자.보석 종류를 카운트하면서 시작점과 끝점을 주어진 목록 상에서 이동해가며 확인하는 투 포인터 문제다.끝점을 이동해가면서 모든 종류의 보석을 포함했는지 시작점을 이동해가며 최단 거

2022년 2월 21일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] N-Queen

N-QueenN X N 위의 좌표 (행, 열)에 퀸이 N개 놓일 수 있다. 이때 퀸이 서로 공격하면 안 되는 경우의 수를 N에 따라 구해야 한다. 즉, 서로 같은 행, 열, 대각선에 퀸이 존재하면 안 된다.row 행에 넣을 퀸의 위치를 정하자. (0 <= row

2022년 2월 19일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 합승 택시 요금

합승 택시 설명노드 별 최단 거리를 구해 특정 구간 c를 경유해 a, b에 도착한 경로별 거리를 구하자. 플로이드 워셜 알고리즘을 통해 각 노드에서 (자신을 포함한) 모든 노드로 향하는 최단 거리를 구한다.자기 자신을 0으로, 인접하지 않은(즉 이어진 간선이 없는) 노

2022년 2월 19일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 여행경로

여행경로모든 노드 방문이 아니라 모든 간선을 사용하는 경로를 탐색해야 한다. 특정 노드에서 출발하는 중복 간선을 허용하는 방향 그래프를 DFS로 풀자.주어진 ticket의 tail → head 정보를 바탕으로 딕셔너리로 만든다. 즉 특정 노드에서 갈 수 있는 인접 노드

2022년 2월 16일
·
0개의 댓글
post-thumbnail

프로그래머스: 단속카메라

#프로그래머스 #단속카메라 #자바

2022년 2월 16일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 멀리 뛰기

멀리 뛰기1칸 또는 2칸을 뛸 수 있다. 총 n칸을 뛸 수 있는 경우의 수를 구한다.1칸, 2칸을 아무런 조건 없이 마음대로 선택해 뛸 수 있기 때문에, 1칸 전/2칸 전 사용했던 경우의 수를 그대로 활용할 수 있다. 이를 활용해 dp를 사용한다.조합 수식을 사용할

2022년 2월 15일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 거스름돈

거스름돈주어진 동전을 사용해 총합이 n이 될 수 있는 경우를 구해야 한다. 0원부터 n원까지 주어진 동전을 통해 총합을 구할 수 있는 경우의 수를 담을 배열 dp동전은 자신 이상의 금액을 치르는 데 사용할 수 있다.cost-coin을 구하는 데 사용되는 경우가 cost

2022년 2월 15일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 줄 서는 방법

줄 서는 방법n명을 줄 세우는 경우의 수 중 k번째에 해당하는 경우의 수를 구한다.파이썬의 permutation 모듈은 시간 효율성이 떨어지기 때문에 직접 factorial 값을 통해 하나씩 구한다.매 차례마다 line 안에 남아 있는 n 명 중 앞 자리에 설 사람이

2022년 2월 15일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 섬 연결하기

섬 연결하기양방향 그래프의 최소 신장 트리를 구한다. 즉 모든 정점을 연결하는 경로의 총 비용이 최소인 경로를 찾아야 한다. 크루스칼 알고리즘을 사용한다.간선의 비용 순서대로 정렬한다.순서대로 간선을 꺼내면서 총 비용을 계산한다. 이때 간선을 이루는 노드가 기존에 계산

2022년 2월 14일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 등굣길

등굣길각 위치로 이동 가능한 경우의 수의 총합은 (가능하다면) 왼쪽에서 오는 경우의 수 + 위쪽에서 오는 경우의 수의 총합이다. 마지막으로 도착지의 경우의 수를 return한다.주어진 행열 리스트를 만들고 시작점에 1, 웅덩이에 -1을 줘서 표시한다.dp를 통해 왼쪽,

2022년 2월 14일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV3] 이중 우선순위 큐

이중우선순위큐힙을 통해 삽입되는 수를 정렬한다. 빈 큐에서 삭제 명령어는 무효라는 조건을 고려해 힙의 원소 개수를 파악해 삭제 명령어가 유효한 경우를 판단한다.삽입되는 수를 정렬하고 순서에 맞춰 입력되는 최댓값, 최솟값 삭제 명령어를 실행해야 한다. 힙을 통해 효율적으

2022년 2월 14일
·
0개의 댓글