https://softeer.ai/practice/6291 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 풀이기본적인 그리디 문제다.강의가 끝나는 시간으로 정렬빨리 끝나는 것부터 먼저 함(선택)그 다음 강의 시작시간이, 그 전 강의 종료시간보다 크거나 같으면 선택종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.로직1. 강의의 시작시간과 종료 시간을 저장하기 위한 클래스 Lecture를 만든다. Lecture는 종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.2. 강의의 개수 n을 입력받는다.3. 강의의 정보를 저장할 List lectures를 선언한다.4. n개의 강의의 시작시간과 종료시간을 입력받는다.5. lectures를 정렬한..
https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 풀이최장 증가 부분 수열 문제다.DP를 사용하여 풀 수 있으며 O(n^2) 의 시간복잡도를 가진다.DP를 사용하기 위해 돌의 개수 n만큼의 크기를 가지는 int형 1차원 배열 dp를 선언한다.dp[i] = i번째 돌이 마지막 돌일 때 철수가 밟을 수 있는 돌의 최대 개수 주의할 점dp[n-1]에 최댓값이 저장되지 않는다. 따라서 최댓값을 따로 저장하여 dp 배열의 값을 구할 때마다 최댓값을 업데이트해야 한다. 로직1. 돌의 개수 n을 입력받는다.2. 돌의 높이를 저장할 int[] stones 배열과, int[] dp 배열을 선언한다. 둘 다 크기는 n만큼 할당한다.3. 돌의..
https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 앞에서부터 두 수의 최소공배수를 구하고, 구한 최소공배수와 배열의 다음 수의 최소공배수를 또 구하고, 이런 과정을 반복해서 최종적으로 모든 수의 최소공배수를 구하면 된다. 로직 1. a, b, gcd, lcm 변수를 선언한다. 2. a와 lcm은 arr[0]으로 초기화한다. arr은 길이가 1이상인 배열이기 때문에 첫번째 원소가 바로 정답이 될 수 있기 때문이다. 3. for문에서 다음과 같..
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.www.acmicpc.net풀이반복적인 재귀 호출을 방지하기 위해, w(a, b, c)의 반환값을 저장하는 3차원 dp 배열을 사용한다.이 때 -50 ≤ a, b, c ≤ 50 이므로, 인덱스를 0부터 100까지 사용하기 위해 배열의 크기를 101x101x101만큼 할당하여 w(a, b, c)의 반환값을 dp[a+50][b+50][c+50]에 저장한다. 로직1. int형 3차원 배열 dp를 선언하고, 크기를 101x101x101만..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구해야 한다. 아래층으로 내려올 때, 아래층에 있는 수에서 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 즉, 현재 위치를 기준으로 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중 최댓값을 선택하여 그 수와 현재 위치의 수를 더한 값을 현재 위치의 배열에 저장하면 된다. 예시) 7 3 8..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 구해야 하므로 BFS를 사용한다. BFS 시작 위치는 캐릭터의 시작 위치와 같다. maps는 0과 1로만 이루어져 있으며 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타낸다. 캐릭터의 방문 여부를 나타내기 위해, 캐릭터가 방문한 칸은 maps에서 2 이상의 값으로 나타낸다. 즉, maps[x][y]는 (x, y)좌..
https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 시험 문제의 정답이 주어졌을 때, 1번, 2번, 3번 수포자의 점수를 구한 다음 높은 점수를 받은 수포자의 번호를 구해야 하며, 여러 명인 경우 오름차순으로 정렬하여 출력해야 한다. 1번, 2번, 3번 수포자의 점수를 구하는 로직은 따로 함수를 작성하여 구현하고, 구한 점수를 score 배열에 저장한다. 점수의 최댓값을 구한 후 그 최댓값을 가진 번호를 ArrayList에 저장한 다음 이 A..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 문제에서 주어진 대로 로봇 청소기의 동작을 구현하면 된다. 로직 1. static 변수로 n, m, cnt, room, dr, dc를 선언한다. cnt는 로봇 청소기가 청소하는 칸의 개수로 정답을 의미한다. room은 청소하는 영역의 상태 정보를 저장하는 2차원 배열로, 아직 청소하지 않은 경우에는 0, 벽인 경우에는 1, 청소한 경우에는 2를 저장한다. 1차원 배열 dr과 dc는 방향 배..
https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net풀이상담을 할 수 있는 가능한 모든 경우를 구한 다음 그 중에서 최대 수익을 구해야 한다. 예시를 들어 설명하겠다. 먼저 1일에 상담을 한다고 가정했을 경우(현재 수익 10), 2, 3일은 할 수 없으므로 4일로 넘어간다. 4일에 상담을 한다고 가정하면(현재 수익 30), 5일로 넘어가고 또 이때 5일에 상담을 한다고 가정하면(현재 수익 45), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 45가 된다.총 수익을 구한 다음 가장 최근 분기였던 5일째로 돌아간다. 5일에 상담을 하지 않는다고 가정하면(현재 수익 30), 6일..
https://school.programmers.co.kr/learn/courses/30/lessons/68644 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 numbers의 길이는 2 이상 100 이하이므로 이중 for문을 사용하여 두 개의 수를 더한 수를 ArrayList에 추가한다. Set이 아닌 ArrayList에 추가하는 이유는 이후 오름차순으로 배열에 저장해야 하기 때문에 Collections.sort() 메서드를 사용하기 위함이다. 로직 1. List list를 선언한다. 2. 이중 for문을 사용하여 두 개의 수를 뽑는다. 3. 뽑은..
https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 입력으로 들어온 모든 DNA와 Hamming Distance의 합이 가장 작은 DNA 를 출력해야 한다. 뉴클레오티드는 총 4가지이므로, 입력으로 들어온 n개의 DNA의 각 자리에 있는 글자들을 비교하여, Hamming Distance의 합이 가장 작은 뉴클레오티드를 찾으면 된다. 로직 1. n과 m을 입력받는다. 2. 입력으로 들어오는 DNA 문..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 캐시 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도..