해당 문제는 프로그래머스나, 백준과 같은 Judge Site 에서 확인한 것이 아닌 개인적인 경로로 본 알고리즘이다. 굉장히 재밌게 풀었던 문제여서 기록을 해둔다. (일반적인 DFS가 아닌 문자열에 대한 DFS, 그리고 그림을 그리는 과정? 에서 재밌게 느꼈다.) 먼저 문제에 대한 설명을 하자면 해상도가 1024인 사각형이 있다고 하자. 그 사각형에 대해 4분할하여 우선순위를 배열하고, 4분할된 사각형에 대해 다시 4분할을 진행하는 문제다. 문자열은 Black(B) / White(W) / P(Node) 로 나뉘어 있고, B/W/P에 대해서는 해당 사각형이 검정색인지, 하얀색인지, 노드인지에 대한 값이다. P는 큰 사각형에서 작은 사각형으로 들어갈 때 쓰이는 구분자이다. 예시) 큰 사각형(1번만 있는 이미..

https://programmers.co.kr/learn/courses/30/lessons/43163?language=kotlin 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 해당 알고리즘은 제한 조건에 신경쓰면 쉽게 풀 수 있는 문제다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 위 내용을 잘 체크하고, isValid 함수를 생성해 유망한지 체크 후 유망하다면 다음 DFS 재귀를 호출하면 된다. 1 ..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr DFS 관련 연습을 하다가 본 문제로, DFS를 이용해 풀어봤다. (DFS : 깊이 우선 탐색) 해당 문제는 BFS로도 풀 수 있다고 하는데, BFS는 잘 구현하지 못해 그나마 해본 DFS로 구현해봤다. Backtracking을 이용하려 하였으나 Backtracking을 구현하게 되면 isValid를 체크할 ..

https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 위 문제는 주어지는 W * H 만큼의 사각형에서 대각선으로 반으로 쪼갰을 때 사용할 수 있는 정사각형이 몇개인지를 구하는 문제다. (여기서 정사각형은 W * H 만큼의 수를 뜻한다. 예) 8 * 12의 사각형은 96개의 정사각형을 갖고있다.) 위 문제를 풀기 위해서는 일반적인 산수로는 안되고 유클리드 호제법 이라는 알고리즘을 사용해야한..

2020 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문자열 압축 알고리즘이 워낙 유명해서 한번 풀어봤다. 이 알고리즘을 풀 때의 핵심은 String의 Substring(문자열자르기)과 For문을 돌릴 때 Step을 주의하여 돌리면 된다. For문의 경우 뭐를 주의하냐면, 결국 문자열을 N개의 단위로 잘라서 표현을 해야하는 문제기 때문에, 초기 시작의 Fo..

프로그래머스 Level 2 문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 위 문제의 풀이 핵심은 User별 Nickname 관리를 진행하는게 핵심이다. UserID를 Key로 잡고 Nickname을 Value로 잡아서 Map을 활용해 문제를 해결했다. Change와, Leave 후 Enter 모두 User DATA에서 UserID가 있는지 확인하고 있다면 바꿔주고, User가 입력한 Commands를 ..