링크: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어1 (시간초과) 일단 단순하게 b번 반복하며 a 곱하기 파이썬은 자동으로 동적할당이 되어 너무 큰 수가 나오면 메모리초과가 나올 수 있음 a를 곱하고 c로 바로바로 나눠주며 메모리초과 방지 import sys input= sys.stdin.readline a, b, c = map(int, input().split()) for i in range(b): a *= a a %= c print(a) 단순히 반복하는 로직은 답이 아닌듯 하다. 아이디어 2 ..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 words에 target단어가 없는 경우 0 반환 첫 bfs를 시작할 시작 노드 찾기( begin에서 갈 수 있는 문자들) for문을 이용해 1번 조건을 만족하는 단어를 찾음 위와 같은 방식으로 그래프를 만들어 BFS를 진행 방문처리를 깊이 표현과 동시에 진행 target노드가 나오면 현재 노드의 깊이 출력 자료구조 Queue(BFS) 방문: int ..
링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 익은 토마토(1)의 좌표들를 q에 넣고 bfs 숨바꼭질과 동일하게 방문처리와 깊이 저장을 동시에 진행 (이건 토마토 배열 안에서 해도 될듯) 상하좌우 확인 0이면 1로 변경 후 큐에 넣기, 1이면 무시, -1이어도 무시 모든 토마토가 익었는지와 며칠이 걸렸는지는 배열을 돌며 확인 0인 부분이 있으면 -1출력 자료구조 토마토: int[][] Queue(BFS) 코드구..
링크: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 수빈이의 시작점을 시작으로 bfs x-1, x+1, 2*x 이 3가지 방향으로 이어지는 그래프로 생각 방문했던 수는 방문처리를 해주어 탐색하지 않기 몇번째 층인지 확인은 방문 처리와 동시에 이루어짐 전 요소의 방문 인덱스에 +1한 값을 현재 요소의 방문 인덱스에 저장 동생의 위치에 도착하는 경우가 발생하면 그 요소의 층을 따로 저장 다음 층 탐..
링크: https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 아이디어 2중 for문 => 값이1 && 방문x => BFS / 그림개수 +1 BFS 돌면서 방문처리 / 그림 넓이 최대값 갱신 시간복잡도 BFS의 시간복잡도 => O(E+V) E+V = (m*n) + (4*E) (V는 넉넉하게 잡아줌) 5*500*500 = 125만 가능! 자료구조 그래프 전체 지도: int[][] 방문 : bool[][] Queue(BFS) 코드 구현 import sys in..
링크: https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 +기를 기준으로 리스트를 나눠서 계산해보면 쉽게 풀리지 않을까? 스택을 이용해 문자열을 돌며 올바르게 입력된 괄호인지 판단하자 돌다가 스택의 크기가 0되기 전에는 곱하기 0이 되면 곱한 것들을 따로 result와 더하고 result에 저장 다시 계속 반복 모든 문자열을 돌았으면 result가 답? 위의 구조로 코드를 짜봄 import sys input = sys.stdin.rea..
