개발왕 찌 (۶•̀ᴗ•́)۶

Kakao Blind Recruitment 2021 문제 날짜 분류 번호 알고리즘 분류 21-03-25 프로그래머스 60057 문자열 링크 문제 요약 문자열을 앞에서부터 n개씩 잘랐을 때 같은 값이 연속해서 나오면 반복해서 나온 개수``반복된문자열로 줄인다 ex) ababrtrt => 2ab2rt n개씩 자르고 남은 문자열은 뒤에 붙여줌 압축한 후의 길이를 비교해서 가장 짧은 것을 정답으로 반환 풀이 길이를 1~문자열의길이 반복 idx를 0부터 길이만큼 늘려주면서 반복 이전 문자열과 지금 문자열을 비교해서 같으면 cnt 증가 다르면 String builder인 result에 cnt와 직전 문자열을 붙여줌 cnt가 1이면 붙이지 않음 pre=cur을 해주고, cnt는 1로에 초기화 남은 문자열 털어넣기 비..

2019 KAKAO BLIND RECRUITMENT 문제 날짜 분류 번호 알고리즘 분류 21-03-29 프로그래머스 42892 트리, 재귀 링크 문제 요약 트리를 구성하는 노드들이 2차원 좌표 위에 주어졌을 때 전위 순회, 후위 순회한 결과를 반환 규칙 모든 노드는 서로 다른 x값을 가짐 자식 노드의 y 값은 항상 부모 노드보다 작음 모든 노드는 왼쪽 서브 트리에 있는 노드들의 x값보다 작음 풀이 pq에 Node를 row순, col순으로 정렬하여 넣음 pq에서 하나씩 빼면서 tree에 넣음 트리가 완성되면 재귀를 통해 탐색함 비고 설마 이게 되겠어? 했는데 됐다 우하하 더보기 package KakaoBlindRecruitment2019.P42892_길찾기게임; import java.util.ArrayLi..

날짜 분류 번호 알고리즘 분류 21-03-25 프로그래머스 72413 다익스트라 링크 문제 요약 S에서 A와 B로 가는 최소 비용 같은 곳을 지나친다면 합승해서 함께 감 풀이 S로부터 모든 지점까지의 거리를 다익스트라로 계산 A와 B도 마찬가지 S, A, B로부터 거리를 저장한 배열 3개를 가지고 어느 점까지가 최소 거리인지 반복문을 돌려서 찾음 비고 처음에는 모든 점에 대해서 다익스트라를 구해서 S까지거리+A까지거리+B까지거리를 찾았는데 시간초과가 났음 더보기 package KakaoBlindRecruitment2021.P72413_합승택시요금; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; impor..

날짜 분류 번호 알고리즘 분류 21-03-25 프로그래머스 60057 문자열 링크 문제 요약 문자열을 앞에서부터 n개씩 잘랐을 때 같은 값이 연속해서 나오면 반복해서 나온 개수``반복된문자열로 줄인다 ex) ababrtrt => 2ab2rt n개씩 자르고 남은 문자열은 뒤에 붙여줌 압축한 후의 길이를 비교해서 가장 짧은 것을 정답으로 반환 풀이 길이를 1~문자열의길이 반복 idx를 0부터 길이만큼 늘려주면서 반복 이전 문자열과 지금 문자열을 비교해서 같으면 cnt 증가 다르면 String builder인 result에 cnt와 직전 문자열을 붙여줌 cnt가 1이면 붙이지 않음 pre=cur을 해주고, cnt는 1로에 초기화 남은 문자열 털어넣기 비교 비고 테케 5번이 하나 틀렸는데.... 바로바로,,, ..

재귀 + backtracking 문제 요약 숫자로만 이루어진 문자열이 주어졌을 때 이 문자열에서 가능한 모든 IP 주소를 담은 List 반환 순서는 상관 X 유효한 IP주소의 조건 4개의 정수로 이루어짐 정수 사이 '.'으로 구분 0~255만 가능 0을 제외하고 맨 앞에 0이 있으면 안됨 ex) 0.0.32.34 => 가능 ex) 255.255.055.0 => 불가능 풀이 재귀로 풀었음 depth==4가 되면 가능한 ip이므로 list에 추가 주어진 문자열을 총 4개로(이게 depth) 쪼개야 하는데 각 depth마다 맨 앞에서부터 문자열 1개/2개/3개씩 검사 canIP로 유효한 IP주소를 구성하는 숫자인지 확인 가능하다면 재귀함수 호출 현재 남은 depth의 개수가 str의 개수보다 작으면 더이상 조..

DFS 문제 요약 2차원 배열에서 가장 긴 등산로 만들기 규칙 가장 높은 봉우리에서 시작 4방 탐색 높은곳에서 낮은곳으로만 이동 가능 (같은 곳X) 딱 한번 최대 K만큼 높이를 깎을 수 있음 풀이 최대지점(봉우리)부터 dfs 직전 높이보다 낮으면 dfs, 같거나 높으면 높이를 깎은적이 없는 경우에만 최대 K만큼 깎아서 이동할 수 있는지 확인해서 dfs 비고 풀이 자체는 금방 떠올랐으나 예외 잡는 데에 오래 걸림 ㅠㅠ 더보기 package s01.SWEA_1949_등산로조성; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int ..

날짜 분류 번호 알고리즘 분류 링크 21-03-13 프로그래머스 12987 그리디 programmers.co.kr/learn/courses/30/lessons/12987 문제 요약 A팀 N명과 B팀 N명이 각각 무작위로 자연수를 부여받았을 때, B팀의 최대 승점 구하기 게임 규칙 A팀 한명과 B팀 한명이 서로 수를 비교하여 큰 수를 가진 팀에 +1점, 동일할 경우 둘 다 0점 모든 사람은 한번만 출전 가능하며, 서로 동일한 숫자를 가질 수 있음 B팀은 A팀의 출전 순서를 앎 풀이 A팀과 B팀을 카드 숫자에 따라 오름차순 정렬 A팀을 기준으로 반복문을 돌리면서 현재 A팀 출전 숫자보다 큰 숫자를 가진 B팀의 팀원이 나올 때까지 b의 인덱스를 증가 비고 레벨 3인데 너무 허무하게 풀려서 당황 ㅎ 더보기 pa..

날짜 분류 번호 알고리즘 분류 링크 21-01-19 BOJ 20366 이분탐색 www.acmicpc.net/problem/20366 문제 요약 N개의 눈덩이 중 4개를 골라 눈두덩이 2개로 만들어진 눈사람 2쌍을 만든다. 이중 두 눈사람의 키 차이가 최소가 되는 값 구하기 눈덩이의 키 = 지름 풀이 눈덩이의 키 순서로 정렬 정렬된 상태에서 a, b, c, d 순차적으로 골랐다고 가정했을 때 a+d와 b+c의 차이가 abcd로 만들수 있는 눈사람의 키 차이임 a, b, d를 3중 for문으로 돌리고(ㅌㅋㅋㅋ ㅠㅠ ) 나머지 c를 b+1과 d-1 사이에서 c의 값 찾기... lower bound로 c의 값 구함 c-1의 값도 고려함 (c-1와 a, b, d가 다를 경우에만) 비고 N이 600인데 시간 제한이..

날짜 분류 번호 알고리즘 분류 링크 21-01-20 BOJ 2585 이분탐색&bfs www.acmicpc.net/problem/2585 문제 요약 (0, 0)에서 (10000, 10000)까지 이동할 수 있는 최저의 연료통 용량 구하기 단, 중간에 주유를 할 수 있는 횟수는 K번 이하여야 함 참고사항 연료의 단위는 1L이며 1L당 10km 비행 가능 두 지점의 거리는 평면상의 거리임 풀이 (0, 0)에서 (10000, 10000)까지 필요한 연료량을 r(최대값)으로 두고 이분탐색 진행 mid로 목적지까지 도착할 수 있는지 없는지를 확인 bfs 사용 que에서 좌표를 하나 꺼내고 주어진 연료량으로 목적지까지 갈 수 있으면 true 반환 목적지까지 갈 수 없는데 연료횟수가 K번이면 다음 좌표로 넘어감 목적지..

날짜 분류 번호 알고리즘 분류 링크 21-01-18 BOJ 17940 다익스트라 www.acmicpc.net/problem/17940 문제 요약 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로 찾기 지하철은 2개의 회사에서 운영하고 있으며, 운영하는 회사가 바뀔 때마다 환승 1회로 계산 풀이 다익스트라 지하철역 번호, 환승횟수, 누적 비용을 포함하는 객체를 만들어서 환승횟수와 비용을 가지고 PQ에 정렬 비고 PQ를 사용한 다익스트라로 간단하게 풀 수 있는 문제 더보기 package b17.BOJ_17940_지하철; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; imp..