전체 글(17)
-
[LeetCode] 1209. Remove All Adjacent Duplicates in String II
코드없는 프로그래밍 채널의 해설을 참고해서 풀었고, 같은 문자가 k번 반복될 때마다 k번 pop을 해주는 방식으로 풀었다. 1. 문자열을 저장할 스택과 얼마나 반복됐는지 체크할 숫자스택을 만든다. 2. 문자열 스택의 마지막을 제시된 문자열과 비교해 같은지 파악한다. 3. 같으면 추가하고 숫자스택의 값도 1올려준다. => 숫자스택의 값을 체크해 k와 같으면 k만큼 pop을 해준다. 4. 같지 않으면 문자스택에 추가하고, 숫자스택에 1을 추가한다. 처음에 문제를 읽고 처음 문자열 스택에서 pop을 하고 나면 변형된 스택에서 새로 겹치게 되는 것을 찾지 못하는 것이 아닌가 생각해 보니 새로 비교하는 문자를 이어서 숫자 스택에 더해주기 때문에 찾을 수 있다는 것을 알게 되었다. st = [] nt = [] fo..
2022.05.02 -
[틀린문제찾기] 미로찾기
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..
2022.04.23 -
[백준] 1931. 회의실 배정
그리디를 사용하는 문제를 파악하기 위해 여러 블로그들을 참고했고, 아래의 블로그에서 풀이방법을 참고했다. 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 그리디를 사용할 수 있냐 없냐 하는 것을 직관적으로 알 수 있는 문제도 있지만 어려운 문제를 보면 그리디로 할 수 있을 것 같은데 반례는 없을까? 이게 최적해를 내놓는다는 보장이 있을까? 하는 생각이 들었을 때 이게 그리디 풀이의 해를 보장하는지에 대한 명확한 증명을 하기는 생각보다 까다롭다. 그리디로 풀 수 있는지 어느 정도 알 수 있는 방법을 소개하는 블로그가 있는데, 현재 지식 수준으로..
2022.04.22 -
[Bolt Into Scripts] 캐주얼 디펜스(2)
https://github.com/Sanghun2/Bolt-Into-Scripts-CasualDefense GitHub - Sanghun2/Bolt-Into-Scripts-CasualDefense: 볼트로 작성된 캐주얼 디펜스게임을 보고 스크립트로 바 볼트로 작성된 캐주얼 디펜스게임을 보고 스크립트로 바꿔서 구현한 버전. Contribute to Sanghun2/Bolt-Into-Scripts-CasualDefense development by creating an account on GitHub. github.com 오늘은 카메라 이동 작업을 했습니다. 카메라를 직접 이동 시키는 것은 CameraManager.cs에서 작업했고, 카메라 이동과 별개로 패럴렉스는 BackgroundScroller.cs라는..
2022.04.19 -
[백준] 3036. 링
https://www.acmicpc.net/problem/3036 첫번째 원이 돌아갈 때 다른 원들은 몇 번을 도는지를 계산해 출력하는 문제다. 1. 일단 첫번째로 원이 회전하는 것은 원의 둘레에 따라 달라지고 원의 둘레를 구하는 식은 2ㅠr인데 2ㅠ는 약분되어 사라지므로 영향을 미치는 요소는 r만 남게 된다. 따라서 원의 반지름의 길이가 곧 얼마나 회전하는지를 결정하는 요소이므로 원의 반지름 길이의 비율을 출력하면 된다. 2. 출력할 비율을 기약분수 형태로 나타내려면 어떻게 해야 할 지 생각해보았다. 기약분수는 더 이상 공통된 수로 나눠지지 않는 수이므로 가장 큰 공통약수로 나눈면 더 이상 나눠지지 않을거라는 생각을 했고, 가장 큰 약수를 구하는 개념은 최대공약수이다. 3. 따라서 원들의 반지름을 첫번..
2022.04.18 -
[백준] 2606. 바이러스
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..
2022.04.15