시나위

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 문제이다. 문자열이 주어졌을때 뒤집어서 같은 숫자를 만들어야한다. 뒤집는 횟수를 구하기 위해 값이 바뀔때마다 하나씩 체크하고 2로 나누어주면된다. (2로 나눈 이유는 예제 입출력에서 규칙을 찾아내었다.) #include int main() { char s[1000000]; int cnt = 1, i; scanf("%s", s); for (i = 1; s[i] != '\0'; i++) { i..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다. # import sys; input = sys.stdin.readline def backtrack(ind, limit): global s, stack if ind == limit: max_v = max(stack) for i in range(1..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net DP로 풀면 되는데 자료형을 주의해야한다. #include #include #include int arr[100][100]; long long dp[100][100] = { 0, }; int main() { int n, i, j, tmp; scanf("%d", &n); int* arr = (int*)malloc(sizeof(int) * n * n); long long* dp = (lon..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS로 진행했다. #include #include #include using namespace std; #define D(s) ((2 * (s)) % 10000) #define S(s) (((s) + 9999) % 10000) #define L(s) (((s) % 1000) * 10 + ((s) / 1000)) #define R(s) (((s) / 10) + (((s) % 10) *..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 그래프 탐색 알고리즘중 하나인 floyd-warshall 알고리즘을 사용하는 문제이다. 해당 알고리즘은 dijkstra와 달리 모든점에서 모든점까지의 최소거리를 탐색할때 사용한다. floyd warshall 알고리즘을 간단하게 설명하면 (1) s에서 e까지의 거리를 직접 가는 경우(cost[s][e])와 (2) k 점을 거쳐 가는 경우(cost[s][k] + cost[k][e]) 두 개를 비교하면..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 시뮬레이션과 백트래킹으로 모든 조합을 만들면 된다. i번째가 i번째로 가는 시뮬레이션 부분은 어렵지 않지만 백트래킹으로 조합을 만들때 중복되는 거 없이 수를 최소한으로 줄여야 통과할수 있었다. #include #include using namespace std; int N, M, H; int ladder[32][12]; int answer; bool check() { int i, r, c; fo..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 최단거리를 찾는 BFS 문제이다. 2차원 배열에서 방문하지 않은 점을 방문하면서 탐색하면 되고, 탐색도중 그람이 있으면 그 위치부터 맨해튼 거리값을 더해서 최소 값이 되는지 확인하면 된다. #include #include #include using namespace std; int map[100][100] = { 0 }; int N, M, T; int d[8] = { -1,0,0,..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 이 문제는 s에서 출발해서 t까지의 최소 가중치를 구하는 문제이다. 다익스트라를 사용하면 쉽게 구할 수 있다. #include #include #include using namespace std; #define INF 1234567890 int dijkstra(int start, int end, int size, vector linked_list) { int cur, cur_dist, adj..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 언제 풀었는지 모르는 문제지만 새롭게 풀었다. 푸는 방식은 deque같은 자료구조를 사용하지 않고 배열로만 접근해서 풀었는데, start와 end 인덱스, 순회방향을 변수로 R일땐 순회 방향만 바꾸고, D일땐 순회 방향에 맞는 맨 앞에있는 원소를 제거했다. 그외엔 어려운게 없었고 입출력은 C++이라 조금 귀찮은 작업이었다. 파이썬이라면 입출력이 조금 쉬웠을것이다. #include #include // stoi, to_string using namespa..

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 어제와 이어서 비트마스크를 사용한 동적 계획법을 공부했다. 문제만 보면 모든 조합 만들어서 최솟값을 찾으면 된다. 그러면 완전탐색이나 백트래킹을 사용해서 탐색을 하면 모든 조합을 찾을수있다. 하지만 N의 최댓값이 20이므로 20^20 이나 20!은 매우 큰 숫자이므로 다른 방법을 찾아야한다. 완전 탐색을 하다보면 항상 겹치는 부분이 생기게 되는데 이때의 값들을 저장하고 일반적인 값을..