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

0,1,2로 된 배열을 작은 순으로 정렬을 하는데 라이브러리를 사용하지 않고 해결하는 것이다. 물론 라이브러리를 사용해도 문제 해결은 가능하지만 이는 정렬에 대한 내용을 이해하고 있는지 점검하기 위한 것이 목표인 문제인 것 같다. 일반적으로는 스왑을 하는 sort알고리즘으로 풀면되고 nlogn의 복잡도를 가지는 알고리즘을 사용해도 좋다. 하지만 nlogn의 복잡도를 가지는 알고리즘은 구현하기에 너무 까다롭고 일반적인 알고리즘은 O(n^2)이라서 효율이 좋지 않다. 이번에는 O(n)의 복잡도로 풀어보라는 미션을 주셔서 O(n)이 되도록 풀어보았다. class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything..

코드없는 프로그래밍 채널의 해설을 참고해서 풀었고, 같은 문자가 k번 반복될 때마다 k번 pop을 해주는 방식으로 풀었다. 1. 문자열을 저장할 스택과 얼마나 반복됐는지 체크할 숫자스택을 만든다. 2. 문자열 스택의 마지막을 제시된 문자열과 비교해 같은지 파악한다. 3. 같으면 추가하고 숫자스택의 값도 1올려준다. => 숫자스택의 값을 체크해 k와 같으면 k만큼 pop을 해준다. 4. 같지 않으면 문자스택에 추가하고, 숫자스택에 1을 추가한다. 처음에 문제를 읽고 처음 문자열 스택에서 pop을 하고 나면 변형된 스택에서 새로 겹치게 되는 것을 찾지 못하는 것이 아닌가 생각해 보니 새로 비교하는 문자를 이어서 숫자 스택에 더해주기 때문에 찾을 수 있다는 것을 알게 되었다. st = [] nt = [] fo..

from collections import deque import math from sys import stdin n,m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) #이동할 벡터(상,하,좌,우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) while q: x, y = q.popleft() #4방향을 체크 for i in range(4): nx = x + dx[i] ny = y + dy[i] #해당되지 않는 범위 체크 if 0 = m: continue if graph[nx][ny..

그리디를 사용하는 문제를 파악하기 위해 여러 블로그들을 참고했고, 아래의 블로그에서 풀이방법을 참고했다. 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. 따라서 원들의 반지름을 첫번..