기둥과 보 설치 문제 설명 구현 문제이다. 머릿속으로 구현은 나름 빠르게 됐는데 코드로 옮기면서 조건을 한 두개씩 빼먹어서 시간이 오래걸렸다. 시험이 아닌데도 3시간씩 걸려서 푸는데.. 언제 이런문제를 1시간 안에 풀 수 있을까... 기둥과 보가 설치될 수 있는 조건을 명확하게 해결하여야한다. 설치할 때는 해당 위치에 기둥과 보가 설치될 수 있는지 확인하고, 삭제할 때는 삭제를 시킨 후 모든 구역에 대해 기둥과 보가 설치 할 수 있는지 없는지 확인한다. 문제 풀이 소스코드 : C++ 해당 좌표에 기둥과 보가 설치 되어있는지 확인하는 구조체 POS Map[101][101]을 선언한다. 우선 해당 좌표에 기둥과 보를 설치할 수 있는지 확인하는 두 함수 chk_pillar와 chk_beam을 구현한다. chk..

124 나라의 숫자 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 문제 설명 10진법을 3진법으로 바꾸는 방식으로 풀면된다. 3진법에는 0,1,2가 쓰인다면 이 문제는 1,2,4가 쓰이도록 문제를 해결한다. 문제 풀이 소스코드 : C++ 재귀를 이용한 풀이 #include #include #include using namespace std; char num[3] = {'1','2','4'}; string solution(int n) { if(!n--)return ""; ..

스킬트리 코딩테스트 연습 - 스킬트리 programmers.co.kr 문제 설명 정해진 스킬 순서를 올바르게 배웠는지 체크하는 문제. 스킬을 의미하는 알파벳 사용 여부와 skill의 순서로 skill_trees들을 체크한다. 문제 풀이 소스코드 : C++ skill에 있는 스킬들을 true표시 해둔다. skill_trees에 담긴 스킬들을 탐색한다. 해당 스킬이 skill에 포함 된 문자라라면 순서가 맞는지 체크한다. 순서를 의미하는 index, skill[index] == s[j]이면 다음 스킬을 체크한다. 그렇지 않으면 순서가 맞지 않으므로 break 위과정을 반복하여 스킬의 모든 길이를 탐색했으면 예외가 없으므로 answer++해준다. 위 과정을 반복한다. #include #include #incl..

다리를 지나는 트럭 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 설명 다리를 queue라고 생각하고 조건을 적절히 이용하여 푸는 문제다. 어렵지는 않지만 생각해야할 조건이 많아서 좀 까다로웠다. 자세한 풀이는 c++코드에 주석처리 해놓았다. 파이썬 코드도 로직자체는 같지만 for문에서 인덱스값을 마음대로 조절할 수 없어서 while문을 이용하였다. 문제 풀이 소스코드 : C++ #include #include #include #include #define PII pair using..

프린터 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 문제 설명 양방향 queue 즉, deque를 이용하여 우선순위에 맞지 않은 작업들은 다시 대기열로 push_back하여 요청한 문서가 몇번째인지 찾아낸다. cpp은 작업들을 내림차순 정렬하여 최대값을 갱샌했고 python은 max함수를 이용하여 매 탐색마다 최대값을 갱신해줬다. 문제 풀이 소스코드 : C++ #include #include #include #include using namespace std; int solution(vector pri, ..

쇠막대기 코딩테스트 연습 - 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레� programmers.co.kr 문제 설명 (는 스택에 쌓아주고 )일때마다 top에 있는 (를 pop하고 스택의 사이즈를 answer에 더해준다. 문제 풀이 소스코드 : C++ #include #include using namespace std; int solution(string arrangement) { int answer = 0; vector v; // stack for(int i=0; i

멀쩡한 사각형 문제 설명 처음에 문제를 접했을 때, 아무리 생각해도 로직이 떠오르지 않았다. 그래서 조금 수학적으로 생각을 바꿔보았다. 대각선을 그릴 때에도 가로의 길이와 세로의 길이와 관련이 있다. 중복되는지점이 4개라는 것을 알 수 있다. 결국 이 대각선을 지나는 사각형의 개수를 구하기 위해서는 중복되는 지점의 개수를 찾아 빼주면된다. 이 경우에 중복되는 지점은 1개이다. 빨간 부분에서 중복되는 점이 발생한다. 결국 이 중복되는 점은 두 수(2,3)의 최대공약수이며 위 모양의 반복되므로 그 개수 *4를 해주면 중복되는 지점의 개수를 구할 수 있다. 결국에는 8과 12의 최대공약수가된다. 따라서 이 문제를 식으로 해결하면 answer = w*h(전체 사각형의 개수) - (w + h - gcd(w,h)가..

뉴스 클러스터링 문제 설명 주어지는 문자열을 2글자씩 잘라 다중 집합을 만들고 두 문자열의 다중집합의 합집합의 개수와 교집합의 개수를 구하는 문제다. 문제 풀이 소스코드 : C++ 문자열을 2글자씩 잘라주는 함수 makeArr 두 글자 중 하나라도 알파벳이 아니면 continue 두 글자 모두 소문자로 변환하고 sv에 담는다. 위 과정 반복 후 반환 변환한 두 벡터 모두 비어있다면 65536을 반환하고 종료 sv에 sv2를 복제한다. 만약 sv에 sv1 값을 찾을 수 있다면 -> 교집합, answer++ answer는 교집합의 개수이고 sv1 + sv2 - answer는 합집합의 개수이다. 교집합 / 합집합 * 65536을 반환한다. #include #include #include #include #in..