데이터 엔지니어

문제링크: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 삼성 기출로 나왔던 문제입니다. 삼성 기출은 조건 확인을 확실히 해주셔야 합니다. 문제 설명 - N: 맵의 크기 - 아기 상어 초기 크기 = 2 / 크기 만큼 물고기를 먹어야 => 크기 + 1 / 상어 위치 = 9 - 지나갈 수 있는 경우: 아기 상어 크기 >= 물고기 크기 - 먹을 수 있는 경우: 아기 상어 크기 > 물고기 크기 - 먹을 수 있는 경우가 여러가지인 경우 1...

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제 설명 - 가로 세로가 n인 크기의 체스판에 n개의 queen을 놓을 수 있는 경우의 수 - queen은 가로 세로 대각선 이동이 가능 - n = 4 인경우 아래 이미지 처럼 2가지 경우의 수가 나옵니다. 풀이 - DFS / 백트래깅 (백트래킹은 지난 https://data-engineer.tistory.com/19에서 설명한 것 처..

문제링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 삼성 기출로 나왔던 문제입니다. 문제 설명 - N, M: 맵의 높이, 넓이 - 테트로미노: 정사각형 4개를 이어붙인 모양 - 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대 - 테트로미노들은 회전 대칭 가능 풀이 이 문제 같은 경우는 도형이 5개에다가 회전을 해도 총 경우의 수가 15가지 ex) ㅜ ㅏ ㅗ ㅓ (4가지) 가 나옵다. 각 지점마다 해당..

문제링크: https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 문제 설명 - n: 동전의 가짓수, k: 만들고자 하는 수 - k를 만들기 위한 동전의 최소 개수 (중복 가능) - ex) n = 3 [1, 5, 12] , k =15 일 때, 15를 만드는 동전의 최소 개수는 4개(12, 1, 1, 1)가 아닌 3개(5, 5, 5)입나다. 풀이 - Dynamic Programming(동적 계획법)을 활용해야 한다. -..

문제링크: https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 문제 설명 - 맵이 주어졌을 때 최단 경로로 도착지점까지 갈 수 있는 비용 구하기 - 벽(0) 길(1) 로 주어짐 - 못가는 경우 -1 리턴 - ex) 풀이 - BFS - queue에 (x, y, cost) 형식으로 들어감 - 방문관리를 cost와 함께 진행해 주어야 함 ex) (0, 2): 5 =..

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 문제 설명 - 팰린드롬 = 앞뒤를 뒤집어도 똑같은 문자열 - 문자열 s가 주어졌을 때 가장 긴 팰린드롬을 출력 - ex) abcdcba 7 4번째 'd' 기준 abacde 3 2번째 'b' 기준 풀이 전부다 검사하면 되는 문제입니다. 효율성을 통과하지 못해 좋은 코드를 찾아 수정하여 제출하였습니다...

문제링크:https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네의 체와 투 포인터를 활용해야 하는 문제입니다. 단순하게 소수를 구했다가 시간초과의 늪에서 헤어나오질 못하고 투포인터의 while문 통과 조건도 잘못 걸어 애를 먹었던 문제입니다. 문제 설명 - 하나의 수가 주어지고 소수의 연속합으로 하나의 수가 만들어 지는 경우의 수를 구하는 문제입니다. - 예시 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 풀이 1. 에라토스테네스 체 일단 소수리스트를 먼..

문제링크: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분탐색의 기본문제입니다. 이분탐색 같은 경우는 조건을 세우는 것이 중요합니다. 1. 이분탐색으로 구하고자 하는 수 2. 이분 탐색의 기준(left right를 움직이는 기준) 문제 설명 - K: 기존에 가지고 있는 랜선의 개수 - N: 필요한 랜선의 개수 - K개의 선이 주어지는데 N개를 만족하며 최대로 구할 수 있는 선의 길이를 구하는 문제입니다. - 이..