기로에 서다

문제 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 풀이 1. 각 숫자에 해당하는 알파벳들을 map으로 저장해두고, s를 순회하며 찾은 숫자들을 관리합니다. 2. s를 다 돌고난 후, 찾은 숫자들에 자릿수들을 곱하여 원래 숫자를 찾을 수 있습니다. 코드 #include using namespace std; map m; void init(){ m["zero"] = 1; m["one"] = 2; m[..

문제 https://www.acmicpc.net/problem/13018 13018번: 특이한 수열 첫째 줄에 n, k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ n)가 주어진다. www.acmicpc.net 풀이 아래와 같이 몇 가지를 관찰하여 해결할 수 있습니다. 1. 1 ~ n까지의 수를 순서대로 둘 때, 1을 제외한 모든 수는 gcd(i, A[i]) > 1을 만족합니다. 따라서 주어진 조건을 만족하는 최대 k값은 n - 1이므로 n == k인 경우 불가능합니다. 2. gcd(i, A[i]) > 1을 k개의 수가 만족한다는 것은 gcd(i, A[i]) > 1을 n - k개 만족하지 않는다는 것과 같습니다. 1에서 순서대로 놓은 수들은 1을 제외하고 모두 gcd(i, A[i]) > 1을 만족하므로 편의..

문제 https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 1. 0번부터 n - 1번까지 중앙 정점을 옮겨가며 매번 거리를 계산하는게 아니라 0번 정점과 그 외 정점사이의 거리를 구한 후, 중앙 정점을 옮길 때마다 추가/감소되는 비용만 구하면 최소거리인 중앙정점을 구할 수 있습니다. 2. 정점을 옮길 때마다 추가/감소되는 비용은 정점과 연결된 간선들의 개수와 관련이 있고, 이는 dfs를 돌려 연결된 간선개수를 찾을 수 있습..

짬날 때마다 풀던게 1000문제까지 왔다 · · 블루까지 찍었으면 좋았을텐데 수직하강하는 능지의 문제로 ,, :( 열심히해서 올해안에 블루안착합시다,,

문제 programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 1. +, -하는 가중치가 같기에 모든 가중치의 합이 0이여야 결국 0으로 만들 수 있습니다. 따라서 0이 아니면 -1을 반환합니다. 2. 조금만 생각해본다면 연결된 두 점에 대해서 연산할 때, 리프부터 처리해서 루트로 올라와야 빠짐없이 0으로 만들 수 있습니다. 3. 트리임이 보장되었기에 0번노드를 루트로 잡고 dfs를 돌리는데 리프노드에선 연산..

문제 programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 풀이 s를 왼쪽으로 회전시키는건 substr을 사용하여 해결할 수 있고, 회전한 문자열 s에 대해 괄호 쌍 여부 판별은 문자열 s에 대해 스택을 사용하여 구현할 수 있습니다. 시험중에 푼 코드이기에 괄호 처리 여부가 지저분하므로 추후에 정리해서 다시올리도록 하겠습니다.. 코드 #include using namespace std; const char o[] = { '(','[','{' }; const char c[] = { ')',']','}' }; bool can(string x) { vector st; for (char op : x) { int ..

문제 programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 풀이 문제에서 설명한대로 부호가 켜져있는 경우엔 양수, 꺼져있는 경우엔 음수로 각각 리턴 값에 더해주면 해결할 수 있습니다. 코드 #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for (int i = 0 ; i < signs.si..

문제 programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 풀이 1. 시, 분, 초를 초로 변환한다면 배열을 사용해 구간의 누적 시간을 쉽게 관리할 수 있습니다. (v[i] = i ~ i +1초 누적시간) 2. logs를 순회하며 보는 재생시간의 시작 점부터 끝 점까지 일일이 체크하여 1초씩 더해준다면 시간 초과가 나기때문에 일단은 시작 점에 +1, 끝 점에..

복학하고나서 여러 가지 활동을 해보고 싶어서 지원하게된 sw마에스트로였는데 면접까지 보게되어 결과와 상관없이 좋은 경험이 될 것 같습니다 :) 1차 코딩테스트는 2시간 내에 알고리즘 6문제 + SQL 1문제 + WEB 1문제 2차 코딩테스트는 알고리즘 3문제 + SQL 1문제 + WEB 1문제가 나왔습니다. 결과는 알 수 없었지만 저의 경우 두 테스트 다 Web문제를 제외한 모든 문제들을 풀고 제출했습니다. 1차 알고리즘 문제는 단순 구현, DFS, 슬라이딩 윈도우, 간단한 분할정복, 냅색dp정도의 주제가 나왔고, 문제 자체가 어렵다기보다는 문제를 정확히 읽고 해당 주제의 내용을 구현할 수 있는지를 물어보는 문제들이 다수여서 내년 기수를 준비하는 분이시라면 자주 빈출되는 주제들을 꾸준히 푸는 연습을 하시..

문제 www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 풀이 낼 수 있는 카드를 정렬해둔 후, upperbound를 통해 낼 카드 번호를 바로 구할 수 있을 것 같지만 낸 카드는 버리기에 사용한 카드의 유무를 저장하는 배열을 사용해 항상 사용하지 않은 카드를 내는 식으로 해결할 수 있습니다. $O((m + k)logm)$ 코드 #include using namespace std; int n, m, k, x,..