개발지식 먹는 하마 님의 블로그

https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 실패한 1차 시도처음에는 완전 탐색 방식으로 코드를 풀고자 시도하였다.1. 문자열로 가능한 조합을 모두 찾고2. 해당 조합 중 가장 큰 조합을 찾는 것이다.조합을 찾기 위한 방법으로 next_permutation 함수를 사용하였다.문제점해당 풀이의 문제는 시간 복잡도가 매우 높다는 것이다.next_permutation은 정렬된 데이터에 대해서 순열을 구할 수 있다.우선 정렬이 먼저 필요하다.그리고 다음 경우의 수가 없을 때까지 순열을 바꿔줘야 하고반복문..

https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 풀이다른 번호의 접두사인 경우가 있는지 확인한다.= 배열에 저장된 데이터 전체에 대해 비교해야 한다. 어떤 번호가 다른 번호의 접두사인 경우가 있으면 false, 아니면 true= 접두사인 경우가 1개만 있어도 false이다.1. 정렬하기접두어가 없는 경우 어쩔 수 없이 전체 데이터에 대해 비교를 하게 되지만,정렬을 하면 어떤가?비슷한 값의 데이터들이 모이면서 접두어가 있는 경우를 앞부분에서 찾아낼 수도 있다.물론 여기서 말하는 정렬은 정수형 또는 ..

https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 맨해튼 거리 : x좌표 차이 + y좌표 차이 ✏️ 문제 풀이탐색 대상이 된 응시자를 기준으로, 다른 응시자에게 향하는 최적의 경로를 찾는 것이 아닌!맨해튼 거리가 2 이하일 때 도달할 수 있는지의 여부를 확인하면 되기 때문에너비 우선 탐색을 사용하고자 하였다.너비 우선 탐색 필수 요소 : 이동 방향 정의 int dirX[4] = {1, 0, -1, 0};int dirY[4] = {0, 1, 0, -1}; 너비 우선 탐색 필수 요소 : 방문 여부..

✏️ 문제 풀이처음 이 문제를 봤을 때, 대각선에 대한 직선의 방정식을 만들고 격자의 좌표를 대입하여 교차 여부를 확인하는 방법을 생각해보았다.그러나 쉽게 구현할 엄두를 내지 못했다.주어진 W와 H 입력의 최대값이 1억 이하의 자연수였기 때문이다.for(int i = 0; i 쿼드트리를 사용해볼까? 하는 고민도 해보았으나 쉽지 않았다.이런 나의 접근법과 일치하는 방법으로 푼 사람이 있었다.그 코드를 참고했다.long long solution(int w, int h) { long long answer = 0; for (int i = 0; i  1) 주어진 격자의 크기 w와 h로 직선의 방정식을 만든다.y = Gradient * xGradient = y좌표 간의 차 / x좌표 간의 차(0, 0),..

✏️ 문제 풀이 - 최대공약수로 비율을 구하기두 Weight의 최대공약수를 구한다.최대공약수가 없는 경우 넘어간다.최대공약수가 있는 경우 기존 무게에 각각의 비율을 적용해 일치하는 경우의 수를 찾아 카운트한다.이 경우 모든 비교에 대해 반복을 돌면서 최대공약수를 구해야 하기 때문에 비효율적으로 느껴졌다.(프로그래머스의 C++은 최대공약수를 구하는 함수 GCD) 굳이 최대공약수를 구할 필요없이 두 무게가 제시된 비율에 해당하는지 확인만 하면 된다.따라서 더 간단한 방법을 사용하고자 했다.X : Y = 2 : 33X = 2Y3X/2 = Y 비교 대상 중 하나인  Weight에 비율을 곱하고 나누어 시소의 균형을 이룰 수 있는 Y를 구하는 것이다.이분탐색 Binary Search 사용하기이분 탐색에는 lowe..

✏️ 문제 풀이새로운 문자일 경우 이를 저장한다.중복을 허용하지 않는 HasgSet을 사용하였다.HashSet seen = new HashSet();현재 문자가 이전 문자와 다를 경우, 이 문자가 나온 적이 있는지 확인한다.contains는 해시 테이블 기반 검색을 하기 때문에 for문 사용해 직접 검사하는 것보다 빠르다.나온적이 있다면 그룹 단어가 아니다. 아니라면 해당 문자를 저장한다.for (char ch : word.toCharArray()) { if (ch != prev) { // 새로운 문자일 경우만 검사 if (seen.contains(ch)) { // 이미 나온 문자라면 그룹 단어가 아님 return false; } seen.a..

✏️ 문제 풀이이번 문제 풀이는 간단하다.-가 등장할 경우, 그 뒤에 등장하는 수를 모두 합해서 뺀다.괄호를 원하는 위치에 삽입할 수 있기 때문에 -가 등장하면 그 뒤에 등장하는 모든 수를 따로 합해,전체 합계에서 뺄 수 있다. Pattern과 Matcher를 사용해 입력받은 문자열을 구분했다.+와- 또는 숫자인 경우의 앞뒤를 잘랐다.Pattern p = Pattern.compile("(\\d+|[+-])");Matcher m = p.matcher(s);List list = new ArrayList();while(m.find()){ list.add(m.group());}  🖥️ 코드 Scanner sc = new Scanner(System.in); String s = sc..

✏️ 문제 풀이long 사용입력받는 변수는 1,000,000,000이기 때문에 정수형 사용이 가능하다.그러나, 최대값이 1,000,000,000인 두 변수를 연산하기 때문에 그 결과는int의 표현 범위를 벗어날 수 있다.따라서, long 자료형을 사용하는 것이 좋다.(int로 받아도 무방하나 연산을 위해 long으로 형변환을 해줘야 하는 노고가 있기 때문이다.)1) 이동한 도시의 주유비가 현재 최소 주유비보다 쌀 경우, 최소 주유비를 해당 값으로 변경한다.long result = 0;long minCost = 1000000000;for (int i = 0; i 2) 이동할 때마다 이동 * 최소 주유비 값을 합계에 더한다.if(cost 🖥️ 코드 class Main { public static v..

✏️ 문제 풀이어떤 자료형을 사용할 것인가?동적 or 정적 배열?우선순위에 따라 데이터 정렬하기어떻게 탐색을 진행할 것인가? 1) 어떤 자료형을 사용할 것인가?시간의 최댓값은 2의 31-1이다.int로 표현할 수 있는 범위 내이기 때문에 int를 사용한다.(int는 2의 31승부터 표현을 못하기 때문에 long long을 사용해야 함)2) 동적 or 정적 배열?메모리 제한은 128MB이다.시작 시간과 끝나는 시간을 2차원 배열로 저장해야 하는데데이터의 최대 개수는 100,000로 정적 배열을 사용할 경우 배열의 크기는 100,000 X 100,000이다.100,000 * 100,000 * 4 byte = 400,000,000,000 byte1MB = 1,048,576 bytes (1024 × 1024)4..

[ 문제 풀이 ]1. 입력값이 정수형이 아닌 문자열이다.따라서, scanf 보다는 cin을 사용했다.char 변수를 통해 문자열의 한 글자씩 받아서 저장했다.for (int i = 0; i > img[i][j]; }} 2. 분할하기N을 길이로 사용해서 계속 절반씩 분할해 나간다.void QuadTree(int x, int y, int size) { int half = size / 2; QuadTree(x, y, half); // 왼쪽 위 ...}3. 재귀사용설정한 영역의 값이 모두 동일하지 않을 때, 재귀로 4 분할된 영역을 분할탐색하도록 설정했다.#include using namespace std;const int MAX = 64; // 최대 크기 64x..