일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 코딩
- DFS
- linux
- 킥스타트
- google coding competition
- 동적 프로그래밍
- 백준
- 프로그래머스
- 구글 킥스타트
- 코딩테스트
- 리눅스
- 네트워크
- OS
- 운영체제
- kick start
- 프로그래밍
- 코딩 테스트
- 순열
- 알고리즘
- 브루트포스
- 그래프
- 딥러닝
- nlp
- PYTHON
- 동적프로그래밍
- AI
- CSS
- dp
- BFS
- 파이썬
- Today
- Total
목록코딩 테스트/프로그래머스 (30)
오뚝이개발자
문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 나의 풀이 처음엔 그냥 2중 for문을 써서 각 시작점마다 보석 종류를 모두 포함하는 끝지점을 검출하면 break하고 다음 시작점부터 탐색하는 알고리즘을 짰는데 역시나 시간초과에 걸렸다. 개선한 풀이는 다음과 같다. start, end의 투포인터를 사용한다. 처음엔 둘다 0번째 인덱스로 초기화 한다. start부터 end까지의 보석이 전체 보석 종류를 포함하면 start를 증가시키고, 모자라면 end를 증..
문제 https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 나의 풀이 n(총 버스 수)과 t(버스 간격)를 사용해 버스가 정차하는 시간 저장 timetable의 시간 모두 분으로 변환 후 오름차순으로 정렬 m(버스 수용 가능 최대 인원)을 이용해 각 버스가 정차하는 시간마다 탈 수 있는 사람 저장 가장 늦..
nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까? 답은 (1,2), (2,1)로 2개이다. 그렇다면 이를 구하기 위한 알고리즘은 무엇일까? 이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자! 가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다. 이를 풀기 위해선 dp를 사용하면 된다. 위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다. 관련 문제 leetcode.com/problems/target-sum/ Target Sum - LeetCode Level up y..
문제설명 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 순위를 확실히 알기 위해선 해당 사람이 이기고 진 정보의 갯수 합이 n-1개가 되어야 한다. 여기서 중요한 점은 A를 이긴 사람은 A에게 진 사람을 이기고 A에 진 사람은 A에게 이긴 사람에 진다 는 것이다. def solution(n, results): answer = 0 # win[i] : i가 이긴 사람의 집합 # lose[i] : i가 지는 사람의 집합 win, lose = {}, {} for i in range(1, n+1): win[i], lose[i] = ..
문제 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 DP를 사용해 푸는 문제이다. 문제에서 이동은 오른쪽과 아래쪽으로만 가능하다고 했으니, 한 지점까지 올 수 있는 가능한 경로는 그 지점의 위와 왼쪽칸으로부터이다. 따라서 각 칸마다 그 칸까지 도달가능한 경로의 수를 저장하면 된다. grid라는 n x m 2차원 리스트를 만들어 (0,0)에 1을 넣고, puddle에는 -1을 넣는다. 그 후, 이중for문으..
문제 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 풀이 처음엔 이분탐색을 사용하지 않고 time stamp를 찍어 반복문을 돌 때마다 시간이 1씩 경과하도록 구현하였다. 그런데 역시나 시간초과에 걸렸다. 어려웠던 부분이 어떠한 기준으로 이분탐색을 하고, 어떤 값을 탐색으로 찾아야 하는지를 정하는 것이었다. 결국 다른 블로그를 참고해서 구현하였다. 먼저 이분 탐색으로 찾아야 하는 값은 "return해야 하는 최소 소요 ..
문제 programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 풀이 처음엔 단순한 문제인줄 알고 DFS를 사용하지 않고 풀어보려 했다. 내가 생각한 방식은 이러했다. 출발점이 ICN인 것들 추출해서 도착점 알파벳 순으로 앞서는 것은 선택한다. 1에서 선택한 경로의 도착점이 출발점인 것을 골라 알파벳순으로 비교하고 선택하는 과정을 반복한다. 그런데 문제는 위와 같은 방법으로 풀이했을 때 반례가 존재한다는 것이다. [["ICN","JFK"],["ICN","..
문제 문제가 조금 복잡해서 링크를 첨부하겠다. programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 풀이 전공자거나 운영체제의 스케쥴링 부분을 공부한 사람이라면 소요시간이 작은 작업을 우선적으로 처리하는 것이 최적의 경우라는 것을 알 것이다. 우선순위큐를 이용하면 되는데 약간은 복잡한 조건을 고려해주어야 한다. 그러나 단순히 소요시간 기준으로 정렬해 처리하면 다른 조건들을 고려하지 못한다. 생각의 순서는 다음과 같다. ..