택시짱의 개발 노트

2020 상반기 이스트소프트 코딩 테스트를 오늘 봤다. 오늘은 총 3시간에 4문제 나왔는데 난이도는 많이 어렵게 나오지는 않았던 거 같다 첫 번째 두 번째 문제는 map을 이용하면 되는 문제 세 번째 문제는 완전탐색을 하면 되는 문제 네 번째 문제는 토큰분할을 이용해서 푸는 문제였다. 테케랑 이런저런 반례를 해보고 제출했는데 실수했으면 어쩌나 해서 약간 걱정 이긴 하다

링크 https://programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하는 문제이다. 쿼리에서 주어지는 단어와 가사를 비교해야 되는데 일일이 모두 탐색하게 되면 시간 초과가 나는 문제이다. 그래서 이 문제를 풀기 위해서는 트라이를 이용해야 되는데. 트라이를 만들기 전에 생각을 해봐야 하는 것이 가사와 단어의 길이에 대한 생각이다. 문제에서는 단어와 가사의 길이가 일치해야 하는 조건이 있는데 모든 가사를..

링크 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 풀이 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제이다. 일단 제목에서 플로..

링크 https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 www.acmicpc.net 풀이 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 개수를 구하는 문제이다...

링크 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 문제 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드 www.acmicpc.net 풀이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제이다. 입력받은 각 단어들을 트라이를 이용하여 트리를..

링크 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 풀이 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제이다. 일단 비트 마스크를 이용하여 수열 S의 모든 부분 수열의 합을 구하고 map에 추가하고 모든 부분 수열을 구하고 나서 1부터 최대로 나올 수 있는 20..

링크 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. www.acmicpc.net 풀이 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제이다. 간단하게 집합 S를 map에 추가 하고나서 M개의 문자열을 map과 매핑하여 포함 여부를 확인하면 된다. 1. map..

링크 https://programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 구하는 문제이다. BFS탐색을 이용하여 최소 값을 구하도록 하였고 이전 문자와 다음 문자를 서로 비교하여 다른 부분이 한 개만 있을 때 BFS의 queue에 추가되도록 하여 target 문자열을 만나게 되면 바로 return을 하도록 하..