0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 컴퓨터과에서 저학년때 배우는 수식.. 이 문제는 중위표기식을 후위표기식으로 고치는 문제이다. 막막할 수 있지만 생각해보면 단순하다. 우선순위와 연산자를 처리해야 하므로 stack에 조건부로 pop, push를 처리해주면 된다. 먼저 문자열을 입력받고 인덱스를 순회하며 경우에 따라 처리한다. 알파벳 대문자인 경우 바로 정답으로 출력한다. (연산자와 관련없음) '(' 인 경우 ..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 결국 가장 먼 집부터 들려야 하므로, 그리디 알고리즘으로 해결해야 된다는 것은 알았다. 그러나 for문을 끝부터 돌리기에는 번거로워서 고민하다 stack을 사용하는 방법으로 해결하였다. 스택 관리 deliveries, pickups 별로 스택을 선언한다. 여기서 중요한 점은, 가장 먼 집이 택배나 회수할 것이 아무것도 없으면 안된다는 것이다. 왜냐하면,..

문제 출처 : https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 처음에 단순 구현으로 생각했으나, 문제를 보면 꼬리를 제거해야 하는 경우도 있고 머리 부분을 추가하는 경우도 있다. 즉 처음과 끝을 push, pop할 수 있어야 했기에 deque을 사용하기로 하였다. 방향 회전시키기 단순 구현이라 특별한 로직같은건 없으나 방향을 90도 회전 시켜야 할 경우에는 다음과 같이 풀이하였다. 인덱스를 접근할 dx, dy 배열을 선언한다. (상 우 하 좌 순..

문제 출처 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 이 문제는 아이디어가 잘 떠오르지 않는 문제였다.. 다른 여러 풀이를 참고했다. 현재 전구를 반복문을 돌린다. i 기준일때 i-1번째까지 정답과 일치하면 넘어간다. 이유는 i+1번째로 기준이 넘어가면 i-1은 더이상 영향을 받지 않기 때문이다. i-1번째가 일치하지 않는다면 스위치를 누른다.(뒤집기) 이 경우를 그냥 시작하는 경우 / 가장 처음에 뒤..

문제 출처 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리(최소 신장 트리) 우선 스패닝 트리는 그래프의 모든 정점을 잇고, 사이클이 없는 트리이다. 정점이 V개면 정점을 연결하는 간선은 V-1개이다. 최소 스패닝 트리는 간선의 가중치 합이 최소가 되는 스패닝 트리이다. 최소 스패닝 트리를 구하는 대표적인 알고리즘은 크루스칼(Kruskal), 프림(Prim) 알고리즘이 있다...

문제 출처 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 플로이드 워셜 알고리즘을 사용하는 문제이다! 다익스트라와 플로이드-워셜의 차이는 아래와 같다. 다익스트라 : 하나의 정점에서 다른 모든 정점의 최단거리 플로이드 : 모든 노드간 최단거리 플로이드 알고리즘의 프로세스는 아래와 같다. 인접 배열을 구한다. 1번노드를 중간 노드(거쳐가는 노드)로 설정해, 거쳐가는 경우의 비용이 더 작으면 배열을 갱신한다. n번노드까지 반복한..

문제 출처 : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 남극의 언어가 anta로 시작되고 tica로 끝난다 -> a c i n t는 필수로 가르쳐야 한다. 즉 K가 5 미만이라면 0을 출력하면 된다. a c i n t는 디폴트로 학습시킨다. 입력 단어에서 anta, tica를 빼고 저장해 시간을 줄일 수 있다. string str = ""; for(int i = 0; i > str; v.push_..

문제 출처 :https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 bfs로 생각할 수 있으나 다익스트라 개념을 도입해 풀어야하는 문제이다. 벽을 부수는 최소 수를 저장하는 dist 배열을 선언해 조건에 달아주면 된다. 코드 #include #include #include #include using namespace std; int M, N; int arr[101][101]; vector dist(101, vector(101..

문제 출처 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 이 문제는 불과 지훈이의 이동경로를 비교를 해야한다. 따라서 먼저 불의 시간 별 이동경로를 저장하는 배열을 만들어 계산한 뒤, 지훈이가 이동 가능한지 비교한다. 불 이동 경로 초기 입력 시 fire 배열은 INF로 초기화하고, 처음 불이 있던 자리만 0으로 저장한다. bfs로 기존 배열 값보다 값이 작으면 갱신하고 큐에 푸시해준다. int fire[1000][10..

문제 출처 :https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 불쌍한 준석이,,, 우선 완전탐색으로 생각했으나 유니온 파인드로 해결해야하는 문제임을 깨달았다. 유니온 파인드는 아래 패턴을 기억해야 할 것 같다. 1. 같은 집합으로 묶어주는 함수(unionParent) root를 찾아주는 함수(getParent)로 가져온 후 서로의 부모를 지정해준다. void unionPar..