기로에 서다

문제 https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 풀이 1. 우선 해야 하는 걸 간단하게 정리하자면 아래와 같습니다. 1. 게임 보드의 서로 인접한 빈 공간 좌표 집합들을 구합니다. 2...

문제 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 당시에 풀 때도 링크드리스트로 풀다가 삽질하고 set으로 방향을 틀었던 기억이 나는데 문제를 꼼꼼히 안읽으면 우왕좌왕 해매기 쉬운문제였던 것 같습니다. 다시 링크드리스트로 구현해봐야지,, 1. 주의 깊게 봐야하는 부분은 아래와 같습니다. ※ "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정..

문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 1. 5개의 대기실마다 검사를 해야하므로 하나의 대기실에 대해 검사하는 함수를 ..

문제 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를 돌려 연결된 간선개수를 찾을 수 있습..

문제 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, 끝 점에..