SCPC는 삼성전자에서 주관하는 대학생 프로그래밍 경진대회다. 살펴보니 참가비도 없고 예선 참가시간도 24시간이나 줘서 괜찮은 것 같다고 생각해 참여하게 되었다. 알고리즘 문제를 많이 풀지도 않았고 대회에 나가본 적도 없지만, 아는 형이 대회에 참여한다는 말을 듣고 까짓거 해보자는 마음으로 신청을 하게 되었다. 후기 구글에 SCPC 난이도를 쳐보면 1차는 실골골플플 정도라는 글이 나온다. 실버 문제는 꽤 풀어봤지만 골드 문제는 8문제 정도 밖에 안 풀어 봤기에 일단 한 문제를 풀고 나머지 두 문제를 풀어보고, 남은 두 문제는 쳐다보지 않기로 결심했었다. 위에 말 그대로 되었다. 1번 문제는 어찌저찌 풀었다. 사실 1번도 쉽진 않아서 꽤 푸는 데 시간이 걸렸다. 2번 문제는 아이디어가 어렴풋이 떠오르기는 ..
생각 앞선 N과 M 문제처럼 백트래킹을 사용하면 된다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 출처 : https://chanhuiseok.github.io/posts/algo-23/ 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 이번에 살펴볼 개념은 백트래킹에 관한 내용입니다. chanhuiseok.github.io 만약 백트래킹에 대해서 더 자세히 배우고 싶다면 바킹독님의 강의를 듣는 것을 추천한다. 바킹독 백트래킹 강의 다른 점은 같은 수를 여러 번 골라도 된다는 점이다. 그렇다면 수가 사용되었는 지 검사하는 부분은 빼도 된다. 그리고 예제 ..
생각 재귀를 사용하면 될 것 같다. 1. 사각형을 4분면으로 나눠서 거기서부터 루프를 돌면서 0인지 1인지 확인한다. 2. bool 변수를 두개 만든다. 하나는 루프를 돌 때 한 번이라도 1이 나오면 false(흰색 사각형이 아니라는 뜻), 또 하나는 루프를 돌 때 한 번이라도 0이 아니면 false(파란색 사각형이 아니라는 뜻.)이다. 3. 그리고 재귀를 사용해서 흰색 혹은 파란색 사각형을 찾을 때까지 계속 탐색한다. 4. 두 bool 변수 중 하나라도 true가 나오면 사각형을 찾은 것이므로 재귀를 그만둔다. 5. 파란색 사각형이면 파란색 사각형의 개수를 나타내는 변수에 1을 더하고, 흰색 사각형이면 흰색 사각형의 개수를 나타내는 변수에 1을 더한다. 6. 모든 과정이 다 끝나면 하얀색 색종이의 개수..
생각 BFS를 사용하여 푸는 문제이다. 일단 나이트는 한 칸을 이동한 후 바라보는 방향의 대각선으로 이동할 수 있다. 따라서 이동은 X = { 1 2 2 1 -1 -2 -2 -1} Y = { 2 1 -1 -2 -2 -1 1 2} 이렇게 설정할 수 있다. (오른쪽으로 갈수록 x가 커지고, 아래쪽으로 갈수록 y가 커진다고 가정했다.) dist 배열을 만들어서 지금 내가 몇번 이동했는지 배열에 입력해야겠다. 코드 #include using namespace std; int board[305][305]; int dist[305][305]; // 해당 칸을 방문했는지 여부를 저장 #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int..
생각 일단 이항 계수가 무슨 뜻인지 몰라서 검색을 해봤다. 이항 계수는 nCk 였구나. 고등학교 확통 시간 때 배운 적이 있다. 문제 조건에서 0 > k; int ans = factorial(n) / ( factorial(k) * factorial(n - k) ); cout
Jclef - 으악! 듣기 고등학생 때 나는 사운드클라우드(이하 사클) 앱으로 음악을 듣곤 했었다. 사클을 둘러보다 보면 평소에는 들어보지 못했던 좋은 곡들이 있어서 좋았다. 이 노래는 가사가 좋다. 이 노래도 사클의 알고리즘의 파도를 타다가 우연히 발견했다. 처음에 이 노래를 들었을 때 제목이 '으악!'이라는 것에 놀랐고, 제이클레프의 음색이 너무 좋아서 놀랐고, 또 가사가 좋아서 놀랐다. 우울에 관해 직접적으로 다루면서도 상대방을 존중하는 가사가 마음에 들었다. 노래를 시작하면 나오는 '우울을 숨기지 않아도 되는 세상이지', 그리고 중간에 나오는 '함부로 너의 상처의 깊이를 가늠한다 말하지 않을게' 이런 가사들을 처음 들었을 때 '이런 노래도 있네'하며 신기해했던 기억이 난다. 그 때까지 들었던 힙합..
생각 맨 처음 든 생각: 벡터로 입력받아서 오름차순으로 정렬한 다음, M/3과 가장 가까운 수를 찾아서 그 수와 양 옆에 있는 수를 더한 값을 구하면 될 것 같다. -> 정렬했을 때 붙어있는 세 값의 합만이 정답이 아니다. 반례가 있으므로 틀렸다. 두번째 든 생각: 벡터로 입력받아서 오름차순으로 정렬한 다음, (*it) + *(it+1) + *(it+2)가 m보다 클 때를 찾아서 그 때 *(it-1) + *it + *(it+1)을 구하면 될 것 같다. -> 아까 위에 말했던 것처럼 정렬했을 때 붙어있는 세 값만이 정답이 아니다. 역시 틀렸다. 붙어있는 값들의 합만이 정답이 아니다. 그러면 어떻게 해야될까? -> 삼중루프를 돌려서 m과 가장 가깝지만 m보다 작은 값을 찾는다. 여기서 주의해야 할 점은 삼중..
생각 이 문제에서 해결해야 될 문제는 크게 두 가지다. 1. [숫자,숫자,숫자...]를 입력받고 어떻게 숫자만 쏙 빼서 덱에 넣을까? 2. 뒤집는 것과 지우는 것을 어떻게 구현하면 될까? 처음에는 1번 문제를 어떻게 풀었냐면, 1. string으로 배열을 입력받는다. 2. '[', ',' ']'가 아니면 숫자로 바꿔서 덱에 push한다. 하지만 이렇게 하면 문제가 있다. 만약 두 자리 수의 숫자가 들어왔을 경우에도 숫자를 따로따로 인식하게 되기 때문이다. 그래서 어떻게 풀었냐면, 1. string으로 배열을 입력받는다. 2. ',', ']'가 아니면 또 다른 string 변수에 더해준다. 3. 만약 ',' 나 ']'이 나오면 string 변수를 stoi로 int로 바꿔주고 덱에 push한다. 4. str..
어떻게 풀까? (문제를 처음 보고 든 생각) 스택을 사용하자. for문을 써서 현재 for문이 가리키는 알파벳이 스택의 top에 있는 알파벳과 같다면 pop을 하자. for문 loop가 다 끝나고 스택이 비어있으면 좋은 단어고, 아니면 좋은 단어가 아니다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; // 단어 수 int cnt = 0; // 좋은 단어 개수 cin >> n; while (n--) { stack s; string a; cin >> a; for (int i = 0; i < a.length(); i++) { if (s.empty()) { // 스택이 비어있다면 s.push(a[..
어떻게 풀까? (문제를 보고 처음 든 생각) 큐를 사용해서 풀면 될 것 같다. 먼저 큐의 front를 한 번 pop하고, 그리고 임시 변수에 갱신된 큐의 front를 저장하고, 큐의 front를 다시 pop한다. 그리고 임시 변수를 큐에 push한다.(위에 있던 수를 밑으로 옮기는 효과) 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); queue q; int n; int temp = 0; cin >> n; for (int i = 1; i n; for (int i = 1; i
