Algorithm

[프로그래머스] 표현 가능한 이진트리 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150367. 표현 가능한 이진트리 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선 예시를 한번 쭉 나열해 보며 감을 잡자. depth..? height..? 가 1일 때는, 0, 1만이 표현 가능하다. height = 2이면, 1, 3번째 숫자 중 1이 있다면 2번째 숫자는 무조건 1이여야 하므로, 111, 110, 011, 010, (000)의 4(5)가지의 ..

[프로그래머스] 택배 배달과 수거하기 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150369. 택배 배달과 수거하기 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 읽고 나서의 초견은, Greedy하게 접근하면 되지 않을까? 였다. 제일 먼 곳에서부터 배달/수거를 cap만큼 꽉꽉 채워서 왔다갔다 하는 식으로.. 일단 구현해보자. 조금 유의하며 코드를 작성했던 부분은, deliveries나 pickups 배열에서 값이 존재하는(0이 아닌) 가..

코딩 테스트를 위한 파이썬 문법(스킬) 총정리 - ver. 1.0.1 (230424)

기본적으로 쉽게 알 수 있는 기본 연산자라던가, 다른 언어와 크게 다르지 않은 부분들은 모두 제외하고, 실제로 코드를 짧게 줄이거나, 더 편하게 문제를 풀 수 있는 스킬들만 모았습니다. 1. 기본 입출력 1-1. input() input() 은 입력받는 한 줄을 모두 문자열(str)로 취급하여 입력받음. 그래서 입력받은 후 캐스팅을 통해 원하는 타입으로 바꿀 필요가 있음. a = input()# 3 입력 b = int(input())# 3 입력 a => (str) 3 b => (int) 3 1-2. 여러 개 나누어 입력받기 1 2 3 a, b, c = map(int, input().split()) 이러면 a=1, b=2, c=3 으로 잘 담긴다. map(function, iterable) 에서 fucti..

[백준] 1987. 알파벳 - python

[Gold IV] https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 1 이건 그냥.. DFS, Backtracking 이용해서 Recursion으로 풀면 되겠다- 라고 간단하게 생각했다. 그런데 가볍게 짠 코드에서 TLE. import sys sys.setrecursionlimit(100000) R, C = map(int, input().split()) board = [list(input()) for _ in range(R)] res..

[백준] 1647. 도시 분할 계획 - python

[Gold IV] https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 문제를 딱 보고서 생각한 것 -> Minimum Spanning Tree구나. MST를 구현하고 나서, 남은 edge들 중 가장 value가 높은 것을 제거하면 될 것 같다. line 13의 = 를 ==로 오타내서 찾는데 시간 좀 씀...ㅎ 아무튼 clear. from collections import deque N, M = map(in..

[백준] 12100. 2048 (Easy) - 파이썬

[Gold II] https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 유명한 2048 게임을 구현하는 문제였다.. 일단 보드의 크기도 최대 1 0: row[j] = row[j-1] j -= 1 row[0] = 0 temp = 0 # 합쳐져서 한 칸 당겼다면 다시 그 index부터 검사 index += 1 else: temp = row[index] index -= 1 return board def up(board):..

[백준] 11049. 행렬 곱셈 순서 - 파이썬

[Gold III] https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 [백준] 10942. 팰린드롬? - 파이썬 [백준] 9252. LCS 2 - 파이썬 [백준] 7579. 앱 - 파이썬 최근 풀었던 위 3개의 DP 문제와 크게 다를 것이 없었던 문제. 근데 DP는 DP인 걸 알아도.. 문제마다 다른 상황에 맞춰서 풀이를 생각해내기 쉽진 않음. 그리고 Line 28의 i += 1 이거 하나 빼먹어서 30분동안 찾았다.........

[백준] 10942. 팰린드롬? - 파이썬

[Gold IV] https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 일단 기본적으로, Palindrome 문제에서 쉽게 생각할 수 있는 풀이라 하면 Stack을 이용한 검증. 하지만, Stack을 이용한다면 Time Complexity가 저 하늘 멀리 날아가 버릴 것이 분명해~ 그렇다면 DP를 이용해서 모든 경우를 이차원 배열에 저장하는 식으로.. 0-1 Knapsack이나, LCS 문제처럼 저장해 놓고 풀이하는 식이 맞겠다. 풀이 설명은 주석으로. 참고로 sys.stdin.re..