IT세상

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include using namespace std; int n, m, v; vector graph[1001]; bool visited_dfs[1001]; bool visited_bfs[1001]; void dfs(int x){ // 현재 노드를 방문처리 visited_dfs[x] = true; cout v; for(int i=0; i> x >> y; grap..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 #include using namespace std; int n, m; int graph[201][201]; // 이동할 네가지 방향 정의(상 하 좌 우) int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int bfs(int x, int y){ // 큐 구현을 위해 queue 라이브러리 사용 queue q; q.push({x,y}); // 큐가 빌 때까지 반복 while(!q.empty()){ int x = q.front().first; int y = q.front().second; q.pop();..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 #include using namespace std; int n, m; int graph[1001][1001]; bool dfs(int x, int y){ // 주어진 범위를 벗어나는 경우 즉시 종료 if(x=n || y=m){ return false; } // 현재 노드를 아직 방문하지 않았다면 if(graph[x][y] == 0){ // 해당 노드 방문 처리 graph[x][y] = 1; // 상하좌우 위치들도 모두 재귀적으로 호출 dfs(x-1, y); dfs(x, y-1); dfs(x+1, y); dfs(x, y+1); return t..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 스택 자료구조 설명(선입후출) 스택 동작 예시 스택 구현 예제 stack s; // 선언 s.push(x); s.pop(); 큐 자료구조(선입선출) 큐 구현 예제 queue q; //큐 선언 q.push(x); q.pop(); 재귀함수 설명 재귀 함수의 종료 조건 DFS(Depth-First Search) 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색 - 스택 자료구조 혹은 재귀 함수 사용 #include using namespace std; bool visited[9]; vector graph[9]; void dfs(int x)..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp[n]은 n개를 구입 할 때 최대 금액으로 정하고 n=1 은 p[1]로 초기화한다 그리고 n=2부터 dp[n] = dp[n-i] + dp[i] 의 점화식을 이용해 풀면 된다 #include using namespace std; int n; int p[1001], dp[1001]; int main(void) { cin >> n ; for(int i=1; i> p[i]; } dp[1] = p[1]; fo..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 전에 풀어봤던 문제라서 쉽게 해결됐다 배열 a에 수열을 넣고 dp배열에는 i번째 값을 포함하는 가장 긴 수열의 수를 넣는다 dp배열은 1로 초기화하고 a값을 차례대로 비교하면서 자신의 값보다 작은 값의 dp값에 1을 더해준다 #include using namespace std; int n; int dp[1001] = {..

내가 보기에 이 책의 결론은 크게 1. 지금 하고 있는 일을 사랑해라 2. 누구에게도 뒤지지 않을 만큼 노력해라 인 것 같다 책 초반에는 일에 미친 사람인가 했고 읽으면서는 왠지 사장님들이 좋아할 내용 같다는 생각을 했다 나는 일을 생계를 위해 마지못해 하는 사람은 아니고 그래도 즐겁게 하는 편이라 공감되는 내용도 있었다 현재의식과 잠재의식에 대한 이야기가 나오는데 나는 코드를 짜다가 해결을 못하고 퇴근했는데 샤워하다가 갑자기 방법이 떠오르는 경험을 한 적이 있었다 개발자 밈 같은 글도 나와서 웃겨서 찍었다 물론 책 내용에서는 우스갯소리가 아니라 뒤에 진지한 내용이 나옴 그리고 이런 내용은 직장인뿐만 아니라 시험준비를 한다거나 해서 확신이 필요한 사람들에게 용기를 줄 수 있는 내용인 것 같기도 했다 책을..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 점수를 담는 배열 arr[i][j] 와 (i. j)를 포함하는 스티커 점수의 최대값 dp[i][j] 배열을 선언해준다 j열의 점수를 계산하면 j-1 대각선에 있는 점수랑 j-2 대각선에 있는 점수 중 큰 값을 비교해 자신의 값과 더해주면 된다 #include using namespace std; int t, n; int dp[2][100001], arr[2][100001]; vo..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 처음에는 숫자 배열만 보고 p[n] = p[n-2] + p[n-3] 라고 생각했는데 직접 그림을 그려보니 p[n] = p[n-1] + p[n-5] 였다 그리고 어느순간 int의 범위를 벗어나서 배열은 long long 형으로 선언했다 #include using namespace std; int tc; long long a[101] ={0,1,1,1,2,2}; int main(void) { cin >> ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 두가지 방법으로 풀 수 있는 것 같다 다른 블로그들을 찾아보니 피보나치 수열로 많이 푼 것 같다 나는 다른 규칙을 찾아서 dp[n][s] : s로 끝나는 n자리 이친수 개수라고 정하고 dp[n][0] = dp[n-1][0] + dp[n-1][1] dp[n][1] = dp[n-1][0] 라는 점화식을 가지고 코드를 짰다 #include using namespace std; int n; l..