CS/Algorithm
[백준(Python/Java)] 1987_알파벳 - DFS
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(DFS)을 통해 가장 긴 알파벳을 찾는 문제였습니다. 기존에 풀었던 많은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)를 문제에서는 방문한 곳을 true로 체크하여 재방문을 하지 않도록 알고리즘을 설계했습니다. 하지만 이 문제에서는 깊이 우선 탐색을 하여 방문한 곳들이 최적해가 되지 않을 때, 다시 그 곳들의 방문 여부를 false로 복원하여 다음 탐색에서 방문할 수 ..
CS/Algorithm
[백준(Python/Java)] 2234_성곽(DFS, 비트마스킹)
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 약간의 비트마스킹을 사용해서 푸는 문제인데, 비트마스킹이 중심인 문제는 아니라고 생각합니다. 단순히 각 방에 위치하는 벽의 정보를 이진수로 바꾸고 남동북서 방향으로 바꿔서 읽어주면 되는 것이죠. 예를 들어, 어떤 방의 벽에 대한 값이 11이라면 11을 2진수로 바꾼 뒤 남동북서 방향으로 네 자릿수를 채우면 0111이 됩니다. 즉, 남쪽에 대한 값만 0로 이동가능하고, 동북서에 대한 값은 1로..
CS/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를 진행하는동안 "벽을 부순 상태인지, 부수지 않은 상태인지'를 큐에 담고 다녀야 합니..
CS/Algorithm
[프로그래머스(파이썬/Python)] 숫자 문자열과 영단어(2021 카카오 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr replace 메서드를 사용해서 정말 쉽게 풀 수 있는 문제입니다. 파이썬의 replace 내장 함수는 자바의 replaceAll 함수처럼 해당되는 모든 문자열을 다른 문자열로 치환해주기 때문에, 아래 풀이처럼 number 배열에 있는 문자열이 존재한다면 해당 문자열의 인덱스를 이용하여 숫자로 바꿔주면 됩니다. [풀이] def solution(s): ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 복서 정렬하기(위클리 챌린지 6주차)
https://programmers.co.kr/learn/courses/30/lessons/85002 코딩테스트 연습 - 6주차 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 문제에서 요구한 4가지 기준값을 정확히 구하고 해당 기준에 따라 정렬을 수행하면 되는 문제입니다. 특히 이 문제에서는 주어진 weights 배열과 head2head배열 내 원소의 문자열 길이가 동일했기 때문에 인덱싱을 쉽게 할 수 있다는 이점이 있었습니다. 다만, 많은 기업의 코딩테스트 문제들과 마찬가지로 테스트케이스가 모두 통과..
CS/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) 점들에 대한 키값으로 인덱스 번호를 붙여서 딕셔너리 ..
CS/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 이 문제는 실제 인턴십 지원을 했을 때 봤던 코딩테스트에서 굉장히 빨리 풀었던 문제입니다...
CS/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이하..
CS/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..
CS/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), 두 가지 방법을 시도해보았지만 모두 다 효율성 테스트를 통과하지 못했습니다... 사실, 이 문제에서 투 포인터를 써야겠다는 생각은 바로 들었지만 뭔가 계속 구현이 꼬이고 몇 가지 테스트 케이스가 틀리고를 반복하다보니 다른 방법으로 회피한 것 같은 느낌도 있었습..
