Programmers
[Programmers] 단어 변환 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 BFS 문제이다. 알고리즘 begin 문자열과 0을 같이 큐에 넣는다. 큐가 빌 때까지 아래의 실행을 한다. 큐에서 현재 문자열과 단계를 꺼낸다. 모든 진행 가능한 word 문자열에 대해 다음을 실행한다. 만약 해당 문자열에 이미 방문했다면 지나친다. 현재 문자열과 word 문자열의 다른 부분이 1개라면 방문 처리 하고 word를 단계 + 1 해서 큐에 삽입한다. 만약 삽입할 문자열이 ta..
[Programmers] 최고의 집합 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정말 놀랍게도... 일부러 찾은 문제가 아닌데도... 이전에 문제를 잘못 접근해서 엉뚱한 방식으로 풀었는데 그 방식으로 풀면 되는 문제였다. 알고리즘 그리디 알고리즘이다. 곱의 최대는 똑같이 배분하면 나온다. 즉, 10를 3개로 쪼개서 곱할 때 최대는 [3, 3, 4] 일 때이다. 증명 s = k + k + ... + k 이와 같이 균등하게 분배되어 있을 때, 이게 최선이 아니라고 가정해보자. 그..
[Programmers] 야근 지수 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자의 범위가 큰 수를 처리해야 하므로 일일이 처리하는 게 아니라 그리디라고 착각했다. 쉽게 구할 수 있는 수식이 있을 거라고 생각해 잘못된 생각을 했다. 남은 작업량을 모두 더해 일을 최대한 한 뒤 남은 일에 고르게 분배했다. 하지만 이러면 일이 한 쪽에 치우쳐져 있을 경우를 생각하지 못한다. 그래서 일일이 처리할 수 밖에 없다는 생각이 들었다. 알고리즘 아주 간단하게 생각했을 때 O(N^2)은..
[Programmers] 2023 KAKAO BLIND RECRUITMENT : 택배 배달과 수거하기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 실제 시험에서 못 풀었던 문제다. 그리디와 최적화가 필요한 문제이다. 그리디적인 아이디어를 떠올리긴 어렵지 않지만, 매번 배달 거리를 처음부터 계산하도록 코딩하면 O(N^2) 이다. 인덱스를 기억해서 O(N) 으로 바꿔야 한다. 알고리즘 그리디 배달과 수거를 할 때, 제일 먼 곳부터 배달/수거하면 된다. 조금만 생각해보면 먼 곳부터 다녀오면서 거리를 줄여나가는 것이 최적이라는 것을 생각할 수 있..
[Programmers] 네트워크 (C++)
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 8분 50초 알고리즘 간단한 BFS 혹은 DFS 문제이다. 이 문제는 어떤 것으로 풀어도 나쁘지 않지만, 코드 구현은 BFS보다 재귀를 사용하는 DFS가 간단한다. 방문체크는 vis라는 배열로 처리하고, 방문하지 않은 노드를 발견하면 카운트를 하고 DFS를 실행하면 끝이다. 정답 코드 #include #include using namespace std; bool vis[201]; v..
[Programmers] 정수 삼각형 (C++)
https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 10분 알고리즘 대표적인 DP 문제이다. 거쳐가는 숫자들을 더해서 저장해놓는 memo 배열을 채워가며, memo의 마지막 열 값들 중 최댓값을 리턴한다. 정답 코드 #include #include using namespace std; int memo[501][501]; int solution(vector triangle) { int answer = 0; memo[0][0] = tri..
[Programmers] JadenCase (C++)
https://school.programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 8분 알고리즘 첫 문자가 소문자이면 대문자로 바꾼다. 그 후 모든 문자를 검사하며 다음을 실행한다. 해당 문자가 공백이면 다음 문자가 소문자인지 검사하고 대문자로 바꾼다. 해당 문자가 대문자이면 이전 문자가 공백이 아닌지 검사하고 소문자로 바꾼다. 정답 코드 #include #include using namespace std; string solution(string s) { if ..
[Programmers] 최댓값과 최솟값 (C++) with 문자열 파싱 (토큰 분리)
https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 8분 29초 문자열 파싱을 위한 split 함수를 공부하기 위해 푼 문제이다. C++은 Python이나 Java와 같이 다른 언어와 달리 토큰분리를 간단하게 할 수 있는 라이브러리 함수를 제공하지 않아 스스로 만들어서 쓰면 좋다. 알고리즘 #include 을 해준 후, 문자열에서 stringstream을 생성해 getline 함수로 토큰분리를 한다. 밑의 함수를 통째로 외우는 것도 ..
[Programmers] 2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금 (C++) with 플로이드
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 31분 02초 프로그래머스에서 레벨2의 문제도 상당히 애를 먹은 게 많아 레벨3를 도전하기 어려웠다. 레벨3를 처음 도전해본 문제인데, 레벨2보다 쉬운데...? 싶은 느낌이다. 이거 레벨 누가 매기는 거지... 보고 문제를 해석하자마자 플로이드 알고리즘부터 생각났다. 하지만 플로이드 관련 문제를 푼지 오래된 것 같아 확실하게 공부해보고자 다른 문제를 풀고 넘어왔다. https://m..
[Programmers] 2020 KAKAO BLIND RECRUITMENT : 문자열 압축 (C++)
https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 46분 43초 차근차근 해나가면 어렵지 않은 문자열 문제다. 단, 해줘야 할 예외처리가 꽤 많은 편이다. 알고리즘 for 문으로 1부터 문자열 길이의 절반까지 모두 단위로 생각해 문자열을 압축해본다. 문자열 길이의 절반이 넘을 경우 압축이 될 수가 없으므로 압축해볼 필요가 없다. 여기서, 문자열의 길이가 1일 경우 예외처리를 해야 한다. 마지막에 테스트해보다가 알게 되었다. 테스트케..