본문 바로가기

BOJ29

구현 (1) 18809번 Gaaaaaaaaaarden BFS BF 그래프 구현 시뮬레이션 14865번 곡선 자르기 구현 3954번 Brainf**k 인터프리터 자료구조 구현 스택 3678번 카탄의 개척자 구현 시뮬레이션 17472번 다리 만들기 2 BFS BF 그래프 구현 MST 16637번 괄호 추가하기 BF 17135번 캐슬 디펜스 BFS BF 그래프 구현 시뮬레이션 17406번 배열 돌리기 4 BF 구현 진짜 나는 좌표가 너무 헷갈린다. 공간지각능력이 좋은 사람은 아니라... 시각화가 너무나 중요하다. 과연 이 필기를 다시 꺼내볼 일이 있을 것인지,, 2021. 1. 29.
BOJ2618 경찰차 BOJ2618 경찰차 dp[ i ][ j ] dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리 T = 가장 최근 사건을 처리하기 직전의 상태 STEP 1. w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다. STEP 2. w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다. w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다. A-A: [ w-1 ][ * ] → [ w ][ * ] A-B: [ w-1 ][ * ] → [ w-1 ][ w ] B-A: [ * ][ w-1 ] → [ w ][ w-1 ] B-B: [ * ][ w-1 ] → [ * ][ w ] ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다. ㆍdis.. 2021. 1. 29.
BOJ13976 타일 채우기 2 BOJ13976 타일 채우기 2 BOJ2133 타일 채우기 같은 문제다. 다만 N의 범위가 다르다. 2133번은 1≤N≤30이기 떄문에 수열의 값을 모두 구해도 된다. 13976번은 1≤N≤1,000,000,000,000,000,000=10^18이기 때문에 행렬의 거듭제곱을 이용하여 풀어야 한다. 필기만 옮기려고 했으나 코드까지 첨부 더보기 #include #include using namespace std; long long DIV = 1000000007; struct Matrix { long long a[2][2]; Matrix() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; } Matrix(long long x, long long y, long long z, lo.. 2021. 1. 28.
BOJ11062 카드 게임 BOJ11062 카드게임 두 명 모두 최선의 전략으로 임할 때 얻는 점수를 구해야 한다. 게임이론 문제 분명 이전에도 본 적 있는 문제인데 헷갈려서 제꼈던 문제였을 것,, 최선의 전략으로 임한다는 말을 이해하기가 어려웠다. 이해하기보단 적용하기가? 미래 예측을 기똥차게 하겠단 소린데 어디까지 생각해야 할지, 완전 끝까지 생각하려면 어떻게 구현해야 할지가 막막했다. pair를 이용한 2차원 array로 풀었다. 재귀를 이용했으면 더 편했을 것도 같은데,, 구현할 때는 구할 수 있는 값부터 전체 배열을 채우는 식으로 빌드업함 dp[ i ][ j ] = 카드 j ~ i 로 게임을 진행할 때 { 먼저 시작한 사람의 점수, 상대방의 점수 } 카드 j ~ i 로 게임을 진행, X와 Y중 X가 먼저 카드를 뽑는다면 .. 2021. 1. 28.
기하학 (1) 고등수학 재밌다. 더보기고민을 안하고 풀어도 됨 바깥 삼각형의 중심 벡터 열심히 계산해서 연립방정식 풀면 된다 너무 재밌따. 피자 배치 닮음비 계산하고 지수 늘려주면서 K번째 피자를 찾는다. 외계인의 침투 모의고사 18번 문제 느낌임 아니면 26번,, 대충 먼말인지 알지 Cows 다각형은 삼각형으로 나눌 수 있다. 삼각형의 넓이는 K-고등수학을 배웠다면 구할 수 있다. 여기선 다만 점을 정렬해줘야 하는데 이때 컨벡스헐 개념이 필요했던 것 같네컨벡스헐 솔직히 아직 완벽히 알지 못하는 상태라 다음에 정리해줘야겠다. 2021. 1. 19.
BOJ1019 책 페이지 www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 이런 거 초등학생 때 많이 풀었던 것 같은데,, 경우의 수같은 거 배울 때 나오는 문제임 처음엔 2459가 있을 때 0001~2000 2001~2400 2401~2450 2451~2459 이렇게였나 뭐 비슷하게 수의 범위로 나눠서 생각하는 걸 시도했음. (실패함) 자릿수로 나눠서 생각하는 게 더 편했다. 1이 등장하는 횟수는 일의 자리가 1인 수의 개수 + 십의 자리가 1인 수의 개수 + ... 이거니까 N=2458, (1) 일의 자리가 k인 수의 개수 = _ _ _ k 인 수.. 2021. 1. 12.
BOJ13977 이항 계수와 쿼리 www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net = 16134 조합(Combination) 15791 세진이의 미팅 페르마의 소정리에 의해 p가 소수이고 a가 정수일 때, a^p≡a (mod p) ⇒ a^(p-1)≡1 (mod p) ⇒ a^(p-2)*a≡1 (mod p) 즉 mod p에서 a의 역원이 a^(p-2)가 된다. a^p구하는 건 재귀함수로 해주고 long long 주의 13977번의 경우 N!, K!, (N-K)!을 모두 구해야하니까 while 돌리기 .. 2021. 1. 12.
BOJ11003 최솟값 찾기 www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net i-L+1 ~ i 번 째 수 중 최솟값 출력 덱 이용하기 내 앞의 수가 나보다 크다 ⇒ 그 수는 필요없다. 내 앞의 수가 나보다 작다 ⇒ 내가 나중에 필요할 수도 있다. push는 뒤에서만 해준다. 덱을 앞에서부터 볼 때 읽은 순으로, 값은 오름차순으로 정렬되도록 한다. 1. 범위를 벗어난 값은 pop front 2. 앞의 수 중 나보다 큰 것 pop back * 이때 앞의 수의.. 2021. 1. 12.
BOJ2478 자물쇠 www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net 입력에 맞는 답 (k1, p, q, k2)가 여러 개 존재한다. 아래처럼 둘 중 뭐가 돼도 상관없다는 걸 먼저 파악함. 그 다음엔 가장 구하기 편한 걸 구하기로 했다. (3, 5, 7, 3): 12345678 → 45678123 → 45672183 → 72183456 (5, 3, 5, 1): 12345678 → 67812345 → 67218345 → 72183456 아래 여섯 가지 예시로 생각해보았다. .. 2021. 1. 7.

티스토리툴바