소프트웨어 마에스트로 14기를 지원했다. 이전기수 선배님들에게 여러 조언을 얻으며 자소서를 작성하고, 지원하게 되었다. 코딩테스트 이번 기수부터는 WEB 문제를 제외한 알고리즘 4문제, SQL 1문제가 출제되었다. 소마의 코테는 구현이 많고 생각보다 어렵지 않다는 평이 많았다. 따라서 구글링을 통해 이전 유형을 찾아보고 복습하는 방식으로 코딩테스트를 준비했다. 1차 유형 정말 간단한 구현 문제였다. 천천히 지문에 맞게 구현만 해주면 되었다. 선분이 주어지고, 교점을 활용한 문제였다. 시험에서는 시간 부족으로 인해 풀지 못했다. 복기하면서 풀이를 고민했는데, 주어진 크기가 작기 때문에 완전 탐색을 통해 충분히 해결할 수 있었다. 아래 문제와 느낌이 비슷하다. 좌표를 2배로 늘려 저장하는 것이 핵심 포인트이..
대회 주소 https://codeforces.com/contest/1800 Dashboard - Codeforces Round #855 (Div. 3) - Codeforces codeforces.com 문제 풀이 A번 문자열 전부 대문자 or 소문자로 변환 중복되지 않도록 새로운 문자열 만들기 MEOW와 일치하는지 확인 B번 대문자, 소문자를 나누어 갯수 세기 조건에 일치하는 만큼 더하기 남는 알파벳이 2개 이상이라면 k가 있는 만큼 더해주기 C번 보너스 카드일때 heapq에 삽입 (최대힙) 영웅카드일 경우에 heappop 후 점수 더하기 D번 문자열에 길이 - 1을 answer로 지정 문자열을 3개씩 골라서 팰린드롬이라면 answer -= 1 EFG 실패.. 결과 떡잎방법대 첫 출격
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 문제 풀이 먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다. 임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다. 하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다. 이러한 트리의 지름을 구하는 문제는 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 확산과 공기청정기를 순서대로 작동하면 된다. 확산은 미세먼지가 존재하는 위치에 상하좌우로 5를 나눈 소수점을 제거한 값만큼 확산된다. 이때 확산할 공간이 없거나 확산 위치에 공기청정기가 존재한다면 확산할 수 없다. 확산이 되는 만큼 감소된다. (확산에서 미세먼지는 항상 보존된다.) 미세먼지의 양이 5미만이라면 확산되지 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석 문제 풀이 입력 범위가 1000 이기 때문에, lis 알고리즘이 아니라 2차원 dp를 사용해 가장 긴 증가하는 수열을 앞에서, 뒤집어서 두 번 구해주었다. 뒤집어서 구해준 값들을 다시 뒤집어 순서를 맞춰주고, 두 dp값들의 합이 최대가 되도록 하는 값 + 1이 답이 된다. 문제 코드 def solve(n, arr): # 앞에서 부터 가장 긴..
