본문 바로가기

코딩테스트

 (46)
[Python] DFS 문제 풀이 정리 DFS 정복하기. 물론 이분탐색이나 BFS도 있지만 내가 느끼기에 상대적으로 많이 보이는 건 DFS이다. 그래서 DFS를 중심으로 문제 연습! https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys sys.setrecursionlimit(100000) input=sys.stdin.readline n = int(input()) # 2차원 행/열 # visited= [[False]*(n) for _ in range(n)] maxNum = 0 ..
[Python] 그리디 # 1. 그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지가 최종적으로 최선이라고 가정하는 알고리즘. 수행과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 처음으로 돌아가 같은 과정을 반복한다. DP보다 구현이 쉽고 시간복잡도가 우수하다. 그러나 항상 최적의 해를 보장하지 못하므로 논리 유무를 살피는 것이 중요한 문제. https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤..
[Python] 프로그래머스 - 정수를 나선형으로 배치하기 갑자기 난이도가 확 올라가네... https://school.programmers.co.kr/learn/courses/30/lessons/181832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 구현 def solution(n): answer = [[0]*n for _ in range(n)] #우,하,좌,상 -> 나선형으로 해야 하므로 dx=[0,1,0,-1] dy=[1,0,-1,0] x,y=0,0 answer[x][y]=1 # 처음 시작 1로 초기화 k=2 while k=n or ny>=n or nx
[Python] 프로그래머스 - 안전지대 0단계 문제를 푸는데 꽤 어려운 문제가 나왔다! https://school.programmers.co.kr/learn/courses/30/lessons/120866 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 내 풀이 def solution(board): answer = 0 dx = [-1, 1, 0 , 0, 1, 1, -1, -1] dy = [0, 0, -1, 1, -1, 1, 1, -1] for i in range(len(board)): for j in range(len(board)): if board[i][j]==1: for k in range..
[Python] ECC 3주차 정리 - 탐색 # 1. 깊이 우선 탐색(DFS) 그래프 완전 탐색 기법 중 하나. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동한다. 재귀 함수로 구현하며 스택 자료구조를 이용한다. 재귀 함수를 이용하는 경우 스택 오버플로에 유의해야 한다. 시간복잡도는 O(V+E). (V: 노드 수, E: 에지 수) DFS에서는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 리스트가 필요하다.(인접 리스트) 또한 DFS의 탐색 방식은 후입선출 특성을 가져 스택을 사용한다. 스택의 성질을 갖는 재귀 함수로 많이 구현한다 DFS 핵심 이론 DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화 한다. DFS를 위해 초기에 인접 리스트로 그래프 표..
[Python] ECC 2주차 정리 - 정렬 # 1. 버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 O(n^2)의 시간 복잡도로 다른 정렬 알고리즘보다 느린 편이다. https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net N = int(input()) A = [0]*N for i in range(N): A[i] = int(input()) for i in range(N-1): for j in range(N-1-i): if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A..
[Python] ECC 1주차 정리 - 자료구조 # 1. 배열과 리스트 배열이란? 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조. 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 특정 인덱스의 값을 삽입/삭제하거나 새로운 값을 삽입하기 어렵다. 한번 선언하면 크기를 조절할 수 없다. 리스트란? 값과 포이터를 묶은 노드를 포인터로 연결한 자료구조. 인덱스가 없어 접근 속도가 느리지만, 데이터의 삭제/삽입 속도는 빠르다. 크기가 정해져 있지 않다. 다만 포인터를 저장할 공간이 필요하여 구조가 배열보다 복잡하다. 파이썬의 배열은 리스트의 특징과 배열 모두 가진다. https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 ..
[Python] 2024-1 이퍼 준비(2) # 난이도  1.문자열 압축https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr# 정답 풀이#들여쓰기에 주의하세요def get_shortened_length(target, unit_length): length = len(target) new_length = length prev_substr = "" # 기준 문자열 count = 1 # 반복 횟수 # 부분 문자열 인덱스 [left, right) left = 0 ri..

티스토리툴바