알고리즘

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. 기둥과 보의 삽입, 삭제 여부와 설치할 위치 정보가 주어진다. 2. 조건에 맞게 삽입, 삭제를 차례로 시뮬레이션할 수 있도록 구현한다. [풀이] 처음 구현한 방법은 기둥, 보를 삽입, 삭제할 때 조건을 확인하고 다 넣어주는 것이었다. 그렇게 했더니 코드가 길어지고 답은 틀리는데 디버깅이 안되서 책보고 다시 짰다. 1. build_frame을 한 줄씩 읽어 기둥인지 보인지, 삽입할 건지 삭제할 건지 확인한다. 2. 삽입이면 append하고 조건에 맞는 설치인지 확인한다. 조건에 맞지 않으면 remove 삭제도 마찬가지로 먼저 remove하고 조건에 맞지 않으면 다시 append 3. 조건에 맞는지 확인하는 코드는 간단하다. [외울 것] * [x, y, 0] in answer : ..

●○○ [문제] 링크 1. 알파벳으로 구성된 문자열이 입력으로 주어진다. 2. 1개 이상의 단위로 문자를 자르고 연속되는 문자열을 압축하여 표현한다. 예) aabbaccc를 1개 단위로 압축했을 때 => 2a2ba3c 3. 이렇게 문자열을 압축했을 때, 압축된 문자열의 최소 길이를 구해라. [풀이] 1. 문자열의 길이를 s라고 했을 때, s/2이상의 크기로 자르는 것은 의미가 없다. 따라서, 문자열을 자르는 크기는 1부터 s/2까지이다. 2. 자르는 단위를 size라고 한다면 연속되는 지 확인할 단어 word = s[:size]로 두고 for문으로 size만큼 더하면서 문자열을 탐색해 나간다. - 만약 다음 문자열이 word와 같으면 연속되므로 count에 1을 더해준다. - 만약 문자열이 연속하지 않으..

●○○ [문제] 링크 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..

[문제] 1. 먼저 배포되어야할 순서대로 기능의 현재 개발 진도가 적힌 progresses와 각 기능의 개발 속도가 적힌 speeds가 주어진다. 우선순위가 낮은 기능이 높은 기능보다 먼저 개발이 완료되어도 먼저 배포x 우선순위가 높은 기능이 배포될 때 함께 배포된다. 2. 이 때, 배포마다 몇 개의 기능이 배포되는지를 return - 배포는 하루에 한 번 이루어진다. [풀이] 1. progresses와 speeds를 보고 배포날짜를 큐에 저장한다. (진도가 100%이상이 되는 날) - progresses + speeds*날짜 >= 100 - 날짜 = (100-진도) / 속도의 올림값 (ceil함수 사용) 2. 저장된 완료일 수를 탐색하며 기준보다 완료일이 더 크면 배포 못함. 1) 큐의 맨 앞 원소를 ..

[문제] 초 단위로 기록된 주식가격이 담긴 배열 prices가 주어진다. 이 때, 가격이 떨어지지 않은 기간은 몇 초인지 return한다. * 제한사항 prices의 각 가격은 1이상 10000이하 prices의 길이는 2이상 100000이하 [풀이] 1. 현재를 기준으로 다음 주식 가격을 확인한다. - 주식 가격이 떨어지지 않으면 count++ 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. = ₩3이 ₩2가 될 때, 1초가 걸리므로 그 동안은 가격이 떨어지지 않는다. - 위와 같은 설명 때문에 다음 주식 가격이 떨어지면 count++를 해주고 멈춘다. 2. answer에 count값을 넣어준다. [코드] #include #include using n..

[정답 코드] #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..