분류 전체보기

[백준 1799] 비숍 C++

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

Bomb Lab Solution Phase_1 ~ secret_phase

- string comparision 0x555555556a50 에 있는 문자열이 “All your base are belong to us.” 이고, strings_not_equal함수에 해당 문자열을 넘겨주고 입력 받은 문자열과 해당 문자열을 비교해서 같으면 retq로 넘어감을 알 수 있었습니다. Answer : All your base are belong to us. - loops 6개의 숫자를 입력 받고 가장 먼저 입력 받은 수(%rsp)와 1을 비교해서 같지 않다면 bomb입니다. 따라서 첫 번째 숫자는 1임을 알 수 있었습니다. %rsp(입력 받은 배열의 첫 부분)을 %rbx에 넘겨주고 %rbp 에는 배열의 마지막 주소값을 넘겨줍니다. Loop 부분입니다. %rbx는 입력 받은 배열의 현재 in..

백준 목표달성 그런데

갑자기 플레V가 되었다ㅋㅋ class5를 달성해서 갑자기 50포인트가 올라서 그렇다.. 완전 물 플레; 아직 많이 부족한데 3주전에 비해서 29문제를 더 풀었다 주로 골드 2 ~ 5문제 위주로 풀고있는데 슬슬 확 어려운 문제도 도전해봐야겠다 못 풀면 못 푸는대로 배울게 있겠지ㅋㅋㅋㅋ 시스템 소프트웨어랑 운영체제가 갈수록 어려워진다 운체는 이론보다 과제가 너무 숨막히고 시소는 2-1 과목인거 치고 너무 어려운데.. 누가 좀 도와줬으면.. 알고리즘 포스팅은 나름 꾸준히 올리고 있지만 프로젝트에 쓰는 django랑 학교에서 배우는 OS, Systemsoftware같은 지식들은 포스팅 하기가 막막하다 시험 공부하면서 좀 집중적으로 올려야겠다ㅠ 미래의 나는 이걸 보고 무슨 생각을 할까

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..

[백준 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]의 초..