Young

https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 오늘은 2020 카카오 신입사원 코딩 테스트 3번째 문제입니다. 이 문제는 무려 정답률 7%를 자랑하는 문제입니다. 설계를 생각해내기 조금 힘들수도 있습니다. 그냥 머릿속으로 시뮬레이션을 돌려보면 꽤나 간단한게 보이는데 실제 구현에 들어가면 난해합니다. 이 문제에서 배울 수 있는 것을 알아보겠습니다. 1. 지도를 90도 돌려서 기존 코드를 재사용할 수 있는 경우가 있음을 인지하자. 2. 지도를 ..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 | 프로그래머스 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 programmers.co.kr 카카오 코딩테스트는 어렵기로 유명합니다. 당분간 카카오 코딩테스트 풀이를..

'재귀함수를 이용한 완전탐색의 기본에 대해서 (1)' 에서는 간단하게 숫자 조합을 고르는 방법에 대해서 알아 보았습니다. 사실 이것만 알면 그보다 좀 더 어려운 문제들 푸는 모든 준비는 끝났지만, 응용하는 방법을 알아보기로 합시다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 www.acmicpc.net 오늘 또한 완전탐색입니다. 지도가 주어졌을 때 최단거리는 보통 BFS로 구하게 됩니다. 하지만, 최대 10개가 주어지는 더러운 칸을 어떤..

https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2로 바꾸면 식이 성립한다. 9567 + 1085 ------ 10652 복면산 문제가 주어질 때, 답이 존재하는지 여부를 출력하시오. 단, 같은 문자는 같은 숫자에 대응되어야 www.acmicpc.net 오늘도 완전탐색입니다. 세 개의 문자열이 주어지면, 존재하는 각 알파벳에 0부터 9까지의 숫자를 분배해주고, 덧셈을 만족하는지 보면..

https://www.acmicpc.net/problem/17252 17252번: 삼삼한 수 첫째 줄에 2,147,483,647보다 작거나 같은 음이 아닌 정수 N이 입력된다. www.acmicpc.net 이 문제는 풀 수 있는 방법이 크게 두 가지가 있습니다. 1. 수학적 풀이 2. 완전탐색 수학적 풀이는 다음에 소개하기로 하고, 이번에는 완전탐색으로 푸는 방법을 소개하겠습니다. 아무래도 코딩 테스트에서 완전탐색이 자주 나오기 때문이죠. 약 3^21 정도면 2,147,483,647 을 넘어서게 됩니다. 그러므로 3^0부터 3^21 까지 1번 또는 0번 사용해서 만들 수 있는가를 알아내기 위한 완전탐색을 수행하면 시간복잡도는 O(2^N) 으로 최대 2^21 = 약1000000 으로 시간안에 충분히 가능합..

https://www.acmicpc.net/problem/17255 17255번: N으로 만들기 음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000) www.acmicpc.net 최대 8자리 숫자가 들어옵니다. 들어오는 숫자가 작아서 완전탐색으로 충분히 가능합니다. 시간복잡도는 O(N * 2^N) 입니다. 완전탐색은 BFS, DFS 아무거나 사용해도 됩니다. 이 코드에서는 DFS로 풀었습니다. 경로가 같은 것은 같은 경우의 수로 가정하는데, 이를 걸러내는 방법이 여러가지 있지만 각 경로를 string으로 이어 붙여서 마지막에 set 자료구조를 사용해서 걸러내면 됩니다. 예를 들어서 123이 들어온다면, 1 -> 12 -> 123 경로를 이어붙이면 112123 이 되고, 이를 set에 in..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 2019년 하반기 삼성 기출문제입니다. 이 문제에서 가장 어려운 점은 바로 '디자인'입니다. 도대체 이 윷놀이 판을 어떻게 디자인해야 하는가...? 처음 해본다면 굉장히 난해합니다. 1. 정사각 배열을 만들어 똑같이 그린다. 2. 원을 하나의 노드라고 생각하고, 그래프로 생각하여 디자인한다. 아무래도 directed graph로 생각하고 디자인하는게 훨씬 쉬워 보입니다. 다만, 파란색 노드에서 시작할 때, 다른 방향으로 가게끔 해주는 코드를 작성해주면 됩니다. 노드 갯수가 총 33개 정도(?) 되는 것 같네요. 뭐 이정도면..