![]()
문제 링크 https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 풀이 바로 위 행의 인접한 두 수의 합을 구하기 위해 다음과 같은 형태로 배열을 만들었습니다. 파란색 삼각형 부분은 n 이 5일때 나오는 형태입니다. [n+1][n+1] 크기만큼의 배열을 선언하고 0으로 초기화합니다. (1,1) 위치의 값을 1로 초기화하면 세번째 행부터 모든 값은 바로 위 행의 인접한 두 수의 합으로 구할 수 있습니다. 세번째 행은 배열에서는 2에 해당하므..
![]()
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수의 성질은 0으로 시작하지 않고, 1이 연속해서 나오지 않는 수를 의미한다. N을 나열하면서 예를 적어보면서 점화식을 쉽게 찾을 수 있었다.N=1 → 1N=2 → 10N=3 → 100, 101N=4 → 1000, 1001, 1010N=5 → 10100, 10110, 10000, 10001, 10010 이친수의 성질에 의해서 반드시 처음 두자리 수는 1과 0이 차례로 오게되고, 이후..
![]()
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제분석 첫째 줄에 N을 입력 받는다. 여기서 N은 이후에 입력받을 숫자들의 개수이다. 다음으로 둘째 줄부터는 N개의 수2를 엔터를 이용해서 입력받는다. 여기서 숫자들은 무작위로 입력을 받는 것이다. 무작위로 입력받은 숫자들을 다시 오름차순으로 정리하는 것이 2750번의 문제 내용이다. 코드 문제풀이 입력받는 input() 코드를 이용하는 것보다 시간이 조금 더 단축하기위해서 stdin.readline()..
![]()
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제분석 첫째 줄에 N을 입력 받는다. 여기서 N은 이후에 입력받을 숫자들의 개수이다. 다음으로 둘째 줄부터는 N개의 수를 엔터를 이용해서 입력받는다. 여기서 숫자들은 무작위로 입력을 받는 것이다. 무작위로 입력받은 숫자들을 다시 내림차순으로 정리하는 것이 2750번의 문제 내용이다. 코드 문제풀이 입력받는 input() 코드를 이용하는 것보다 시간이 조금 더 단축하기위해서 stdin.readline()을..
![]()
https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 분석 이 문제는 중복된 정수를 제외하고 오름차순으로 정렬한 결과를 출력하는 간단한 문제이다. 코드 n = int(input()) arr = set(map(int,input().split())) arr = sorted(arr) print(" ".join(map(str,arr))) 문제풀이 이번 스터디를 통해 배우지 않았더라면 리스트를 사용하여 조건문을 활용해 중복된 값은 넣지않는 코드로 구현을 하였겠지만, 이번에 set이라..
![]()
문제 0부터 9까지의 숫자가 표시된 카드를 가지고 두 사람 A와 B가 게임을 한다. A와 B에게는 각각 0에서 9까지의 숫자가 하나씩 표시된 10장의 카드뭉치가 주어진다. 두 사람은 카드를 임의의 순서로 섞은 후 숫자가 보이지 않게 일렬로 늘어 놓고 게임을 시작한다. 단, 게임 도중 카드의 순서를 바꿀 수는 없다. A와 B 각각이 늘어놓은 카드를 뒤집어서 표시된 숫자를 확인하는 것을 한 라운드라고 한다. 게임은 첫 번째 놓인 카드부터 시작하여 순서대로 10번의 라운드로 진행된다. 각 라운드에서는 공개된 숫자가 더 큰 사람이 승자가 된다. 승자에게는 승점 3점이 주어지고 패자에게는 승점이 주어지지 않는다. 만약 공개된 두 숫자가 같아서 비기게 되면, A, B 모두에게 승점 1점이 주어진다. 10번의 라운드..
![]()
오늘은 백준 알고리즘 5582번 공통 부분 문자열문제를 풀어보는 시간을 가져보겠습니다. 이 문제는 다이나믹프로그래밍으로 접근하면 수월하게 풀 수 있습니다. 문제 먼저 보겠습니다. 이 문제는 행렬테이블을 그려서 규칙성을 발견하여 점화식을 만들어 풀 수 있습니다 위의 그림처럼 문자열 두 개의 문자가 같을 때 이전에 같았던 dp[i-1][j-1] + 1 임을 파악할 수 있고 이를 토대로 arr1[i] == arr2[j]같다면 dp[i][j] = dp[i-1][j-1] +1 임을 이끌어낼 수있습니다. 코드는 다음과 같습니다. #include using namespace std ; string arr1; string arr2; int dp[4001][4001]= {}; int ans; int max_res..
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 집의 개수가 최대 20만개이고 집의 좌표가 10억까지 가능하므로 이진탐색으로 풀어야 한다. 1. 공유기 좌표를 정렬 2. 정렬된 공유기 좌표에서 가장큰 좌표와 가장 작은 좌표의 차이가 가능한 최대값 3. st = 1, ed = (가장 큰 집의 좌표 - 가장 작은 집의 좌표)로 두고 이진 탐색을 한다. 4. 첫번 째 집에는 무조건 공유기..
https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제분석 먼저 정수 입력이 주어진다. 입력된 정수에 따라 loop 문을 돌면서 빈 리스트에 append를 하거나 pop을 하고 마지막에 리스트의 총합을 출력하면 되는 문제이다. 문제에서는 0을 입력받을 경우 pop을 하고 0 이외의 정수일 경우 해당 정수를 리스트 안에 집어넣도록 하였다. 코드 from sys import stdin A = [] N = int(st..
https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 피보나치 수 문제인데 범위가 커져서 1,000,000,007로 나누는 문제이다. 나머지 분배법칙에 대해 자세히 알고있지 못하여 살짝 해맸는데 나머지 분배법칙만 잘 알고 있으면 dp를 사용하여 쉽게 풀수 있는 문제이다. 나머지 분배법칙의 증명은 다음 블로그를 참고하였다. https://sexycoder.tistory.com/66 모듈러 연산의 성질과 증명 모듈러 연산의 성질과 증명 위와 같이 모듈러 연산은 나머지를 구하는 연산자이며 다음의 분배법칙이 모두 성립한다. 왜 이런지 궁금해서 계속 ..
https://www.acmicpc.net/problem/19946 19946번: 2의 제곱수 계산하기 263 = 9,223,372,036,854,775,808 까지는 계산을 잘 하다가 264를 264-1인 18,446,744,073,709,551,615로 계산을 잘못해버렸다. www.acmicpc.net 문제에서 2의 제곱을 곱하다가 실수로 1을 빼버리는 순간이 단 한 번 존재한다고 하고, 실수할 때가 언제인지 구하라고 합니다. 풀이는 두 가지가 존재합니다. 첫 번째 풀이 첫 번째는 2의 제곱은 계속 짝수만 나오는데, 1을 빼버리면 그때 한 번 홀수인 값이 존재한다는 것을 이용하는 풀이입니다. 이 경우에는 홀수인지 짝수인지 확인하면서 짝수면 2로 계속 나누면 되지만, 홀수가 나오는 순간부터는 1을 더해..
![]()
https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 문제 풀이 첫번째 줄에서 얻은 값들을 n이라는 리스트에 저장하고, 두번째 줄부터 입력되는 탐사 영역의 각 구간들을 source라는 2차원 리스트를 생성하여 값을 저장한다. 동시에 각 구간에서의 최댓값을 저장할 result라는 2차원 배열을 source와 같은 크기로 생성한다. wook는 오른쪽이나 아래쪽으로 한 칸씩만 이동하기 때문에 바로 전에 다녀온 길은 위쪽이나 왼쪽에서의..
