SiO2whocodes

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 다이나믹 프로그래밍 C++ 접근방법 이것도 그냥 피보나치다. 근데 입력이 1,000,000까지고 출력은 모든 이진수 개수%15746이다. 그래서 그냥 피보나치 처럼 풀어서 나눈 나머지를 출력하면 절대 값이 안나온다. 다행히 나머지를 구하는 것이라는 거 나머지를 구해야 하는거면 굳이 결과 값을 다 더하면서 갈 필요가 없다. 결과 값에서 15746로 나누어 떨어지는 만큼은 필요 없기 때문에 1부터 N까..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 동적계획법 C++ 접근방법 피보나치 수열은 재귀로 푸는 것 보다 동적계획법으로 배열을 사용해서 푸는게 시간복잡도가 훨씬 낮다. 이는 재귀로 계산하면 계속 같은 계산을 반복해야하지만 배열에 값을 저장해두면 다음번엔 계산하지 않아도 되기 때문이다. 근데 이 문제는 이런 논리를 사용하긴하는데 수학적으로는 피보나치와 약간 연결성이 떨어져 보였다. 뭔가 푸는 방법만 같은 느낌 실제로 코드는 피보나치수열을 동적계획법으로 풀이한 것과 로직은 동일하다. 어렵게 생각하지 말고 그냥 트리나 표를 그려서 접근하는..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 수학3 c++ 접근방법 애초에 팩토리얼 구하는 수의 범위가 500까지라(시간제한2초) 팩토리얼을 계산해서 푸는 문제는 아니었다. 가장 작은 자리 수 부터 연속되는 0의 개수를 출력하는 문제라 N부터 0까지 연속되는 수가 모두 곱해서 팩토리얼 결과가 나오는 거니까 0의 개수는 5*2의 개수이다. 근데 연속되는 수니까 2의 개수가 5의 개수의 비해 많을게 분명하다. 따라서 2의 개수는 세지 않고 5의 개수만 센다. 이때 주의할 점은 25, 125같이 2개 이상의 5로 구성된(?)수가 있..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 수학3 C++ 접근 방법 정수 N을 2부터 나눠가는데 이를 나눠서 0이면 계속 같은 수로 나누면서 출력하면 오름차순으로 소인수분해 결과를 출력할 수 있다. 가장 작은 소수부터 시작해서 그 수로 더이상 나눠지지 않으면 나누는 수를 1 증가시켜 나눠보는 과정을 반복하고 N이 1이하가 되면 반복문을 나온다. 소스코드 #include using namespace std; int main(){ int N; cin >> N; int d = 2; while(N > 1){ while(N%d == 0){ cout

https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 수학3 C++ 분명 실버라고 알고 있는데 생각보다 쉬웠다. 근데 정렬하지 않으면 틀려서 sort함수로 급하게 정렬해서 했더니 맞았다. 첫째줄에 모든 약수의 개수가 주어지고, 둘째줄에 모든 약수가 주어지면 N을 구하는 문젠데 그럼 정렬해서 최솟값과 최댓값을 곱하면 N이 나오는 간단한 문제였다. 소스코드 #include #include using namespace std; int main()..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백트래킹 C++ 삼성 SW 역량 테스트 기출 문제 1 문제 순서가 정해진 피연산자들이 주어지고 +,-,x,÷ 의 개수가 입력된다. 그럼 연산자들의 순서를 바꿔가며 계산한 값의 최댓값과 최솟값을 출력하는 문제이다. 접근방법 순서가 다르게 연산자들을 나열한다. N과 M(1)의 코드를 재사용했다. 그 결과 연산자들의 순서가 다른 모든 경우의 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백트래킹 C++ 삼성 SW 역량 테스트 기출 문제 2 접근방법 팀선정에 N과 M(2)에서 사용했던 코드 재사용했다.(조합) 근데 보수관계의 조합은 필요없어서 첫번째로 들어오는 수가 0인 조합만 조사했다. ischeck배열로 1이면 스타트팀, 0이면 링크팀에 넣고 또 스타트팀의 능력치 합산 점수, 링크팀의 능력치 합산 점수를 구한다. 그리고 이들의 차이는 gap변수(전역변수)에 저장하면서 최솟값을 갱신한다. f함수 끝낸..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 C++ 4는 2와 3을 합친 문제이다. 수열 내의 중복을 허용하고, 오름차순이다 2에서 사용했던 if문을 사용하고, 중복을 허용하기 때문에 반복여부를 체크하는 ischeck배열도 사용하지 않는다. 다만 중복을 허용하는 오름차순이기 때문에 for문 제어변수 i의 초기값을 result배열의 가장 최근 값부터 N까지로 한다.(=) 소스코드 // // 15652.cpp // back track..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 C++ 이게 순열이네 1은 순열은 아니다. 수열 내의 중복이 허용되지 않았다 이 코드가 제일 간단했다. 그냥 반복문돌면서 result에 넣어서 출력하면 끝 // // 15651.cpp // back tracking // // Created by 임수정 on 2020/07/08. // Copyright © 2020 임수정. All rights reserved. // #include usi..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 c++ N과 M(1) 문제의 연장선이다. 1은 순열이었고 2는 오름차순이라는 조건을 줘서 조합이다. 그래서 반복문을 0부터 N-1까지가 아니라 result 배열의 가장 최근의 수 부터 N-1까지 반복한다. (실제로 입력하는 수는 배열의 가장 최근의 수 보다 크고, N보다 작거나 같은 수이다. ) 이때 cnt가 0인 경우는 따로 처리해준다. result[-1]ㄸㅐ문 더 좋은 방법이 있을 ..