알고리즘/프로그래머스
-
[프로그래머스] 시험장 나누기 / 2021 카카오 채용연계형 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 6. 23:00
🖇️ 문제 링크 코딩테스트 연습 - 시험장 나누기 카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다. 하나의 노드는 하나의 시험장을 나타냅니다. 검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다. 2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다. 노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다. https://programmers.co.kr/learn/courses/30/lessons/81305 📝 문제 분석 그리디, 최적화 결정 문제, 트리 등 복합적인 풀이가 필요한 문제였습니다. k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 리턴해야 하..
-
[프로그래머스] 미로 탈출 / 2021 카카오 채용연계형 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 6. 23:00
🖇️ 문제 링크 코딩테스트 연습 - 미로 탈출 신규 게임 '카카오 미로 탈출'이 출시되어, 라이언 이 베타테스터로 참가했습니다. 위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다. https://programmers.co.kr/learn/courses/30/lessons/81304 📝 문제 분석 평범한 다익스트라 문제에 트랩이라는 매커니즘을 적용시켜야 하는 문제입니다. 트랩은 최대 10개가 있을 수 있기 때문에 2..
-
[프로그래머스] 표 편집 / 2021 카카오 채용연계형 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 6. 22:59
🖇️ 문제 링크 코딩테스트 연습 - 표 편집 업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행 을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. https://programmers.co.kr/learn/courses/30/lessons/81303 📝 문제 분석 최대 100만개의 원소가 있고, 최대 20만번의 명령을 수행해야 합니다. 삭제 명령이 있기 때문에 배열을 사용하게 된다면 시간 내에 수행할 수 없습니다. 양방향 연결리스트를 구현하여 원소 삭제와 원소 복원..
-
[프로그래머스] 거리두기 확인하기 / 2021 카카오 채용연계형 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 6. 22:59
🖇️ 문제 링크 코딩테스트 연습 - 거리두기 확인하기 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요. https://programmers.co.kr/learn/courses/30/lessons/81302#fnref1 📝 문제 분석 BFS 탐색을 진행합니다. 거리가 3 이상이라면 더 이상 탐색하지 않아도 됩니다. 파티션으로 막혀 있을 경우 더 진행할 수 없으며, 자신이 아닌 응시자를 발견하면 FALSE..
-
[프로그래머스] 숫자 문자열과 영단어 / 2021 카카오 채용연계형 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 6. 22:59
🖇️ 문제 링크코딩테스트 연습 - 숫자 문자열과 영단어문제 설명 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다.https://programmers.co.kr/learn/courses/30/lessons/81301 📝 문제 분석영어로된 숫자와 배열 인덱스를 맞춰놓고, replace를 사용해서 숫자로 변..
-
[프로그래머스] 동굴 탐험 / 2020 카카오 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 5. 00:03
🖇️ 문제 링크 코딩테스트 연습 - 동굴 탐험 오지 탐험가인 프로도 는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. https://programmers.co.kr/learn/courses/30/lessons/67260 📝 문제 분석 💡 before[y] = x → y를 방문하기 전에 x를 방문 해야 됨 after[x] = y → x를 방문 후에 y를 방문 해야 됨 discovered[y] → y에 갈 수 있는 경로가 있다는 것을 확인은..
-
[프로그래머스] 경주로 건설 / 2020 카카오 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 23:36
🖇️ 문제 링크 코딩테스트 연습 - 경주로 건설 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다. https://programmers.co.kr/learn/courses/30/lessons/67259 📝 문제 분석 [0, 0]에서 [N - 1, N - 1]까지 도달하는 그래프 탐색 문제입니다. 탐색하는 방향에 따라서 비용이 달라지기 때문에 방향에 따른 최솟값을 저장하고 있어야 합니다. 여기서는 세로 방향과 ..
-
[프로그래머스] 보석 쇼핑 / 2020 카카오 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 23:36
🖇️ 문제 링크 코딩테스트 연습 - 보석 쇼핑 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. https://programmers.co.kr/learn/courses/30/lessons/67258 📝 문제 분석 보석 종류의 개수를 구하고 시작합니다. (스트림 사용) 해시맵과 큐에 보석을 하나씩 넣습니다. 맵에 보석 전체 종류가 다 들어가게 되면, 모든 보석이 다 있어야..