boj

[백준 1799] 비숍 C++

1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹 연습하기 #4 1. 문제풀이 아이디어 비숍의 특징 : 체스판의 검은 칸에 있는 비숍과 흰색 칸에 있는 비숍은 서로 아무 영향을 끼칠 수 없다. 이 문제를 정석적인 백트래킹으로 푼다면 시간 복잡도는 O(2^(N*N))이 된다.. 체스판에 모든 곳에 비숍을 놓을 수 있고 N=10이면 각각의 칸마다 ( 비숍을 놓는다 or 놓지않는다 ) 2가지의 경우가 생기므로 2^100가지의 경우를 모두 탐색해야한다 2^100 = 1.2676506e+30 이므로 참신한 방법이 필요하..

[백준 10026] 적록색약 C++

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net BFS 연습 #1 전형적인 BFS 탐색 문제이다 색약인 경우에 'R' 과 'G' 를 같다 생각하고 탐색하게 해주면 문제없이 풀 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6..

[백준 14499] 주사위 굴리기 C++

14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 주사위가 굴러가는걸 내가 어떻게 아냐고.. 라고 처음에 생각했었는데 생각보다 할 만했던 문제였다 삼성 역량평가는 물체가 좌표상에서 움직이는 시뮬레이션 문제가 정말 주된 유형인듯하다 주사위가 굴러가는걸 어떻게 표현할까? 문제에 그려져 있는 주사위 평면도를 보고 풀이방법을 떠올릴 수 있었다.. 저게 없었으면 못풀었을지도 dice[i] 는 i번 면에 적힌 숫자를 의미한다..

[백준 12852] 1로 만들기 2 C++

12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net dfs + 백트래킹 기법을 사용해서 푼 문제 vector temp : dfs를 돌면서 거쳐온 숫자가 순서대로 저장되어 있는 벡터 (경로 저장) solve 함수의 cnt는 현재 사용된 연산의 횟수 solve함수가 실행 될 때마다 현재 숫자 n을 경로벡터(temp)에 저장해 주고 n == 1 이 되면 현재 결과 값과 비교해서 cnt값이 더 작다면 지금까지 지나온 경로를 ret 벡터에 넣어준다 모든 경로를 탐색하는게 기본 동작이지만 if(cnt > result) return; 코드가 있기 때문에 현재 구해진 결과값보다 지금 경로에서의 연산 사용횟수가 많아진다면 return을..

[백준 2533] 사회망 서비스(SNS) C++

2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #3 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 지난 포스팅 우수마을과 다르게 dp[now][0] -> 현재 친구가 얼리어답터가 아니라면 연결된 모든 친구는 얼리어답터여야 한다 이므로..

[백준 1949] 우수 마을 C++

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #2 [백준 15681] 트리와 쿼리 C++ 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1. hyeo-noo.tistory.com 이전 문제에서 아주 조금 개념이 추가된 트리 동적계획법 문제를 풀어보았다 만약 1번 ..

[백준 15681] 트리와 쿼리 C++

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #1 R이 트리의 기본 루트일 때 정점 U를 루트로 하는 Subtree에 속한 정점의 수를 출력 문제 이해를 위한 설명! 트리의 기본 루트는 5이다 사진에서 4를 루트로 하는 서브트리는 아래와 같다 그림과 같이 4를 루트로하는 서브트리의 정점은 1, 2, 3, 4 이다 (자신도 서브트리에 물론 포함) 트리의 리프노드 까지 가면 dp[now]를 반환한다(dp[i]의 초..

[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 돌대가리 건너기 다이나믹 프로그래밍 처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다.. 결국 어쩔 수 없이 구글을 참고했는데.. 단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다 dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수] 처음 dp배열을 -1로 초기화 시켜주고 현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..

[백준 17136] 색종이 붙이기 C++

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹 연습하기 #3 삼성 A형 기출 문제 백트래킹을 효과적으로 적용하기 위해서 가장 큰 색종이 먼저 덮어줘야하는 그리디 기법이 사용되었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ..