Python
-
[Python] Programmers 자동완성알고리즘/문제풀이 2021. 8. 20. 22:41
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 2. 문제 요약 검색어 자동완성으로 단어 리스트에서 찾을 때 총 몇 글자까지 입력해야 하는지 리턴한다. 3. 아이디어 정리 트라이 구조 생성 word_num = 0 - 현재 문자를 포함하는 단어 수 children = defaultdict(TrieNode) - 자식 노드 (dict 자료형) 트라이 구조에 단어들 넣기 (아래 그럼..
-
[Python] Programmers 124 나라의 숫자알고리즘/문제풀이 2021. 8. 20. 22:37
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 2. 문제 요약 기존 3진법 012와 다르게 124 나라에서는 124만 사용 가능하다. 10진법을 124 나라 숫자로 변환한다. 3. 아이디어 정리 124 나라 규칙을 찾아서 구현을 아래와 같이하였다. 3으로 나누어 떨어지지 않는 경우 나머지를 리스트에 넣는다. 3으로 나눈 몫을 n에 넣는다. 3으로 나누어 떨어지는 경우 4를 넣는다. 3으로 나눈 몫을 n에 넣는다. 몫은 1 제거해준다. 4. 문제 풀이 4-1. 내 풀이 def solution(n): result = list() while n: if n % 3 != ..
-
[Python] 백준 16235 나무 재테크알고리즘/문제풀이 2021. 8. 20. 22:33
1. 문제 링크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 문제 요약 4계절에 맞게 구현을 하여 k 년이 지난 후 살아있는 나무 개수를 출력한다. 3. 아이디어 정리 나무 나이를 저장할 그래프를 새로 생성한다. - 3차원으로 저장 k 년 동안 4계절을 반복 진행한다. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한 칸에 여러 개 나무가 있다면 어린나무부터 여름: 죽은 나무 = (나이 // 2)로 현재 양분에 넣어준다...
-
[Python] 백준 21278 호석이 두 마리 치킨알고리즘/문제풀이 2021. 8. 20. 22:29
1. 문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 2. 문제 요약 모든 건물에서 가장 가까운 치킨집 2개를 고른다. 3. 아이디어 정리 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬 2개의 건물을 선택하여(예상 치킨집) 모든 집을 방문해서 걸리는 거리를 측정 현재까지 최소 거리이면 결과에 저장 4. 문제 풀이 4-1. 내 풀이 import sys n, m = map(int, s..
-
[Python] 백준 1956 운동알고리즘/문제풀이 2021. 8. 14. 20:17
1. 문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 2. 문제 요약 최소 사이클의 도로 길이의 합을 출력한다. 3. 아이디어 정리 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬 자기 자신 -> 자기 자신 마을로 돌아오는 거리 중 최솟값 구하기 참고 - 플로이드와샬 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜 점화식 각 단계마다 특정한 노드 k..
-
[Python] Programmers 로또의 최고 순위와 최저 순위알고리즘/문제풀이 2021. 8. 14. 20:13
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 2. 문제 요약 구매한 로또에 0이 표기되어 있고, 당첨 번호가 주어진다. 당첨 가능한 최고 순위와 최저 순위를 리턴한다. 3. 아이디어 정리 내 로또 번호를 한 개씩 for문을 돌린다. 0이 아닌 경우 win_nums(당첨번호)에 들어가는지 확인한다. 최저 순위 관련 변수에는 0의 개수 만큼 당첨 ..
-
[Python] 백준 17609 회문알고리즘/문제풀이 2021. 8. 14. 17:45
1. 문제 링크 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 2. 문제 요약 회문: 0 (앞뒤 동일) 유사회문: 1 (한 문자 삭제 시 앞뒤 동일) 둘 다 해당 안됨: 2 3. 아이디어 정리 투 포인터를 이용해서 회문을 검사한다. left right 문자가 동일한 경우: left + 1, right + 1 left right 다른 경우: 한 문자열 제거 후 회문 확인 오른쪽 문자열 제거한 경우 제거 후 회문이 되는지 확인 왼쪽 문자열 제거한 경우 제거 후 회문이되는지 확..
-
[Python] 백준 18513 샘터알고리즘/문제풀이 2021. 7. 31. 18:35
1. 문제 링크 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 2. 문제 요약 모든 집에 대한 불행도의 합의 최솟값 구하기 3. 아이디어 정리 샘터를 기준으로 불행도를 늘려주면서 bfs를 진행한다. 샘터를 기준으로 시작하기 위해 큐에 넣어준다. -1, + 1 위치 방향으로 bfs 진행 해당 집 위치를 큐에 넣기 - (집 위치, 현재 불행도 + 1) 4. 문제 풀이 4-1. 내 풀이 import sys from c..