SiO2whocodes

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 수학3, 동적계획법 C++ 이항계수를 동적계획법으로 푸는 문제 (간략) 작년 알고리즘 수업에서 배우고 또 비슷한 손코딩 문제가 시험에도 나왔었던 문제 이항계수였는지는 기억안남 DP에서 피보나치와 함께 배운 기억이 난다. 두 문제 모두 재귀를 배울때 나오는 개념들이지만 사실 시간복잡도면에서 보면 배열을 사용해서 반복문을 쓰는게 훨씬 효율적이다. (이걸 동적계획법 부분에서 배움 매번 이런식이지 비효율적인거 실컷 가르쳐놓고 효율적인 방법 나중에 알려주기 교수님 : 하지만 ..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 브루트포스 C++ 규칙없이 칠해져있는 큰 판을 잘라서 8*8체스판을 만드는데 다시 칠해야 하는 칸이 최소인 경우 최솟값을 출력하는 문제 예전에 입력값 긴거 보고 패스했었는데 실버5라고 떠서 브루트포스 끝낼겸 시도해봤다. 접근방법 우선 접근방법은 브루트포스인 만큼 입력받은 큰 판에서 8*8판이 만들어 지는 모든 경우를 조사하는 것이다. 체스판을 다시 칠하는 칸의 개수를 조사하는 과정은 처음엔..

https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 수학 C++ 정수를 나눈 결과의 소숫점 백만자리까지 출력할 수 있어야 한다. double, float자료형 모두 백만자리까지의 소수점을 저장하지는 않으므로 나눗셈을 반복문으로 구현해서 값을 출력해야한다. 접근방법은 정수의 나눗셈을 반복문을 이용해서 구현하는 것 A/B라면 A를 B로 나눈 나머지에 10을 곱한다. 그 과정을 N만큼 반복한 뒤 마지막에 A를 B로 나눈 값을 출력하면 끝 소스코드 #..

https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 수학3 C++ 풀다가 느낀건데 수학으로 분류되는 문제는 지금의 나보다 고3의 내가 더 잘풀 것 같다. 첫번째 링을 한 바퀴 돌렸을 때 인접한 링이 도는 횟수는 첫번째 링의 둘레/인접한 링의 둘레이다. 결국 그냥 반지름의 비이다. R1/R2 구하는거라 뭐지 왜 실버3이지 했는데 문제가 의도한건 약분이었다. 약분은 두 수의 최대 공약수로 두 수를 나눈 값을 출력하는 방법으로 구현했다. 접근 방법 요약 인접하는 ..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 C++ 백트래킹의 고전 문제 N-Queen 문제이다. 아무리 그래도 규칙 설명 한 줄이 없다. 접근방법 알고리즘 수업 때 배운 로직을 사용했다. 각 행에 퀸이 놓여있는 열 인덱스를 담은 col 배열을 전역변수로 선언해두고 한 행 안에서 각 열에 대한 반복문을 돌면서 퀸을 놓고 함수를 재귀 호출한 뒤 다시 퀸을 거두면서 백트래킹을 구현했다. promising을 함수 초반에 호출하여 검사하는게 직관적으로 와..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 www.acmicpc.net 수학 C++ 접근방법 처음엔 조합으로 풀어보려고 했다. 옷을 한개 골랐을 때 ~ cnt(종류의 수)까지의 모든 의상의 조합을 구한 다음에 종류별 옷의 개수를 곱한 뒤 모든 값을 더하려고 했다. 하지만 코드가 너무 복잡해졌다. 포기 이 문제의 가장 큰 힌트는 그 종류의 옷을 안 입는 경우를 추가해서 경우의 수를 구하는 것이다. 그리고 마지막에 아무것도 안입는 경우(1개)를 빼면 된다. 아주 간단한 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 수학 C++ 시간복잡도가 문제 O(N)으로 풀어야 하는 문제인 것 같다. 배열을 총 두개를 사용했는데, 처음 입력받은 숫자가 들어있는 배열과 본인을 포함하는 연속된 수들의 합 중 최댓값을 저장하고 있는 배열 바로 전 수를 포함한 최대 연속된 수의 합에 본인을 더한 것과 본인을 비교해서 큰 값을 배열에 저장한다. 그 배열에서 가장 큰 값이 연속된 수의 최대값이 된다. 로직에서 힌트를 조금 얻었다. 소스코드 #..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 � www.acmicpc.net 스택 C++ 배열로 만든 스택 기본 자료구조 ..진짜 말할게 이것뿐.. C++에서 문자열 다루는거랑 동적할당,벡터 쓰는게 익숙하지 않다. 그래서 쉬운문제여도 문자열을 다뤄야 하면 자바나 파이썬을 쓰게 되고 벡터는 아직도 익숙해지지가 않아서 찾아가면서 하는데 좀 더 많이 쓰려고 노력해야겠다. 부족한 부분을 찾아가는 유익한 문제풀이 시간~ 소스코드 #include #include..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 수학3 C++ 리터럴리 두 정수의 최대공약수랑 최소공배수를 출력하는 문제다. 최대공약수는 둘 중 작은 수부터 하나씩 감소시키면서 검사하고(이렇게 안하고 좀 더 효율적으로 할 수 있겠지만 통과는 된다) 최소공배수는 둘 중 작은 수부터 그의 배수를 검사한다. 끝 오늘 문제는 폰코딩했다. ios문자랑 아스키코드가 안맞는건지 “랑 - - 이 코드로 인식이 안돼서 계속 컴파일 에러가 떴었다.. 이전에 풀었던 코드에서 가져와서 고쳐서 냈는데 이번엔 걍 틀렸습니다.; 해결못하..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 다이나믹 프로그래밍 C++ 접근방법 문제에 떡하니 피보나치 같은 규칙을 찾아서 풀으라고 써있어서 그렇게 풀었다. 사실 그림만 보면 p[i] = p[i-1] + p[i-5] 가 맞지만 p[i-2] + p[i-3] 으로 제출해도 맞다. 처음엔 불필요한 계산을 최대한 안하려고 (동적계획법이니까) 변수도 더 쓰고 처리도 더 했었는데 그런거 다 안해도 통과되길래 그냥 다 지우고 최대한 간결하게 제출했다. 소..