알고리즘
[프로그래머스](Lv.3)길 찾기 게임[2019 KAKAO BLIND RECRUITMENT][파이썬/트리/전위순회/후위순회/Preorder/Postorder/Tree]
https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 길 찾기 게임 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 ..
[프로그래머스](Lv.3) 외벽점검 [2020 KAKAO BLIND RECRUITMENT][파이썬/Python/슬라이딩윈도우/원형큐]
https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 문제 설명 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한..
[백준/BOJ] #15961 #2535 회전초밥 [투포인터/슬라이딩윈도우/파이썬/Python]
https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 요..
[프로그래머스/알고리즘] 폰켓몬 [파이썬/해시]
https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 문제였다. 그런데 처음에 조합이랑 카운터를 사용했는데 시간초과가 났다. 보니까 set을 이용하면 반복문없이 길이 비교만 하면 됐다,, 시간초과 코드 from itertools import combinations from collections import Counter def solution(nums): answer = 0 take = int(len(nums)/2) for i in combin..
[알고리즘/프로그래머스] 숫자 문자열과 영단어 [파이썬/구현/문자열]
https://school.programmers.co.kr/learn/courses/30/lessons/81301 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2021 카카오 채용연계형 인턴쉽 기출문제. 쉬운 문제인데 내 풀이가 테케 몇개 실패해서 왜인지 싶다. 아직도 이유를 잘 모르겠다. 파이썬 풀이 1) 리스트 두 개와 zip 활용 def solution(s): hangul = ['zero','one', 'two','three','four', 'five', 'six', 'seven', 'eight', 'nine'] arab = [i for i in ..
[알고리즘/프로그래머스/카카오코테2021] 신규아이디추천 [문자열/파이썬/python]
https://school.programmers.co.kr/learn/courses/30/lessons/72410 카카오 블라인드 채용 기출 문제다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 신규 아이디 추천 문제 설명 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는..
[백준/BOJ]#4949:균형잡힌 세상[문자열/스택/파이썬/python]
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 내가 효율적으로 짠건지는 사실 잘 모르겠는데 내가 하는 코딩습관대로 체크플래그로 풀었다 left괄호는 플래그 1, 2 오류는 플래그 5 예제들이랑 반례들 다 통과하는데 20%쯤에서 통과가 안되서 30분정도를 애먹었는데 질문게시판에 있는 반례들이 한 6페이지까지도 다 잘 나와서 대체 뭐가 문제인지 개행문자가 문제인걸까 애를 먹고있었는데 딱 반례 '[([]])'가 no가 나와야하..
[알고리즘/프로그래머스] 더 맵게 [힙/heap/파이썬/python]
https://programmers.co.kr/learn/courses/30/lessons/42626# 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코..
[백준/BOJ]#13565:침투[DFS/그래프/깊이우선탐색/파이썬/python]
https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 메모리 초과의 늪에서 못 빠져나오게 한 문제,,, 대체 코드에 문제가 없는데 왜 이러는건가 재귀탐색제한을 줄여도 보고 30분을 헤매었는데,, 결국 컴파일러를 pypy3가 아닌 python3 으로 바꾸니 통과했다;;; 백준에서 이런 경우가 간혹 있는데 이럴때마다 시간이 아깝고 힘 빠진다^^;; 승부는 내야하니 정답은 내야겠고,, bfs보다는 dfs로 푸는 게 더 ..
[백준/BOJ]#2078:무한이진트리[트리/수학/파이썬/python]
https://www.acmicpc.net/problem/2078 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 트리 문제라고 명시되어있지만 사실상 수학 문제다!! #2078_무한이진트리 a,b=map(int,input().split()) l=0 r=0 while a>1 and b>1: if a>b: l+=a//b a%=b else: r+=b//a b%=a l+=a-1 r+=b-1 print(l,r)
[백준/BOJ]#1406:에디터[스택/파이썬/python]
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 처음에 보고 문자열로 파싱하는게 가장 빠르다고 판단해서 풀었는데 시간초과가 떴다. 시간초과 코드 #1406_에디터 s=str(input()) num=int(input()) cursor=len(s) for _ in range(num): ctrl=list(map(str,input().split())) if cursor
[백준/BOJ]#15805:트리 나라 관광 가이드[트리/파이썬/python]
https://www.acmicpc.net/problem/15805 15805번: 트리 나라 관광 가이드 윤호는 K개의 도시들이 트리 형태로 연결되어 있는 트리 나라의 관광 가이드이다. 윤호가 새롭게 맡게 된 패키지는 트리 나라의 루트 도시에서 시작해서 모든 도시를 순회하고 오는 상품이다. www.acmicpc.net 파이썬 코드 #15805_트리나라관광가이드 from collections import Counter n=int(input()) city=list(map(int,input().split())) cntcity=Counter(city) visited=[0 for _ in range(len(cntcity.keys()))] parent=[0 for _ in range(len(cntcity.keys(..
[백준/BOJ]#9935:문자열 폭발[문자열/스택/파이썬/python]
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 처음에 보고 단순히 문자열 sequential search로 풀으니 시간초과가 났다! 역시 골드문제는 한큐에 풀리지 않지 분류를 보니 스택인 걸 보고 스택으로 바꾸었는데 또 시간초과! 반복문을 하나 줄이려면 뒤에서부터 탐색하면 된다는 걸 깨달았다. 그리고 마지막 res join문을 반복문안에서 하고 앉아있었다는 걸 깨닫구 코드를 수정하니 맞았다. 시간초과 코드(단순 순차탐색) #99..
[백준/BOJ]#2263:트리의 순회 [트리/분할정복/파이썬/python]
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 인오더와 포스트오더 (inorder, postorder)를 입력으로 받으면 preorder(프리오더)를 출력해주는 문제다. 트리의 순회방법_ 전위, 중위, 후위 순회 방식이다. 위의 트리 예시들을 읽어보면 대략적으로 그림이 그려진다. Preorder는 맨처음에 루트(부모)가 들어오고, postorder는 맨마지막에 들어온다. 이를 이용하여 처음에 루트를 구한다. Inorder는 왼쪽부터 쭉 순서대로 순회한다는 것을 알 수 ..
07 분할정복
시간복잡도:fastsum()과 recursivesum()이 종료하는 데 걸리는 시간은 함수 호출 횟수에 비례. 즉, recursivesum()은 n번의 함수호출fastsum()은 호출될때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.따라서 두 값의 상한은 모두 logn이므로 O(logn)! 부적절한 경우) 절반으로 나누는 알고리즘이 큰 효율 저하 불러오는 이유:여러 번 중복되어 계산되면서 시간 소모 (=overlapping subproblems)(→ 이런 경우는 8장 동적계획법으로 해결) 대표적 예제) 병합 정렬 Merge SortMerge Sort (평균/최악:O(nlogn) 7.2 문제: 쿼드 트리 뒤집기(QUADTREE, 하)algospot.com :: QUADTREE쿼드 트리 뒤집기 문..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python/C++]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ]#1629:곱셈 [분할정복/수학/파이썬/python]
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복 divide n conquer 과 수학 문제다. 수학의 분배법칙을 분할정복에 적용하여 재귀로 풀어나가면 된다. 호기심에 재귀 호출 순서가 궁금해서 프린트문을 여러번 찍어보았는데 마지막 홀수인 경우, ..(10^1)%12 x 10) %12 x 10이 마지막으로 호출된다. 그러므로 12로 다 나누면 남는 건 10 * 10 숫자만 남아서 결론적으론 답이 4가 나온다. #1629_곱셈 a,b,c=map(int,input().split()) ''' 수학의 분배법..
[백준/BOJ]#1780: 종이의 개수 [분할정복/재귀/파이썬/python]
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복과 재귀를 이용하여 푸는 문제다. dfs bfs가 생각났는데 분류가 분할정복으로 되어있고 9개로 종이개수가 정해져있으므로 for문으로 돌리고 재귀를 해서 체크하면 된다. #1780_종이의개수_dividenconquer n=int(input()) paper = [list(map(int,input().split())) for _ in range(n)] res1=0 res0=0 res..
[백준/BOJ]#17413: 단어 뒤집기 2 [문자열/파이썬/python]
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 쉬운 문제라고 생각하고 후딱 풀려고 했는데.. 스톤헤드..!!! 은근히 오래 걸렸다.... delimiter(bracket) 기준으로 처음에 인덱스를 기준으로 뽑아내다가 리스트와 char 데이터타입의 충돌로 또 애먹다가.. 뒤엎고 다시 짜고.. 하다가 완성했다 결국. bracket안에서만 문자열이 뒤집히지 않으므로 신경써주고 나머지는 플래그를 두어서 그외의 경우에 ..