문제풀이/프로그래머스
-
[프로그래머스]멀리 뛰기 - JAVA문제풀이/프로그래머스 2021. 2. 27. 13:31
[프로그래머스]멀리 뛰기 programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이 문제의 조건대로 n이 1일때부터 경우의 수를 구해보았다. n 방법 경우의 수 n = 1 1 1 n = 2 1 + 1 2 2 n = 3 1 + 1 + 1 2 + 1 1 + 2 3 n = 4 1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 2 + 2 5 n이 4일..
-
[프로그래머스]게임 맵 최단거리 - JAVA문제풀이/프로그래머스 2021. 2. 25. 14:59
[프로그래머스]게임 맵 최단거리 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 풀이 프로그래머스 레벨4 문제 임에도 불구하고 BFS를 사용하면 금방 풀리는 문제이다. BFS를 사용하는 이유는 최단경로를 탐색하기 때문이다. 현재까지의 cost를 저장해 주기 위해 Node class를 만들어 주었다. BFS의 반환 타입을 int형으로 해주어 x, y가 도착 노드에 도착했다..
-
[프로그래머스]보석 쇼핑 - JAVA문제풀이/프로그래머스 2021. 2. 24. 14:04
[프로그래머스]보석 쇼핑 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 set, map, queue를 사용하여 풀었다. 사용한 이유는 다음과 같다. 1. set은 보석의 종류의 개수를 알아내기 위해 사용하였고, 2. map은 보석의 종류별 개수를 기록하기 위해 사용하였고, 3. queue에는 보석의 순서대로 저장한 후 보석의 개수가 2개 이상이 되면 빼주도록 하여 문제에 조건에 맞는 보석의 구간을 구하기 위해 사용하였다. 하나씩 살펴보쟝. 1. set을 사용해 보석..
-
[프로그래머스]자물쇠와 열쇠 - JAVA문제풀이/프로그래머스 2021. 2. 23. 15:39
[프로그래머스]자물쇠와 열쇠 programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 특별한 알고리즘을 사용하지않는 구현, 시뮬레이션 문제이다. 그러나 어떻게 풀어야 할지 아이디어를 생각해 내기 어려웠던 문제라고 생각이 든다. 문제를 푸는 핵심 아이디어는 아래 와 같다. 1. lock를 확장한다. 2. key를 회전한다. 3. key가 lock에 맞는지 확인힌다. 하나씩 차근차근 살펴보쟝. 1. lock를 확장한다. 확장하는 이유는 키의 일부가 자물쇠의 영역을 벗어나도 키로 ..
-
[프로그래머스]디스크 컨트롤러 - JAVA문제풀이/프로그래머스 2021. 2. 22. 14:31
[프로그래머스]디스크 컨트롤러 programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 이 문제의 개념은 CPU스케줄링의 비전섬 기법중 SJH스케줄링 기법이랑 완전히 동일하다. ReadyQueue에 있는 작업 중에 실행시간이 짧은 작업에게 먼저 CPU를 할당한다. ReadyQueue는 우선순위 큐를 사용하여 실행시간이 짧은 순서대로 정렬되게 해주었고, 기존의 jobs는 시작시간 순서대로 정렬해 주었다. 반복문을 사용하여 ..
-
[프로그래머스]징검다리 건너기 - JAVA문제풀이/프로그래머스 2021. 2. 21. 13:41
[프로그래머스]징검다리 건너기 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이 이분탐색 문제이다! 이분탐색을 하지 않고 풀면 시간초과가 날 것이다! 전형적인 이분탐색의 유형으로 최소값, 최대값을 건널 수 있는 프렌즈의 수 범위로 둔다. 처음에는 min을 0, max를 건널 수 있는 프렌즈의 최대값으로 둔 다음, mid이상의 프렌즈가 건널 수 있다면 min을 mid + 1로, mid이상의 프렌즈가 건널 수 없다면 max를 mid - 1로 변경하여 또 탐색한다. 이때 건널 수 있는지 없는지 판단하는 방법은 간단하다. stones의 각 ..
-
[프로그래머스]등굣길 - JAVA문제풀이/프로그래머스 2021. 2. 20. 14:42
[프로그래머스]등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 문제 설명이 조금 이상하긴 한데 그림을 보면 m이 세로 행의 개수이고, n이 가로 열의 개수이다. 그러므로 board를 만들때 boar[n][m]으로 만들어 주었다. 이에 따라 puddles의 위치 좌표도 [y, x]좌표로 입력이 되어있다고 생각했다. 그런데 또 문제 설명에서 오른쪽 아래 학교의 좌표는 m, n이라고 한다. 배열로 생각하고..
-
[프로그래머스]하노이의 탑 - JAVA문제풀이/프로그래머스 2021. 2. 18. 14:06
[프로그래머스]하노이의 탑 programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 풀이 DP의 전형적인 문제인 하노이의 탑 문제이다. 하노이의 탑은 문제 설명에도 나와있듯이 N개의 원판을 1번 기둥에서 3번 기둥으로 2번 기둥을 사용하여 조건에 맞게 이동시키는 문제이다. 이 문제를 이해하기 위해 N이 작은 때를 생각해 보았다. N이 2라면 2개의 원판을 1 -> 2 -> 3으로 옮기는 경우의 수가 될 것이고..