링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여www.acmicpc.net아이디어바로 보자마자 bfs로도 풀 수 있을 것 같음근데 dfs를 연습하기 위해 dfs를 사용2중 for문을 통해 방문처리를 확인하고 dfs진행dfs는 재귀를 사용각 영역마다 each변수로 크기 표현구현import sys input = sys.stdin.readline n = int(input()) danzi = [list(map(int, input().strip())) for _ in range..
링크: https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 아이디어 배열이 그렇게 크지 않아 적록색약인 경우와 아닌 경우 두 번 bfs를 해도 될 것 같음 방문처리 배열도 만들어서 bfs 진행해보자 첫 bfs함수는 색깔을 인자로 같이 넣어주어 같은 색상끼리 묶어주기 두 번째 bfs함수는 R,G를 같은 색상으로 인식하게 해주면 될듯 (조건문) 두번째 함수 돌릴 때는 방문처리 배열을 재활용하자 1이 방문이 되지 않은 것으로 인지 코드 impor..
링크: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 아이디어 dp 배열 2개를 만들어 각 지점에서 우측 좌측 '가장 긴 증가하는 수열' 문제에서 사용한 점화식을 적용 두 dp배열을 모두 만들어준 후 합쳐주어 바이토닉 부분 수열의 길이를 구함 구현 import sys input = sys.stdin.readline n = int(input()) s = list(map(int, input().split())) dp_left = [1]*n dp_right = [1]..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 operations의 각 요소를 split() 처리해주어 삽입과 삭제를 판단. heapq를 활용하여 삽입은 자동처리 -1, 1 확인 후 최솟값 최댓값 둘 중 뭘 뺄지 판단 코드(틀림) import heapq def solution(operations): heap = [] for i in operations: # 삽입 삭제 분리 a, b = i.split() # 삽입은 heapq를 ..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr아이디어triangle배열을 dp 배열로 재사용해도 문제가 없어 보인다.각 노드에 갈 수 있는 최대 값을 triangle테이블에 덮어쓰기 점화식: triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]) dp의 가장 깊은 층의 최댓값을 반환 -> max 두 번 쓰면 될 듯?코드def solution(triangle): # 양 사이드는 미리 구한다..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 2중 for문을 돌리는데 i, j를 비교하여 큰 수를 1차원 배열에 append 하는 방식으로 하면 1,2,3 과정을 한 번에 할 수 있을 듯 이후 슬라이스를 하여 result를 반환한다. 코드(시간초과) def solution(n, left, right): tmp = [] # 수 채움과 동시에 1차원 배열로 표현 for i in range(n): for j in range(n):..
링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 아이디어 가로 새로 크기만큼 배열 생성 입력된 좌표를 1로 변경 이중 for문을 돌며 1인 좌표에서 bfs 탐색 진행 탐색을 마친 좌표는 0으로 변경 from collections import deque import sys input = sys.stdin.readline dx = [0,0,1,-1] dy = [1,-1,0,0] t = int(input()) def bfs(graph, a, b): que..
링크: https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 아이디어 첫째날 둘째날을 a, b로 두고 D와 K를 가지고 점화식을 만들어 보자 예) D가 4면 a, b, a+b, a+2b, 2a+3b, 3a+5b=> K=a+2b DP배열을 2차원배열로 만들어 a에 곱해지는 값과 b의 곱해지는 값을 저장함 구현 D, K = map(int, input().split()) d = [0] * 31 d[1] = (1,0) # 첫째날 1a + b d[2..
링크:https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 당장 예시만 봐도 1~5까지 더하고 4~6 이런게 순서대로 더해보고있다. 단순 반복문 하나만 돌며 tmp에 1식 증가한 수를 더하며 n이 될 때마다 answer에 +1, tmp를 초기화 하는 방식을 써보자 조건에 반복문을 돌다 tmp가 n보다 커지면 더이상 조사할 이유가 없으니 break 구현 def solution(n): answer = 0 for i in range(1, n+1)..
