2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 두개의 포인터를 활용하여 시작 인덱스와 끝 인덱스를 지정하여 합이 N이 되는 경우의 수를 구합니다. 합 N : s이동(s+1), 감소 합 == N : count+1 , s+1 pseudo-code /*pseudo-code*/ N // 목표 합 start = 1, end = 1 //시작, 끝 자연수 (포인터) count = 0, sum = 1 //개수, start 부터 end까지 연속된 자연수의 합 w..
11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 문제 11659 - 구간합 구하기의 2차원 버전 arr하나로도 구현 가능 하나, 일단 두개의 배열로 진행. 배열을 입력받아 arr에 저장 d라는 2차원 배열에 구간 합 저장. (이때 공식: d[i][j] = d[i][j-1]+d[i-1][j]-d[i-1][j-1]+arr[i][j]) (x1,y1)과 (x2,y2)를 입력받고, ans = d[x2][y2]-d[x2][y1-1]-d[x1-1][y2]+d[x1-1][y1-..
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 처음에 이중 for문으로 배열을 다 탐색하며 계산을 했으나 시간 초과 발생. 이전에 구한 값을 앞으로 구할 값에 사용 가능 → DP로 구현 가능. BufferedReader, StringTokenizer, nextToken으로 구현하는 것이 Scanner 쓰는 것 보다 훨씬 빠르다. 후기-> C++이랑 파이썬 쓰다가 자바로 코딩하려니까 적응이 안되는데.. 자바가 생각보다 실행시간도 길고 함수 사용도 복잡해서 적응하는데 시간이 좀 걸릴 것 같..
문제가 상당히 길다. 하지만 이전 문제들처럼 그냥 거리계산만 하면 된다. 기본 BFS문제에 속하는 문제이다. 맵의 시작 부분을 큐에 넣음과 동시에 BFS를 시작한다. 도달하지 않은 곳의 dist 값은 -1이고, 시작점으로부터의 거리가 dist 값에 업데이트된다. 생각해 주어야 할 것은, (n-1,m-1)번째 dist값이 -1이라면 길이 막혀서 갈 수 없는 곳이므로 -1을 출력한다는 것과, 시작점의 dist을 0으로 설정하였으므로 마지막에 값을 저장할 때 +1을 해줘야한다는 것이다. #include #include #include using namespace std; int dist[102][102]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int solution(v..
고민하다가 모르겠어서 풀이를 보고 생각을 해 보았습니다.. DFS에 대한 완벽한 이해가 안되었던 것 같고, 뭔가 재귀인 것 같다고 생각하긴 했지만 구현 방식이 생각나지 않았다. 재귀.. 너무 어려워요 sum과 index를 기록해가며 DFS를 진행한다. 제일 먼저 sum = 0, index = 0을 매개변수로 DFS 함수를 호출하면 DFS 함수 내에서 더하기 연산(sum = sum+numbers[0], index = 1), 빼기 연산 (sum = sum-numbers[0], index = 1)을 순차적으로 진행한다. sum은 numbers의 각 원소에 맞게 더하거나 빼게 되고, index는 다음 numbers의 원소로 넘어갈 때마다 1씩 증가한다. 종료 조건은 index와 numbers의 길이가 같은 경우..
기본적인 거리 계산 문제이다. 우선 dist 배열을 -1로 초기화해 주었다. 이중 for문을 돌면서 방문할 노드를 찾는다. #include using namespace std; int n,m,k; int board[102][102]; int dist[102][102]; int ans; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; for(int i=0;i>r>>c; board[r][c]=1; } for(int i=1;i
거리계산과 방문 체크 배열을 따로 만들지 않고, vis배열을 우선 -1로 초기화해서 한번도 방문하지 않은 노드를 -1로 나타낼 수 있도록 하였다. 방문을 한 경우 바로 전 노드의 거리에 +1을 해주었다. 그렇게해서 시작점부터 특정 정점까지 모든 위치의 거리를 구할 수 있었다. #include using namespace std; int n,m; string board[102]; int vis[102][102]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=0;i>board[i]; }//입력받기 for(int i=0;i
1. 시작점이 여러개인 경우 2. 거리 계산 두가지를 할 수 있으면 풀 수 있는 문제 같다. 1번의 경우 이중 for문으로 모든 정점을 돌며 시작점을 찾으며 bfs를 진행하면 되고, 2번의 경우 시작점을 기준으로 큐안에 들어가는 정점의 갯수를 세면 된다. 그리고 W,B의 경우를 각각 구하기 위해 BFS를 두번 구하였다. #include using namespace std; int n,m; string board[102]; int vis[102][102]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=0;i>board[i]; } //bfs를 ..
BFS와, DFS의 가장 기본적인 문제인듯 싶다. dfs는 재귀함수로 구현하였고, bfs는 큐를 사용하였다. 먼저 DFS의 경우, 그래프에서 노드간의 연결을 위해 벡터를 사용하였다. 그냥 이차원 배열을 사용해도 좋을 듯 하다. 입력 받으며 벡터에 저장할 때, 해당 그래프가 양방향임을 주의하자 "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 이라는 문구로 인해 sort가 필수적이다. 그러나 2차원 배열을 통해 1번 노드부터 m번 노드까지 방문하면서 1. 방문한 적이 있는지, 2. x번쨰와 i번째가 연결되어 있는지 확인하는 방식을 사용해도 좋을 듯하다. 다음으로 BFS의 경우, 우선 시작 노드에 방문 표시를 한 뒤, 큐에 푸시한다. 그리고 큐가 빌때 까지 무한 루프 내부..
- 재귀함수: 자기 자신 다시 호출 : 종료 조건 반드시 명시. 함수 무한 호출 가능 - DFS(Depth First Search) : 깊이 우선 탐색. 깊은 부분 우선적으로 탐색 : 스택 or 재귀함수 - DFS 동작 방식 1. 탐색 시작 노드 스택에 삽입, 방문 처리 2. 스택 최상단 노드에 방문하지 않은 인접한 노드 있으면 해당 노드 스택에 삽입, 방문 표시. 방문하지 않은 인접 노드 없으면 스택에서 최상단 노드 꺼낸다. 3. 더이상 2번 수행할 수 없을 때까지 반복 - 베이스 라인 void dfs(int x){ vis[x] = true; cout