막 어려운 문제라기보다는, 생각의 전환을 잘 하고 싶어서 글을 적게 된 문제이다. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내가 푼 풀이 처음에는 dfs + dp를 이용해서 문제를 풀려고 했었다. 이전에 갔던 길이라면, 최단거리를 다시 구할 필요가 없기 때문이다. 이렇게 하니 답은 나왔지만, 시간 초과가 떠서 맞지 못했다. 아래는 그 dfs 코드이다. 이미 최단거리를 구했던 곳이라면 더이상 가지않고 최단거..
1. 삽입 정렬 (Insertion Sort) 설명 이미 정렬이 된 부분과 되지 않는 부분을 나누면서 정렬한다. 배열의 앞의 요소부터 차례대로 이미 정렬이 된 부분과 비교하여, 적합한 위치를 찾아 삽입하는 알고리즘이다. 두번째 요소부터 왼쪽의 요소들(이미 정렬이 된 부분)과 비교하여 삽입 위치를 찾아야한다. 이미 정렬이 된 부분과 비교연산을 할때는, 왼쪽으로 옮겨가며 비교를 하여 삽입 위치를 찾는다. 예시 1. [5, 3, 8, 1, 2, 7] → 두번째 원소인 3과 왼쪽의 이미 정렬된 배열인 [5] 와 비교 - 3과 5를 비교했을 때 5보다 작기 때문에 5를 한칸 뒤로 이동 : [3, 5] 2. [3, 5, 8, 1, 2, 7] → 세번째 원소인 8과 왼쪽의 이미 정렬된 배열인 [3, 5] 와 비교 -..
SWEA에서 모의 역량테스트 문제 풀어보다가 신기한?흥미로운? 문제를 발견해서 적어보려고한다. 또, 내가 푼 방법은 다른사람들이 주로 푼 방법과는 달라서 두가지 방법을 모두 정리해보려한다. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이..
이 문제는 좀 문제(?)가 있는 문제라고도 할 수 있다. 시간복잡도적으로 더 효율적인 코드를 알게 되어서 그 내용을 정리해보려고한다. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 일단, 재귀 + 백트래킹으로 풀 수 있는 문제다. 그렇게 풀어도 통과할 수 있다. 나 또한 그렇게 풀었다. class Solution { int answer = 0; public int solution(int[] info, int[][] edges) ..
해커랭크에 있는 Lily's Homework 문제에 대해 정리해보려고한다. 어떤 알고리즘을 써야 적합한지에 대해서는 생각해냈지만, 구현방식을 생각해내지 못해 몇개의 테스트케이스에서 시간초과가 났다. 해결 과정 먼저, 문제를 읽고 도출해야하는 것이 크게 두가지라고 생각한다. 1. "인접한 인덱스의 원소의 차가 가장 작게 만들어야한다" -> 오름차순이나 내림차순으로 정렬이 되어야한다는 말이다. 2. "두 인덱스를 최소 횟수로 swap하여 1번 상태를 만들어야한다." -> 정렬 방법 중에 선택 정렬을 한다. 그런데, 선택 정렬은 시간복잡도가 O(N^2)이다. 기준 인덱스를 모두 도는 것이 (N) * 나머지 인덱스 중에 가장 작거나 큰 값 찾기 (N-1) 이 문제의 N의 최대값은 10^5이기 때문에 시간초과가 ..
문제를 읽어봤을 때 대충 풀어봤던 백준 문제 중에 '치즈' 라는 문제와 비슷해보여서 쉬울 줄 알았다. 백조가 만나야한다는 요소만 추가된 문제인줄 알았다. 그렇지만 플레5인 이유가 있었다..! '치즈'에서 풀었던 방식으로 똑같이 풀으려했더니 시간초과가 났다. 그래서 다른사람들의 풀이를 참고하여서 다시 풀어보았다. https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 더보기 문제 두 마리의 백조가 호수에서 살고 있었다...
[프로그래머스] 택배 배달과 수거하기 - 23 카카오 채용 (Java)
그리디 문제다. 내가 푼 방법은 테스트케이스 17번 딱 하나가 시간초과로 절대 풀리지 않았다. 그러던 중 질문하기 탭에서 엄청난 풀이를 발견했다. !!! 그래서 그 풀이를 정리해보려고 한다. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 더보기 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다..
[프로그래머스] 등산코스 정하기 - 22 카카오 인턴 채용 (Java)
코딩테스트에서 풀었던 문제다. 물론 100점을 맞지는 못했던 문제라서 내가 풀었던 풀이를 다시 살펴보고, 문제를 다시 풀어보았다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2022 테크 여름인턴십 코딩테스트 해설 2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금 tech.kakao.com 문제 설명 더보기 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터,..