알고리즘 문제풀이/프로그래머스
-
프로그래머스 최댓값과 최솟값 c++ 풀이 Level 2 연습문제 최댓값과 최솟값 문제 정리 문자열 s에는 공백으로 구분된 숫자가 있다. str에 나타나는 숫자중 최대, 최소 값을 찾아 "(최소값) (최댓값)" 형태로 반환해라 문자열에는 둘 이상의 정수가 공백으로 구분되어 있다. 문제 풀이 문자를 공백을 기준으로 나눈다. 나눠진 수를 차례대로 하나씩 숫자로 변환해본다. min, max와 비교해서 업데이트 해준다. 최종 min, max 값을 string으로 변환하여 정답을 완성한다. c++ 문자열 split sstream 헤더에 있는 istringstream 을 이용해서 나눌 수 있다. istringstream ss(split할 문자열)을 선언한다 자를 문자를 담을 string buffer를 선언한다(str..
[문자열] 프로그래머스 level2 최댓값과 최솟값 c++ 풀이프로그래머스 최댓값과 최솟값 c++ 풀이 Level 2 연습문제 최댓값과 최솟값 문제 정리 문자열 s에는 공백으로 구분된 숫자가 있다. str에 나타나는 숫자중 최대, 최소 값을 찾아 "(최소값) (최댓값)" 형태로 반환해라 문자열에는 둘 이상의 정수가 공백으로 구분되어 있다. 문제 풀이 문자를 공백을 기준으로 나눈다. 나눠진 수를 차례대로 하나씩 숫자로 변환해본다. min, max와 비교해서 업데이트 해준다. 최종 min, max 값을 string으로 변환하여 정답을 완성한다. c++ 문자열 split sstream 헤더에 있는 istringstream 을 이용해서 나눌 수 있다. istringstream ss(split할 문자열)을 선언한다 자를 문자를 담을 string buffer를 선언한다(str..
2020.07.05 -
프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..
[DP] 프로그래머스 level2 땅따먹기 c++ 풀이프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..
2020.07.04 -
프로그래머스 다음 큰 숫자 c++ 풀이 Level 2 연습문제 다음 큰 숫자 문제 정리 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다. ``` n의 다음 큰 숫자는 n보다 큰 자연수 n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 n은 1,000,000 이하의 자연수이다. 문제 풀이 n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다. 이를 n이 2나 1이 될때까지 반복한다. 마지막..
[2진수 변환] 프로그래머스 level2 다음 큰 숫자 c++ 풀이프로그래머스 다음 큰 숫자 c++ 풀이 Level 2 연습문제 다음 큰 숫자 문제 정리 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다. ``` n의 다음 큰 숫자는 n보다 큰 자연수 n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 n은 1,000,000 이하의 자연수이다. 문제 풀이 n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다. 이를 n이 2나 1이 될때까지 반복한다. 마지막..
2020.07.03 -
프로그래머스 가장 큰 정사각형 찾기 자바(java) 풀이 Level 2 연습문제 가장 큰 정사각형 찾기 문제 정리 1과 0으로 채워진 표가 있다. 표 1칸은 1x1의 정사각형으로 이루어져 있다. 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하여라 naive한 문제 풀이 처음에는 정말 naive하게 5중 for문을 이용해서 풀어보았습니다. 정확성은 모두 맞추었지만 역시나 효율성 테스트는 통과하지 못했습니다. 최대 크기의 board에서 우측하단 하나만 0인 경우 이런 경우 터질 것 같습니다. naive한 코드는 아래와 같습니다. public static int solution(int [][]board) { int x_len = board.length; int y_len = board[0].le..
[DP] 프로그래머스 level2 가장 큰 정사각형 찾기 자바 풀이프로그래머스 가장 큰 정사각형 찾기 자바(java) 풀이 Level 2 연습문제 가장 큰 정사각형 찾기 문제 정리 1과 0으로 채워진 표가 있다. 표 1칸은 1x1의 정사각형으로 이루어져 있다. 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하여라 naive한 문제 풀이 처음에는 정말 naive하게 5중 for문을 이용해서 풀어보았습니다. 정확성은 모두 맞추었지만 역시나 효율성 테스트는 통과하지 못했습니다. 최대 크기의 board에서 우측하단 하나만 0인 경우 이런 경우 터질 것 같습니다. naive한 코드는 아래와 같습니다. public static int solution(int [][]board) { int x_len = board.length; int y_len = board[0].le..
2020.06.02 -
프로그래머스 이중우선순위 큐 자바 풀이 Level 3 해시(Hash) 이중우선순위큐 문제 정리 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조 이다. 1.1 I 숫자 : 큐에 주어진 숫자를 삽입한다 1.2 D 1 : 큐에서 최댓값을 삭제한다. 1.3 D -1 : 큐에서 최솟값을 삭제한다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최대값, 최솟값]을 반환하여라. 최대/최소를 삭제하는 연산에서 최대/최소값이 둘 이상인 경우, 하나만 삭제한다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다. 문제 접근 우선순위 큐는 deque 처럼 뒤에서 뺄 수 없습니다. 그래서 오름차순, 내림차순 우선순위 큐를 따로 두어 최대, 최소를 구해야겠다고 생각했습니다. 오..
[우선순위 큐] 프로그래머스 level3 이중우선순위큐 자바 풀이프로그래머스 이중우선순위 큐 자바 풀이 Level 3 해시(Hash) 이중우선순위큐 문제 정리 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조 이다. 1.1 I 숫자 : 큐에 주어진 숫자를 삽입한다 1.2 D 1 : 큐에서 최댓값을 삭제한다. 1.3 D -1 : 큐에서 최솟값을 삭제한다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최대값, 최솟값]을 반환하여라. 최대/최소를 삭제하는 연산에서 최대/최소값이 둘 이상인 경우, 하나만 삭제한다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다. 문제 접근 우선순위 큐는 deque 처럼 뒤에서 뺄 수 없습니다. 그래서 오름차순, 내림차순 우선순위 큐를 따로 두어 최대, 최소를 구해야겠다고 생각했습니다. 오..
2020.05.28 -
프로그래머스 디스크 컨트롤러 자바(java) 풀이 Level 3 해시(Hash) 디스크 컨트롤러 문제 정리 하드 디스크는 한 번에 하나의 작업만 수행한다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 적게하여라. jobs의 길이는 최대 500이다. jobs의 각 행은 [작업이 요청되는 시점, 작업의 소요시간]이다. 각 작업에 대해 소요시간은 최대 1000이다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 문제 접근 만약 라면공장 문제를 풀지 않고 이 문제를 풀었다면 오래걸렸을 것 같습니다. 하지만 라면공장 문제를 풀고 감을 익혀서 문제를 풀 수 있었습니다. 이 문제는 문제를 파악하고 걸린시간의 평균을 가장 적게 하는 방법만 생각한다면 쉽습니다. 이 문제에 ..
[우선순위 큐] 프로그래머스 level3 디스크 컨트롤러 자바 풀이프로그래머스 디스크 컨트롤러 자바(java) 풀이 Level 3 해시(Hash) 디스크 컨트롤러 문제 정리 하드 디스크는 한 번에 하나의 작업만 수행한다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 적게하여라. jobs의 길이는 최대 500이다. jobs의 각 행은 [작업이 요청되는 시점, 작업의 소요시간]이다. 각 작업에 대해 소요시간은 최대 1000이다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 문제 접근 만약 라면공장 문제를 풀지 않고 이 문제를 풀었다면 오래걸렸을 것 같습니다. 하지만 라면공장 문제를 풀고 감을 익혀서 문제를 풀 수 있었습니다. 이 문제는 문제를 파악하고 걸린시간의 평균을 가장 적게 하는 방법만 생각한다면 쉽습니다. 이 문제에 ..
2020.05.27