devlog

출처 : 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 dp를 활용해서 풀이하는 문제이다. 0에서 n번째 까지 동전이 있는데 이중 for 문을 돌며 0번째 동전만 사용했을 때부터 n번째 동전까지 다 사용한 경우까지 더하면 된다. for (int i = 1;i n >> k; for (int i = 1;i > c[i]; } memset(dp, 0, sizeof(dp)); dp[0] = 1; //0원을 만드는 경우의 수는 1이라고 하자 for (int i =..

풀이 방법 반복된 계산을 줄여 풀이하는 dp 문제이다 stairs배열에는 계단의 점수를 저장하였다. (0인덱스에는 시작점) dp배열은 dp[i] == i번째 계단까지 오는 최대 점수이다 (i 계단을 밞고 있어야 한다) dp[1]은 당연히 stairs[1]이고 dp[2]는 stairs[1] + stairs[2]보다 큰 경우는 없으므로 stairs[1] + stairs[2]가 된다. 그럼 dp[3]은 stairs[1] + stairs[3] 또는 stairs[2] + stairs[3]가 될 수 있다. 그럼 dp[n]인 경우 점화식은 dp[n-3] + stairs[n-1] + stairs[n] (n-3을 밞고 있는 경우 중 최대 + n-2계단 뛰어넘고 n-1, n-2 계단 연속으로 밞기) 또는 dp[n-2] +..

출처 : 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 퀸끼리는 같은 행, 열, 대각선에 놓일 수 없다. 위의 세 가지 조건중 하나(행)를 기준으로 잡고 퀸의 위치를 저장하였다. (같은 행에는 2개의 퀸이 놓일 수 없기에 한 행에는 무조건 1개의 퀸만 배치) 그래서 배열 queen_col [i]는 i번째 row에 퀸이 몇 번째 col에 있는지를 뜻한다. 백트레킹을 통해 문제를 해결해 준다. can함수를 통해 퀸을 배치할 수 있는지 확인해 준다. 같은 col인지는..

출처 : 11404번: 플로이드 (acmicpc.net) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 방법 플로이드 와샬 알고리즘을 사용하면 된다. #include using namespace std; int INF = 987654321; int n, m, s, e, w; int edge[101][101]; void floyd() { for (int i = 1;i > m; for (int i = 1;i s >> e >> w; if (edge[s][e] > w) { edge[s][e] = w; } } f..

출처 : 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 방법 일단 각각의 섬들을 구분하기 위해 섬에 번호를 붙여 bfs를 통해 land배열에 넣어 주었다. 거리를 구할 때 중복된 경우를 처리하지 않기 위해 섬의 고유 넘버가 작은 쪽에서 큰 쪽으로 가는 경우만 처리했다. (큰 쪽에서 작은 쪽으로 가는 길과 작은 쪽에서 큰 쪽으로 가는 길이 똑같기 때문) for문을 통해 맵 전체를 돌며(완전 탐색) s_bfs함수를 통해 bfs를 해주는데 이때 만약 다음 칸이 0..

출처 : 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 방법 일단 몇 덩어리(변수 cnt) 인지 판단 후 0이면 두 덩어리 이상 안 되는 케이스 이므로 0을 출력한 후 종료 두 덩어리 이상이면 year(기간)을 출력한 후 종료하면 된다. 만약 아직 한 덩어리 라면 빙하를 녹여주는 작업이 필요하다 빙하는 동시에 녹는데 한 덩어리씩 녹여주는 작업을 한다면 먼저 녹인 빙하가 다른 빙하에 영향을 줄 수 있기 때문에 (ex 빙하가 녹아 0이 되면 이 빙하랑 인접해..

출처 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 방법 평범한 문제 처럼 보이지만 순간이동을 할 때에는 0초라는 재밌는 조건이 있다. 그래서 bfs할 때 그냥 queue를 사용하면 0초라는 조건 때문에 복잡하게 된다. (시간 많이 걸리는 경우를 먼저 q에서 pop 되는 경우 때문) 그래서 우선순위 queue를 사용해서 시간이 작게 걸리는 경우를 먼저 pop 하여 사용하면 문제를 해결할 수 있다. #..

출처 : 코딩테스트 연습 - 네트워크 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 방법 bfs/dfs를 반복 하면 네트워크의 개수를 알 수 있다. for 문을 돌면서 방문하지 않은 네트워크를 발견 했을때 bfs/dfs를 수행하면 된다 #include #include #include #include using namespace std; int visited[201]; void bfs(int k, int n, vector computers) { q..

출처 : 14226번: 이모티콘 (acmicpc.net) 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 방법 bfs를 이용 시 동일 단위크기로 나누는 것이 중요하다 처음에는 queue에 화면에서 이모티콘 하나를 삭제하는 경우 time + 1인 경우와 화면에서 클립에 복사하고 클립에서 다시 화면으로 복사하는 경우 time + 2로 나누었는데 이렇게 하면 time의 크기가 달라져 복잡해진다. 그리고 항상 클립과 화면의 이모티콘의 개수가 똑같아진다는 오류도 생긴다 그러므로 1. 화면에서 이모티콘 하나를 삭제하는..

출처 : 3584번: 가장 가까운 공통 조상 (acmicpc.net) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 방법 처음에는 bfs 나 dfs를 활용하여 문제를 풀 생각을 하였지만 그러기엔 완전 탐색방법 밖에 생각이 안 났다. 이 방법은 시간이 너무 오래 걸릴거 같아 다른 방법을 생각하였다. 처음에 입력 A, B를 받을 때 바로 배열 parent에 parent[B] = A로 저장하여 자신의 부모를 저장하였다. 그리고 공통 조상을 구할 노드 중 한..