Algorithm
[백준(Python/Java)] 2206_벽 부수고 이동하기(BFS)
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 일반적인 BFS 문제에서 "벽을 부술 수 있는 기회가 1회" 추가된 문제입니다. 따라서 이 문제를 해결하기 위해서는 "어느 벽 하나를 부술 것인가?"를 정할 수 있어야 합니다. 하지만, 임의의 벽을 하나 제거하고 BFS를 수행하는 행위를 반복하면 시간초과가 발생하기 때문에 한 번의 BFS를 진행하는동안 "벽을 부순 상태인지, 부수지 않은 상태인지'를 큐에 담고 다녀야 합니..
Algorithm
[프로그래머스(파이썬/Python)] 숫자 문자열과 영단어(2021 카카오 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr replace 메서드를 사용해서 정말 쉽게 풀 수 있는 문제입니다. 파이썬의 replace 내장 함수는 자바의 replaceAll 함수처럼 해당되는 모든 문자열을 다른 문자열로 치환해주기 때문에, 아래 풀이처럼 number 배열에 있는 문자열이 존재한다면 해당 문자열의 인덱스를 이용하여 숫자로 바꿔주면 됩니다. [풀이] def solution(s): ..
Algorithm
[프로그래머스(파이썬/Python)] 복서 정렬하기(위클리 챌린지 6주차)
https://programmers.co.kr/learn/courses/30/lessons/85002 코딩테스트 연습 - 6주차 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 문제에서 요구한 4가지 기준값을 정확히 구하고 해당 기준에 따라 정렬을 수행하면 되는 문제입니다. 특히 이 문제에서는 주어진 weights 배열과 head2head배열 내 원소의 문자열 길이가 동일했기 때문에 인덱싱을 쉽게 할 수 있다는 이점이 있었습니다. 다만, 많은 기업의 코딩테스트 문제들과 마찬가지로 테스트케이스가 모두 통과..
Algorithm
[프로그래머스(파이썬/Python)] 길 찾기 게임(2019 카카오 블라인드)
https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 이 문제의 핵심은 (x, y) 형태로 주어진 점들을 어떻게 이진트리 형태로 만들 것인가였다고 생각합니다. 이진 트리를 만들기만 하면 순회같은 경우에는 재귀 함수를 이용해 쉽게 구현할 수 있기 때문이죠. 제가 이진 트리를 만들기 위해 수행했던 로직을 간단히 정리하면 아래와 같습니다. 1) 우선 주어진 (x, y) 점들에 대한 키값으로 인덱스 번호를 붙여서 딕셔너리 ..
Algorithm
[프로그래머스(파이썬/Python)] 거리두기 확인하기(2021 카카오 개발자 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 이 문제는 실제 인턴십 지원을 했을 때 봤던 코딩테스트에서 굉장히 빨리 풀었던 문제입니다...
Algorithm
[프로그래머스(파이썬/Python)] 후보키(2019 카카오 블라인드)
https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 카카오 기출 문제는 꼭 한 번씩 2~3개의 테스트케이스가 틀리는 경우가 많은 것 같습니다. 맞왜틀도 실력이라고 생각하기 때문에 아직 갈 길이 먼 것 같습니다... 이 문제는 주어지는 컬럼의 수가 1이상 8이하이고, 릴레이션의 개수도 20이하..
Algorithm
[프로그래머스(파이썬/Python)] 모음사전
https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차_모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 애초에 문제에서 만들 수 있는 단어의 모든 가지 수가 크지 않았기 때문에 중복 순열을 이용해서 풀 수 있었습니다. 단어의 길이가 1부터 5까지인 모든 단어를 리스트에 입력한 뒤 정렬을 하고, 해당 단어가 몇 번째에 있는지 index 내장 함수로 찾아주기만 하면 되겠죠! 풀이는 아래와 같습니다. [풀이] fro..
Algorithm
[프로그래머스(파이썬/Python)] 보석 쇼핑(2020 카카오 개발자 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 카카오의 효율성 문제를 풀면 눈물이 납니다. 이 문제를 풀 때도 1) O(N^2)으로 몇 가지 트릭을 넣은 풀이, 2) 이분 탐색으로 O(N*logN), 두 가지 방법을 시도해보았지만 모두 다 효율성 테스트를 통과하지 못했습니다... 사실, 이 문제에서 투 포인터를 써야겠다는 생각은 바로 들었지만 뭔가 계속 구현이 꼬이고 몇 가지 테스트 케이스가 틀리고를 반복하다보니 다른 방법으로 회피한 것 같은 느낌도 있었습..
Algorithm
[백준(파이썬/Python)] 1644_소수의 연속합(투 포인터, 에라토스테네스의 체)
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net N이 클 때 소수 판별을 효율적으로 할 수 있는 에라토스테네스의 체와 투포인터 개념을 활용하는 문제입니다. 에라토스테네스의 체는 소수 판별할 때 대표적인 알고리즘으로 "임의의 정수 x가 소수라면, x의 배수는 소수가 아니다"라는 명제를 이용해 구현하는데요. 이를 구현하는 방법은 아래 코드에서 prime_list() 함수로 구현되어 있습니다. 한편, 문제에서 구하고자 하는 것은 어떤 수 N을 연속한 소수의 합으로 나타낼 수 있는 경우의 수입니다. 따라서, 에라토스테네스의 체로 구한 N보다 작은 소수들의 집합을 리스트로..
Algorithm
[프로그래머스(파이썬/Python)] 수식 최대화(2020 카카오 블라인드 채용)
https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 2020년 카카오 블라인드 채용에 있는 문제로, 문제의 요구사항을 충실히 구현하면 되는 문제입니다. 우선 문자열로 주어진 expression을 splitExpression() 함수를 구현해서 숫자와 연산자 집합으로 분리를 했습니다. 문제 조건에서 "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다. 라는 내용이 있기 때문에, numbers..
