꺼진불도다시보자

문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 접근방법 well known중에 well known infix to postfix 문제다. 연산자들은 따로 모아뒀다가, 낮은 우선순위 연산자가 들어올 때, 한꺼번에 postfix에 넣어준다. 여기서는 +, -, *, /가 전부다. 곱하기 나누기가 들어오면 따로 모아놨다가, 더하기 빼기 들어왔을 때, 다 빼서 postfix에 붙이면 된다. 그리고 중요한건 '('가 들어왔을 때 어떻게 처리하..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 접근방법 DP를 이용해 풀었다. 분명히 맞는 거 같은데, 틀렸다고 나와서 한참 헤멨다. 알고보니 cache 배열의 범위가 틀렸었다. 단순히 n의 범위가 16까지라서 cache[16][16]으로 정의했는데, 내가 범위 체크를 함수 들어가기 전이 아니라 함수 들어가고 나서 하기 때문에, 16 크기의 house배열이 입력으로 들어오는 경우, cache 17을 접근하게 되는..

문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 접근방법 막대기 사이 빗물을 채우기 위해서 배열을 2개 만들었다. 최고점을 저장하는 배열 arr와 블록이 쌓인 모양 그대로 2차원배열 block이다. 최소 w>2 이상일 때 빗물이 채워질 수 있다. 따라서 i = 2 부터 시작해서 block을 횡으로 탐색할건데, 이때 block의 높이인 arr[i]를 받아와서 heigth로 저장한다. height는 세로위치, j는 가로 위치..

문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 접근방법 앞서 사용했던 투 포인터를 사용했다. 투 포인터가 은근히 많이 쓰이나보다. 회전 초밥이기 때문에, dishes배열을 2개 이어 붙였다. 배열 이어 붙이는 것이 아주 유용하게 쓰인다. start와 end 포인터를 두고 그 사이에 있는 숫자들의 개수를 셌다. 그리고 while문이 돌 때마다 배열을 초기화했다. flag는 범위 안에 쿠폰 번호가 있는..

문제 https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 접근방법 단순 계산으로 접근했다. 파랑색, 빨강색 볼 개수를 각각 세고 가장자리에 있는 파랑색, 빨강색 볼 개수를 빼줬다. 가장자리에 있는 볼들은 움직이지 않아도 되는 볼들이다. 움직여야 할 볼이 적은 색을 선택해 그 숫자를 세면 된다. 코드 #include #include using namespace std; int main() { int n; cin >> n;..

문제 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 접근 방법 dp문제인 줄 알았다. 근데 투 포인터 문제라고 하길래 투 포인터가 뭔지 검색해봤다. 투 포인터를 알고 나서 다시 봤는데도 구현방법이 떠오르지 않아서, 다른 사람이 푼 걸 봤다. 그냥 끝까지 구현 해볼 걸 그랬다. 할 수 있었을 거 같은데, 아쉽다. 코드 #include #include using namespace std; int main() { int n, k; cin >>..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 접근 방법 BFS문제다. 코드를 줄이려 꼼수쓰지 않고, 코드가 길어지더라도 최대한 정석적으로 풀려고 노력했다. 코드 #include #include #include using namespace std; struct ground { int r; int c; int count; }; int dx[4] = {0, 1, 0, -1}; int dy[4] =..

[백준 9017] - 크로스 컨트리 c++ 문제 https://www.acmicpc.net/problem/9017 9017번: 크로스 컨트리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 www.acmicpc.net 난이도 - 실버3 접근 방법 구현 문제라고 써져 있지만, 정렬 문제에 더 가깝다고 생각했다. 처음엔 쉬워보였는데, 막상 구현하려니 조건이 까다로웠다. deleted_arr를 둬서 6명의 팀원이 없는 팀들을 제거한 상태를 저장하려고 했는데, 배열의 특정 원소를 삭제하는 함수를 몰랐다. 그래서 6명의 팀원이 존재하는 팀만 골라내어 deleted_arr..