알고리즘
-
알고리즘) 카카오 블라인드 채용 2020, 기둥과 보 설치알고리즘/프로그래머스 카카오 2020. 5. 7. 00:35
Kakao Blind Recruitment 2020 기둥과 보 설치 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 주목할 점 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다. 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다. 바닥에 보를 설치 하는 경우는 없습니다. 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다. 구조물이 겹치도록 설치하는 경우와, 없는 ..
-
알고리즘) 2019 카카오 개발자 겨울 인턴십, 징검다리 건너기알고리즘/프로그래머스 카카오 2020. 5. 7. 00:24
2019 카카오 개발자 겨울 인턴십 징검다리 건너기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 투 포인터 알고리즘으로 풀다가 효율성 13번만 시간 초과가 뜨길래 이진 탐색으로 풀었다. 이진탐색이기에 left, mid, right를 무엇으로 잡을 것인지가 핵심이다. 1. 돌의 stepping 수(=건널 수 있는 사람의 수) 최소값, 최대값을 각각 left, right에 넣어준다. 2. while문을 돌면서 mid 값 (건널 수 있는 사람의 수 예상 답)과 비교하면서 건널 수 있을 경우에는 answer을 저장해주고 최소인 left를 mid+1로 저장..
-
알고리즘) 카카오 블라인드 채용 2020, 가사 검색알고리즘/프로그래머스 카카오 2020. 5. 3. 00:30
Kakao Blind Recruitment 2020 가사 검색 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주목해야할 조건 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다. 풀이 처음 문제를 보고 어? 쉽네? 라고 접근했다. 선형 loop를 통해 조건에 맞는지 확인하고 count를 업데이트 하는 식으로 짰다. 하지만, 역시나 카카오는 쉬울리가 없다.. 효율성에서 1,2,3번이 틀렸다. 여기서 '아.. Trie구나' 라고 생각했다. Trie를 떠올린 것 까지는 좋았..
-
알고리즘) 카카오 블라인드 채용 2020, 자물쇠와 열쇠알고리즘/프로그래머스 카카오 2020. 5. 1. 16:17
Kakao Blind Recruitment 2020 문자열 압축 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 DFS로 해야하나 고민하다가, 열쇠가 회전하는 경우(+4) 열쇠의 이동 범위 등을 생각하면 시간초과가 분명할 것 같아서 포기했다. 오래 고민하다가 감이 안잡혀서 다른 분들의 로직을 참고했는데, 자물쇠의 크기를 3배 확장하는 방법이 존재했다.. 생각보다 간단한 문제여서 크게 반성했다.. 어렵게만 접근한 것 같았다.. 이후 로직은 스스로 생각했다. 1. 자물쇠의 크기를 3배 확장하고, 원래 자물쇠의 정보를 확장한 배열의 정중앙에 둔다...
-
알고리즘) 카카오 블라인드 채용 2020, 괄호 변환알고리즘/프로그래머스 카카오 2020. 5. 1. 16:03
Kakao Blind Recruitment 2020 괄호 변환 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아..
-
알고리즘) 카카오 블라인드 채용 2020, 문자열 압축알고리즘/프로그래머스 카카오 2020. 5. 1. 15:53
Kakao Blind Recruitment 2020 문자열 압축 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다. 풀이 (2020.05.01) 문자열을 제일 앞부터 정해진 길이만큼 자르는게 중요해서 저 조건만 따로 적어봤다. 처음 문자열 부터 자르는 것과 중복되는 문자열의 갯수를 파악하는 것에 주의한다면 어려운 문제는 아니었다..
-
알고리즘) 프로그래머스 Graph, 사이클 제거알고리즘/프로그래머스 고득점 Kit 2020. 5. 1. 15:37
프로그래머스 고득점Kit - Graph 사이클 제거 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다. 전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, ..
-
알고리즘) 프로그래머스 Graph, 순위알고리즘/프로그래머스 고득점 Kit 2020. 4. 27. 16:14
프로그래머스 고득점 Kit - Graph 순위 풀이 (2020.04.27) 문제의 조건에서 경기 결과에 모순이 없으며, A>B, B>C 이면 항상 A>B>C의 순서가 매겨진다고 되어있다. 따라서, 경기 결과가 유실되어도 특정 선수(A)가 이긴 상대들은 A를 이긴 상대들이 이길 수 있다는 뜻이다. 경기 결과 입력 후, 서로 상관관계에 따라 입력을 해주고 랭킹을 부여할 수 있는 선수들을 찾아 return했다. 1. 전체 경기 결과를 이긴 상대 리스트, 진 상대 리스트에 담아준다. (선수 Index에 맞춰서) 2. 서로 경기 결과에 대해 이기고 진 상대들을 업데이트 해준다. 3. 경기 결과가 모두 있는 선수들은 Rank를 부여할 수 있으므로, 전체 경기 결과가 있는 선수들의 수를 return해준다. (2020..