분류 전체보기

[python] 백준 - 11660. 구간 합 구하기 5

🤔문제 해결 S1 | DP (0,0) 부터 리스트의 모든 지점까지 각각의 합을 구한다. 2번을 수행하고 나면 아래와 같은 결과를 얻을 수 있다. 합을 누적한 리스트로 아래 그림처럼 구하고자 하는 영역을 구하고 필요없는 부분은 빼주면 된다. 여기서 많이 헷갈릴 수 있는데 문제는 1,1부터 시작하지만 우리는 0,0부터 시작한다. 또, 빼줘야하는 영역(빨간색) 부분은 두번 빼는 경우가 있기 때문에 다시 더해줄 영역(초록색)을 한번 더해준다. 여기서 끝이 아니다. x축이 처음부터 인경우와 y축이 처음부터인 경우, 둘 다 아닌경우 이 3가지 경우로 나눠서 풀어줘야한다. 💨 시간초과 때문에 힘들었던 문제... 💻소스 코드 import sys from itertools import accumulate # 누적 합을 ..

[html] 공백 문자, 띄어쓰기

공백문자 가져가세요 "ㅤ" 🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻 ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ 🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺 ㅤ ㅤ ㅤ

[python] 프로그래머스 - 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv3 설치된 구조물의 정보를 리스트에 쌓는다. ex) 설치된_리스트: [(좌표, 좌표, 구조물), ..., (좌표, 좌표, 구조물)] | x,y,(기둥or보) 이 설치된 구조물 리스트를 for문을 돌며 이 구조물들의 설치가 조건에 맞는 지 체크한다. def check() 구조물 설치일 경우 일단 설치한다. 큰 3번을 체크한다. 구조물들이 조건에 맞지 않으면 추가한 것을 삭제한다. 구조물 삭제일 경우 일다 삭제한다. 3번을 체크한다. 구조물들이 조건에 맞지 않으면 삭제한 것을 추가한다. 잘 정렬해서 답을 출력한다.!!!!! 💨 여기서 set() 을쓰는 이유는 if a in list: 같은 경우 때문. 리스트로 탐색하는 경우는 O(n) 이지만 셋으로 탐색하는 경우는 O(1) 이다. 마지막에 답..

[python] 프로그래머스 - 문자열 압축(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv2 2. 리스트를 만들어 문자열을 1개, 2개, ... , n/2개 까지 쪼갰다. 문자열이 abcabcabcabcdededededede 라면 [['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', ''], ['ab', 'ca', 'bc', 'ab', 'ca', 'bc', 'de', 'de', 'de', 'de', 'de', 'de', ''], ['abc', 'abc', 'abc', 'abc', 'ded', 'ede', 'ded', 'ede', ''], ['abca', 'bcab', 'cabc', 'dede', 'dede',..

[python] SWEA - 1389. 케빈 베이컨의 6단계 법칙

🤔문제 해결 1. S1 | 그래프 이론, 그래프 탐색, 너비 우선 탐색, 플로이드-와샬(?) 2. 인접리스트를 만든다! 3. 베이컨수와 그 때의 사람을 저장할 변수 생성 4. 한사람씩 모두 BFS 탐색 5. visited에 저장된 숫를 모두 합치면 베이컨 수가 나온다. 6. 비교를 통해 가장 작은 베이컨수를 가진 사람을 답으로 출력한다. 💨 제목만 보고 어려운 문제인줄 알았는데 BFS를 모두 돌아주면 해결된다. 💻소스 코드 import sys from _collections import deque N, M = map(int, input().split()) # 인접 리스트 생성 adj = {x + 1: [] for x in range(N)} for i in range(M): s, e = map(int, s..

[python] 백준 - 1074. Z

🤔문제 해결 1. 재귀,분할정복 | S1 2. 모두 쪼개려고 하는경우 메모리초과 혹은 시간초과가 발생한다. 3. 내가 찾고자하는 행과 열이 포함된 박스만 찾아서 재귀함수를 실행시킨다. 4. 여기서 각 박스의 첫 숫자를 구한다. (1) 예를 들어 사이즈가 8인 박스의 첫숫자는 0이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 박스를 쪼개면 (2) 각 박스의 첫 숫자는 0, 16, 32, 46 이다. (3) 왼쪽 위 박스는 그대로, 오른쪽 위 박스는 첫숫자에 (size//2)**2*1 값을 더해준다. (4) 왼쪽 아래 박스는 첫숫자에 (size//2)**2*2 값을, 오른쪽 아래 박스는 첫숫자에 (size//2)**2*3 값을 더해준다. 5. 박스의 크기가 2가 되면 찾고자 하는 행과 열을 찾..