조용하지않는개발Blog

코딩 테스트 문제를 유출하는 것은 절대 해서는 안되는 일이기에 문제 유형과 어떤 식 이였는지만 작성하여 나중에 어떻게 풀었는지, 어떤 유형이 많이 나오는지 알기 위해서 작성하였습니다. 또한 이정도의 유형도 문제가 된다면 삭제 하겠습니다. 총 3문제가 나왔습니다. 문제 자체는 어렵지 않았습니다. KT 에이블 자체가 교육을 듣고 성장할 사람을 찾기 때문에 어렵게 내기 않은듯합니다. 1. 기본 구현 문제 -> 시간 마다 변화는 비밀번호를 x초 일때 현 비밀번호는? 이걸 구현해야하는 문제 -> 레벨 1 2. BFS, DFS 문제 -> 회사와 집의 거리에 따른 버스비 최소 비용 문제 추가적으로 계산이 필요한 부분도 있지만 유형만 알려드리기 위해서 넘어가겠습니다. -> 레벨 2 3. 그래프 구현 문제 -> 브로트포..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보고 조합 문제겠구나 생각했다. 하지만 조합을 정확히 모르면 풀수없는 문제이기에.. 수학공부를 해야겠다. 싶었다. 각 종류 별 옷이 기에 n+1C1 의 조합으로 곱해주면 된다. 예시를 통해 보면 headgear:hat, turban eyewear: sungl..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 모든 노드의 최단 거리를 알아내는 문제이다. 이문제는 플로이드 워셜 알고리즘을 이용하면 쉽게 풀 수 있었다. 그래서 문제이름도 플로이드? 하지만 플로이드 워셜을 몰라도 풀수는 있겠지만 알고있으면 좀더 쉽게 풀 수 있을것으로 생각이 든다. 이것도 알고리즘에 작성할 필요가 있다. import sys input = sys.stdin.readline n = int..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 스택을 이용하여 풀수있는 단순한 문제였다. 다만 구현하면서 어떻게 구현을 해야하는지 생각을 많이 해야해서 골드 5이지 않을까 생각이 든다. import sys input= sys.stdin.readline n = int(input()) n_list = list(map(int,input().split())) stack=[] result = [0]*n for..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 통해서 겹치는 구간을 없애기만 하면 되는 문제이다. 다시 말해서 최장 증가 부분 수열(LIS)로 문제를 풀면 된다. 다음에 관련해서 알고리즘을 작성해놓아야 좋을듯하다. 두가지 방식으로 풀었는데 dp와 이분탐색으로 문제를 해결하였다. import sys input = sys.stdin.readline n = int(input()) n_list = [] for..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체가 짧지만 단순하게 풀면 어렵고 다이나믹 프로그래밍으로 풀면 그나마 쉽게 풀 수 있는 문제이다. 처음에 풀 때, 반복문, 재귀를 이용해야하나 고민했는데 그러면 너무 많은 시간이 걸릴 것 같아서 포기했다. 그래서 dp로 10001이 담긴 리스트를 생성하고 가치가 낮은 동전을 넣고 그다음으로 가치 높은 동전을 넣어가면서 ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제 자체는 어렵지 않은 문제였습니다. 처음에 보고 그래프로 푸는 문제인가?! 하고 생각했는데 보니까 최소값인 치킨집을 선택하고 집에서 거리를 계산하여 최소가 되는 길이를 찾는 형식의 문제였습니다. 또한 n,m의 최대가 50, 13 이여서 반복이 조금 들어가도 시간 초과는 안나겠다는 생각을 가지고 편하게 풀었습니다. 먼저 그래프에서 치킨집과..

https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 문제 설명 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직..

코딩 테스트 문제를 유출하는 것은 절대 해서는 안되는 일이기에 문제 유형과 어떤 식 이였는지만 작성하여 나중에 어떻게 풀었는지, 어떤 유형이 많이 나오는지 알기 위해서 작성하였습니다. 또한 이정도의 유형도 문제가 된다면 삭제 하겠습니다. 총 4문제 3시간동안 푸는 문제였다. 난이도 기준은 프로그래머스입니다. 1. 정렬문제 -> 버블정렬 구현 -> 레벨 1 2. 구현 -> 단순 구현 -> 레벨1 (다만 조건을 잘 봐야했던걸로 기억함 - 함정이 있다! 조심해라!) 3. 이분탐색 문제 -> 나중에 풀었던 사람들과 이야기 했을때 이분탐색 문제 같다고함. 나는 정렬후 반복으로 풀어서 아마 테스트케이스에서 시간초과가 나왔을것이다. -> 레벨 3 4. 최소 이동 문제 -> dfs, 백트레킹로 풀었음. 다른 분들 이야..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어 수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의..