[문제] https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 가까운 같은 단어를 이었을 때 이은 선이 겹치지 않는 문자인지를 체크하는 문제. [풀이컨셉] 문자를 이은 선이 겹치지 않으려면 가까운 문자끼리 대칭성을 가져야 한다. 대칭성이 없이 번갈아 나올 경우 첫번째 그림처럼 꼬이게 되고 다른 문자가 등장하더라도 가까운 문자끼리 대칭성을 이루면 두번째 그림처럼 선을 꼬이지 않게 그릴 수 있다. 따라서, 스택을 통해 문자를 저장하고 비교하는 문자가 스택의 마지막..

그리디를 사용하는 문제를 파악하기 위해 여러 블로그들을 참고했고, 아래의 블로그에서 풀이방법을 참고했다. https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 그리디를 사용할 수 있냐 없냐 하는 것을 직관적으로 알 수 있는 문제도 있지만 어려운 문제를 보면 그리디로 할 수 있을 것 같은데 반례는 없을까? 이게 최적해를 내놓는다는 보장이 있을까? 하는 생각이 들었을 때 이게 그리디 풀이의 해를 보장하는지에 대한 명확한 증명을 하기는 생각보다 까다롭다. 그리디로 풀 수 있는지 어느 정도 알 수 있는 방법을 소개하는 블로그가 있는데, 현재 지식 수준으로..

https://www.acmicpc.net/problem/3036 첫번째 원이 돌아갈 때 다른 원들은 몇 번을 도는지를 계산해 출력하는 문제다. 1. 일단 첫번째로 원이 회전하는 것은 원의 둘레에 따라 달라지고 원의 둘레를 구하는 식은 2ㅠr인데 2ㅠ는 약분되어 사라지므로 영향을 미치는 요소는 r만 남게 된다. 따라서 원의 반지름의 길이가 곧 얼마나 회전하는지를 결정하는 요소이므로 원의 반지름 길이의 비율을 출력하면 된다. 2. 출력할 비율을 기약분수 형태로 나타내려면 어떻게 해야 할 지 생각해보았다. 기약분수는 더 이상 공통된 수로 나눠지지 않는 수이므로 가장 큰 공통약수로 나눈면 더 이상 나눠지지 않을거라는 생각을 했고, 가장 큰 약수를 구하는 개념은 최대공약수이다. 3. 따라서 원들의 반지름을 첫번..

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터의 수를 구하는 문제로 다시 해석하면 1번과 직, 간접적으로 연결된 컴퓨터를 탐색해 그 수를 출력하는 문제다. bfs, dfs 중 아무거나 사용해도 되겠지만 이번에는 bfs를 사용했다. from collections import deque from sys import stdin def bfs(start_node): global count q = deque() q.append(start_node) visited[start_node] = True while q: v = q.popleft() for n in graph[v]: if not visited[n]: q.append(n) visited[n] = True count += 1 num_of_com = int(std..

from sys import stdin n = int(input()) concentList = [] for i in range(n): concentList.append(int(stdin.readline().rstrip())); print(sum(concentList) - (n-1)) 34908 kb 284 ms 개선된 코드 (메모리 16%증가, 처리속도 50%감소) from sys import stdin n = int(input()) concentList = list(map(int,stdin.read().split())) print(sum(concentList) - (n-1)) 40468 kb 132 ms 추측할 수 있는 내용 1. for문이나 append를 했을 때 처리하는 속도가 늘어난다. 2. ma..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 개요 이번 내용은 dfs, bfs이다. 풀이 코드 from collections import deque import queue import sys input = sys.stdin.readline def bfs(v): global bfsAnswer bVisited[v] = True bfsAnswer += f"{v} " queue = deque() queue.ap..