![]()
https://www.acmicpc.net/problem/4963구상1. 가로, 세로 뿐만 아니라 대각선도 있으니 이를 고려해야겠다. 8번 반복해야겠네.2. bfs방식이겠다.3. bfs가 몇번 반복됐는지 보면 섬의 개수가 나오겠다.코드#include #include #include using namespace std;int map[51][51];bool visit[51][51];int w, h;int dx[] = {0,0,-1,1,1,1,-1,-1}; // 대각선까지 고려해아함int dy[] = {1,-1,0,0,1,-1,-1,1};int cnt = 0;void bfs(int a, int b){ queue> q; q.push(make_pair(a, b)); while(!q.empty()..
https://www.acmicpc.net/problem/1260 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결..
![]()
https://www.acmicpc.net/problem/1697문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.입출력 예제코드..
![]()
1260번: DFS와 BFS (acmicpc.net)import sysinput = sys.stdin.readlinen,m,v=map(int,input().split())di={}for _ in range(m): a,b=map(int,input().split()) if a in di: di[a].append(b) di[a]=sorted(di[a], reverse=True) else: di[a]=[b] if b in di: di[b].append(a) di[b] = sorted(di[b], reverse=True) else: di[b]=[a]def DFS(start): #깊이~후입선출=스택 st=list() visit=..
![]()
문제 & 링크https://www.acmicpc.net/problem/11660 풀이1. 테이블에 값을 입력 할 때 시작점인 (1, 1)부터 현재 위치인 (i, j)까지의 전체 누적합을 dp 테이블에 저장한다. 설명: 현재 위치까지의 누적합을 저장하기 위해서는 빨간 사각형(dp[i - 1][j])과 파란 사각형(dp[i][j - 1])을 더하고 둘이 겹치는 부분(dp[i - 1][j - 1])을 빼준 뒤 현재 위치의 값을 더해주면 된다. 2. 원하는 범위의 누적합을 구할 때 1에서 만든 dp 테이블을 이용하여 구한다.설명: 원하는 범위의 누적합인 초록 사각형을 구하기 위해서는 전체 사각형(dp[x2][y2])에서 빨간 사각형(dp[x1 - 1][y2])과 파란 사각형(dp[x2][y1 - 1])을 빼준 ..
![]()
문제 & 링크https://www.acmicpc.net/problem/1644 풀이1. 에라토스테네스의 체를 이용하여 4,000,000까지의 모든 소수를 구해준다. (2부터 4,000,000까지 반복문을 이용하여 탐색한다. 탐색된 수 자기 자신을 제외한 모든 배수들을 bool 타입을 이용해서 체크한다.)2. 반복문을 마친 후 체크되지 않은 수들이 곧 소수이기에, 이를 따로 배열에 저장한다.3. 투 포인터(i = 0, j = 1)를 이용하여 해당 인덱스에 임시 연속합(tmp)을 만든다.4. N이 소수일 경우 cnt를 1 증가시킨다.5. 임시 연속합(tmp)이 N보다 클 경우 임시 연속합에서 i 인덱스에 해당하는 소수를 빼고, i를 증가시킨다.6. 임시 연속합(tmp)이 N보다 작을 경우 j를 증가시키고,..
![]()
https://www.acmicpc.net/problem/10451Algorithm순열이 주어졌을 때, 존재하는 사이클의 수를 출력하는 문제이다. 문제에서 주어지는 순열 순서대로 graph에 넣어주면 [[3], [2], [7], [8], [1], [4], [5], [6]] 와 같은 그래프가 만들어진다.우리는 존재하는 사이클의 수를 알고 싶기 때문에, bfs를 돌면서 모든 그래프를 방문할 때까지 시작점을 달리하여 반복해 주면 된다.cycle_cnt = 0 while (False in visited): start_p = visited.index(False) bfs(graph,start_p,visited) cycle_cnt+=1즉, 반복문을 통해 bfs를 돌린후에 ..
![]()
https://www.acmicpc.net/problem/1158 K번 쨰 수가 되기 직전까지 맨 앞의 원소를 K-1 번 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)그리고 K번째로 뽑힌(poll) 원소는 출력하면 된다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Buf..
https://www.acmicpc.net/problem/13904문제웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다. 웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.입력/출력첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다. 다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다. 얻을 수 있는 점수의 최댓값을 출력한다.코드f..
https://www.acmicpc.net/problem/1417문제다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.예를 들어서, 마음을 ..
https://www.acmicpc.net/problem/2164문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.N이 ..
![]()
문제 & 링크https://www.acmicpc.net/problem/9252 풀이1. dp 테이블을 0으로 초기화한다.2. 두 문자열을 dp 테이블의 1부터 시작하도록 반복문을 설정한다.3. 각 문자열의 원소가 같을 경우 dp[i][j]라면 dp[i-1][j-1]에서 1을 더해서 저장한다. 대각선의 값에서 1을 더하는 이유는 각 문자열에서 i번째 j번째 문자가 빠졌을 때 i-1번째, j-1번째 까지의 공통 부분 수열이 1 줄어야 하기 때문이다.4. 각 문자열의 원소가 다를 경우 dp[i][j]라면 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다. 5. 3 - 4의 과정을 반복하며 dp 테이블의 마지막 원소에서 LCS의 길이를 구할 수 있다.6. dp 테이블의 마지막 원소(LCS의 길이)로..
