알고리즘/백준

https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 문제 제목이 너무 충격적이라 정리하고 싶어서 정리.. 문제 딱따구리 위치(2)에서 가장 가까운 음식 (3, 4, 5)까지의 거리를 구하는 문제 풀이 딱따구리 위치를 시작점으로 두고 bfs탐색. 거리 저장용 dist, 방문 여부 확인용 visited배열 2개를 생성. bfs함수 안에서는 dist값 ..

https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 어떤 수식이 주어졌을 때 괄호를 제거해서 나올 수 있는 서로 다른 식을 출력해라. 괄호를 제거할 때 서로 쌍이 되는 것만 제거할 수 있다. 제거 후, 올바르지 못한 괄호가 생기면 안된다. (올바른 식이 아니다.) 풀이 일단 쌍이 되는 괄호의 인덱스를 찾는다. - 열린 괄호를 만나면 스택에 해당 인덱스를 저장 - 닫힌 괄호를 만나면 스택에서 pop을 한 값과 현..

●○○ [문제] 링크 1. 현재 점수가 N점일 때, 이를 반으로 나눴을 때 양 쪽 각 자리수의 합이 같으면 럭키 스트레이트 기술을 사용할 수 있다. 예) 123402 => 123 / 402로 나누면 => 각 자리 수 합이 6으로 같다 [풀이] 1. 점수 N을 입력받는다 2. N//2를 기준으로 좌, 우 값을 더하고 비교한다 [외울 것] # 문자열 입력 a = input() # 문자를 int로 b = (int)a[0] [코드] score = input() N = len(score) left = 0 right = 0 for i in range(0, N//2): left += int(score[i]) for i in range(N//2, N): right += int(score[i]) if left == ri..

[정답 코드] #include #include #include #include #include #include using namespace std; typedef struct { int idx; int y; int x; }info; typedef struct { int sum; int num; }comb_info; const int MAX = 51; int map[MAX][MAX]; //나라인구 정보 bool vis[MAX][MAX]; //탐색 체크 int N, L, R; bool can_move = true; //상,하,좌,우 int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 }; vector comb; int answer = 0; //디버깅용 프린트 void pr..

[정답 코드] c++ #include #include #include #include using namespace std; typedef struct { int speed; //속도 int d; //방향 1:상,2:하,3:우,4:좌 int z; //크기 }info; //상어 정보 int R, C; //R - 세로y, C - 가로x int M; //초기 상어 수 vector map[101][101]; //어장~!~! vector temp[101][101]; int answer = 0; //잡은 물고기의 합. void print() { cout

[정답 코드] #include #include #include #include #include using namespace std; const int MAX = 100000000; //디버깅용 프린트 함수 void print(vector&v) { int s = v.size(); for (int i = 0; i < s; i++) { cout

지저분 그자체 [정답 코드] #include #include #include #include using namespace std; //디버깅용 프린트함수 void print(vector&v) { for (int i = 0; i N >> L; M = N; //map 이차원 배열 선언 vector map(N, vector(M)); for (int i = 0; i > map[i][j]; } } //가로방향 탐색 for (int i = 0; i < N; i++) { find(map[i]); } //세로방향은 어떻..

[정답코드] #include #include #include #include using namespace std; const int MAX = 9; //int map[MAX][MAX]; int N, M; vector virus; //y,x int dy[4] = {-1,1,0,0}; int dx[4] = {0,0,-1,1}; int ans=-1; int count_safe(vector& v) { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (v[i][j] == 0) cnt++; } } return cnt; } void dfs(vector&v) { queue q; for (int i = 0; i < virus.size..

[문제] 1) 정수 A, B가 주어졌을 때, *2 혹은 1을 추가하는 연산을 통해 A->B까지 가는 것이 목표. 2) 이 때,연산의 수행해야하는 연산 횟수의 최솟값을 구해라. ▷ 입력 : A, B (최대 10^9) [풀이] 1) 기본적으로 comma6oz.tistory.com/10 (숨바꼭질) 문제와 탐색방법은 유사하다. 2) bfs로 탐색하고 queue에 현재 노드와 연산 횟수를 저장한다. ▷ 현재 노드가 B가 되면 탐색을 종료하고 연산 횟수 반환한다. 3) 숨바꼭질 문제와 다르게 최대값이 매우 크므로 vector를 만들어서 거리 값을 저장하면 메모리 초과가 발생한다. ▷ vector을 이용해 BOJ에 제출했을 때 bad_alloc과 OutofBounds가 발생했다. ▶ 메모리 초과 해결 방법 ▷ in..

[문제] - M*N크기 배열에 토마토 정보가 주어진다. (1=익음, 0=안 익음, -1=없음) - 익은 토마토에 인접한 곳에 있는 토마토는 다음날 익는다. - 며칠이 지나야 모든 토마토가 익을 것인가 - 입력 : M,N, M*N배열 정보 - 출력 : 날짜 [풀이] - bfs로 배열을 탐색한다. (기본 껍데기 활용) - q.front()로 현재 노드를 설정하고 상하좌우 노드를 탐색한다. => 이 때, 날짜를 계산하기 위해 map[next]의 값을 map[cur]+1로 해준다. - 마지막에 map의 최댓값-1을 하면 모든 토마토가 익는 날짜를 알 수 있다. - bfs가 끝나고 map에 0이 남아있으면 다 익지 않은 것이므로 -1로 예외처리 필요. - 틀린 원인 : 배열을 입력 받을 때 m,n 헷갈려서.. [..

[문제] - M*N배열에 0,1을 입력하고 이어진 1의 묶음을 찾아내는 것 - 아래 그림처럼 이어진 1의 묶음을 세보면 5개 => bfs로 풀자 [풀이] - 기본 bfs알고리즘에서 시작 노드를 for문을 통해 새로 정해주면서 돌린다~ - 이미 방문했거나 0인 노드는 탐색 x - 주의) 테스트케이스마다 map과 vis를 memset으로 초기화해줘야된다. 까먹고 안했다가 틀림! [코드] #include #include #include #include using namespace std; #define X first #define Y second int M, N, K; const int MAX = 51; int map[MAX][MAX]; bool vis[MAX][MAX]; int ans = 0; int dx[..

[문제] - 수빈이 위치 N, 동생 위치 K로 나타낼 수 있다. (0 node+1, node-1, 2*node - 위의 3개 노드를 bfs방식으로 탐색한다. - node 또는 next가 map의 범위를 벗어나거나 node가 k, 즉 동생 위치에 도달했을 경우 continue * 런타임에러 발생 원인 : node 예외처리만 해주고 next에 대해서 처리를 안해줘서 발생 [코드] #include #include #include #include using namespace std; const int MAX = 100001; int n, k; vector map[MAX]; bool vis[MAX]; //방문 여부 확인 int dist[MAX]; //거리(초) 저장 void bfs(int start) { //초기..