목록분류 전체보기 (122)
tony9402
코딩테스트 준비할 겸 실력 유지 및 각 코딩테스트들의 트렌드를 경험하고자 시간이 된다면 신청을 하는 편이다. 그 전에는 그냥 참가할 생각을 못했는데 이번부터 신청을 하고 경험하고 있다. 2021 카카오 블라인드 1차는 총 7문제가 출제되었다. 1차를 보기 전에 1차에서 4솔 정도 하면 1차는 통과된다는 말을 들어서 1 ~ 4번을 빨리 풀고 쉴 계획을 세우고 시험을 보았다. 문제는 나중에 공개되므로 나중에 풀이 설명을 보완하겠다. 1번 : 100점 알고리즘 : Case work, 문자열 문제 조건에 따라 하나씩 문자열을 처리하면 된다. 난이도는 쉬운 편이지만 C++로 하나씩 구현하기 귀찮긴 했다. 하지만 단계별로 하나씩 구현하면 쉽게 맞을 수 있다. 2번 : 100점 알고리즘 : DFS, 백트래킹 문자열에..
2차 대회는 9월 5일 14:00 ~ 17:00에 진행되었다. 1차땐 워낙 문제가 쉬워 이번엔 좀 어려워지긴 하겠지 예측을 했지만 예측한 것보다 훨씬 어려운 문제들이 출제되었다. 1차 후기를 쓴 것과 마찬가지로 각 문제를 어떤식으로 풀었는지, 어떤 알고리즘으로 풀었는지에 대해서만 언급하겠다. 1번 : 100점 알고리즘 : 완전탐색 처음엔 지문이 너무 안 읽혔다. 계속 읽어봐도 안읽혀서 내가 생각한대로 짜봤더니 WA가 나왔다. 좀 더 고민을 하고 있다가 1번 문제에 관해 공지가 올라왔는데 그 이후로 파악을 해서 풀었다. 제대로 이해했을 때 떠올린 풀이는 바로 완탐이였다. (모든 경우를 완탐을 하면 TLE, 하지만 문제 조건에 맞춰서 특수(?) 상황에 대해 완탐은 AC) 2번 : 100점 내가 사용한 알고리..
8월 29일 (토) 14시 ~ 17시 동안 브랜디 코딩대회 1차가 진행되었다. 알고리즘을 못하지만 그래도 알고리즘 푸는 폼을 최소한 유지하고 싶어 시간만 맞다면 최대한 신청하여 보는 편이다. 이번에 브랜디 코딩대회와 카카오 코딩테스트를 신청하여 봤다. 브랜디 코딩대회에 대해 간단히 후기를 남기겠다. 문제 지문에 대한 얘기는 하기 조심스럽고 난 어떤 알고리즘으로 풀었는지 정도만 얘기하겠다. 1번 : 100점 입력 받을 개수를 안알려줬을때 입력을 받을 수 있는지에 대한 문제인거 같았다. 문제 자체는 매우 단순했다. 알고리즘은 몰라도 if문을 사용할 수 있다면 충분히 풀 수 있는 문제이다. 2번 : 100점 전형적인 완탐 + BFS 문제. 이 문제를 풀면서 생각났던 문제들은 (연구소, 불, 불!, 탈출 등 B..
[문제] 백준 3025 돌 던지기 [알고리즘] 시뮬레이션 [시간복잡도] $ O(N + R) $ [솔루션] 일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다. 이를 어떻게 줄일지 아이디어를 생각해봐야한다. 아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다. 결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다. 아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다. 이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과. 아이디어 3 그렇다면 어떻게 짜야할까? 바로,..
저번 셋을 통해 4문제 2시간이 은근 짧다고 느껴져서 2문제를 추가하여 돌렸다. 총평은 역시 그리디가 많고 언제나 어렵다... [문제] Codeforces 1384 A [문제 유형] Greedy, Constructive algorithms [시간복잡도] $O(n)$ [풀이] 문자열 $S_{i}$와 $S_{i+1}$의 가장 긴 공통 접두사의 길이가 n개 주어진다. 이를 가지고 조건에 만족하는 문자열을 출력하면 된다. [소스코드] #include #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const ll MOD = 1e9 + 7; char nex..
백준에서 알고리즘 풀다가 최근에 다시 코드포스를 참가하면서 느낀점은 CP 실력이 더더욱 나빠졌다는 것이다. 따라서 실력을 상승시키기 위해 난이도를 정해놓고 빠른 시간에 풀 수 있도록 연습을 하려 한다. 처음은 간단하게 난이도 1000 ~ 1400 정도의 문제를 2시간 제한시간을 주고 풀기 시작하고 점차 너무 쉽거나 난이도를 올려도 될때는 문제 수를 늘리거나 난이도를 상향하여 계속 진행할 것 같다. [문제] Codeforces 1385 C [문제 유형] Greedy [시간복잡도] $O(n)$ [풀이] 배열 A에서 A의 접미사 ( $1 \le i \le n, ; [ a_{i} , a_{i+1} , ... , a_{n}]$ ) 중 $a_{i} \le a_{i+1} ... a_{i+k} \ge a_{i+k+1}..
제 11기 소프트웨어 마에스트로의 전형은 아래와 같았다. 원서 접수 -> 1차 코딩테스트 -> 2차 코딩테스트( + 인적성 검사) -> 심층 면접 코딩테스트는 1차, 2차 모두 알고리즘 3문제, SQL(데이터베이스) 1문제, Web 1문제가 나왔다. 1차 코딩테스트 알고리즘 1번 : 7-segment (codeforces.com/problemset/problem/1295/A) 알고리즘 2번 : 색종이 관련 문제 알고리즘 3번 : 구간 나누기 SQL : 학생들의 성적 평균 비슷한 문제.. 웹 : To Do List 2차 코딩테스트 알고리즘 1번 : 연속합 구하기 (boj.kr/1912) 알고리즘 2번 : union-find or bfs/dfs (boj.kr/10216) 알고리즘 3번 : 스위핑 SQL : ..
문제링크 : 바로가기 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 큐브를 한 번만 돌려서 모든 면을 맞출 수 있는지 확인하는 문제이다. 배열 돌리는 연산을 구현하는 것이 살짝 까다롭다. 큐브는 3차원이기 때문에 돌리는 방향은 3가지로 표현 할 수 있다. 전개도를 고정하고 돌릴 수 있는 방향을 써보면 위, 아래( == 위 x3 == -위), 왼쪽, 오른쪽( == 왼쪽 x3 == -왼쪽), 시계방향, 반시계방향(== 시계방향 x3 == -시계방향)이다. 1. 위쪽 방향 2. 왼쪽 방향 3. 반시계 방향 1번에서 ..
1. Triangles (Bronze) 점들을 이용해서 만들 수 있는 모든 직각삼각형 중 넓이가 가장 큰 값을 구하면 된다. #include #define all(x) (x).begin(),(x).end() #define mp make_pair using namespace std; typedef pair pii; vector vc; int cross(int i, int j){ return vc[i].second * vc[j].first - vc[i].first * vc[j].second; } bool check(int i, int j, int k){ pii v1 = mp(vc[i].first - vc[j].first, vc[i].second - vc[j].second); pii v2 = mp(vc[k]...
오랜만에 코드포스를 했다. 6솔 할 수 있었는데 생각하지도 못한 부분 때문에 TLE가 떠서 5솔 밖에 하지 못했다... A. Candies and Two Sisters Problem - A - Codeforces codeforces.com a > 0, b > 0이고 a > b를 만족하는 a + b = n의 개수를 찾는 문제이다. n > 2 일때 b는 1부터 (n - 1) / 2까지 가능하고 n = 1일땐 (n - 1) / 2로 계산 가능하므로 그냥 n을 받으면 (n-1)/2를 출력하는 소스를 짜면 된다. B. Construct the String Problem - B - Codeforces codeforces.com 각 케이스 마다 n, a, b가 주어지는데 n은 문자열의 길이, a는 부분 문자열의 길이..