기록하는 개발자

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다. 경주로의 출발점은 (0, 0) 칸(좌..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 설명 0,0 에서부터 내려와 m, n까지 도착하는 경로의 개수를 찾는 것이 문제이다. 다음번 이동할 칸은 현재 칸의 값보다 작아야 이동할 수 있다. bfs를 돌면서 상하좌우를 체크해주면 되는데, 한번 방문한 좌표는 다시 방문할 수 있는 것이 특징이다. 한번 방문한 좌표는 다시 상하좌우를 체크해줄 필요가 없다. 그러므로 이전 경로까지 가는 경우의 수를 더해주기만 하면 된다. 이 문제에서의 중..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 이 문제의 핵심은 가지고 있는 추를 이용해서 확인할 수 있는 추의 무게를 모두 찾아내서 원하는 추의 무게가 있는지 없는지 확인하면 된다. 다이나믹 프로그래밍으로 분류되어있는 문제이지만 수의 제한(추의 개수는 최대 30개)이 크지 않기 때문에 완전탐색으로도 해결할 수 있다. 만약 추가 1이 있다고 하자. 무게 4인 추가 새로 추가된다고 하면 무게 1인 추와 무게 4인 추를 이용하여 확인할 수 있는 무..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 해결 방법 처음 접근한 방법은 dp를 이용해서 풀어보려고 했습니다. 첫번째 사각형을 첫번째 원소로 놓고 진행하며 현재 사각형 높이가 이전 사각형 높이보가 증가한 경우, 감소한 경우, 증감의 크기가 1인 경우와 아닌 경우로 나눠서 머리를 싸매면서 풀었는데 결국 해결을 못했습니다 ㅜㅜ 반례에 늪에 빠지고 말았습니다..... 그래서 풀이를 참조하..

짐 싸기 문제(가방에 물건을 담는 케이스)는 동적 계획법으로 해결할 수 있는 경우가 많습니다. 여러 물건이 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제입니다. 대표적인 문제로는 백준 12865 평범한 배낭 문제가 있습니다. 물건의 무게(W)와 가치(V)가 주어지고, 담을 수 있는 배낭의 최대 무게가 주어집니다. 이 때 베낭에 넣을 수 있는 물건들의 최대 가치를 구하는 문제입니다. 해당 냅색문제에서는 물건을 쪼갤 수 없다고 가정합니다. 해당 문제에서 물건의 개수가 N = 4개이고, 베낭의 최대 용량은 K = 7입니다. 1번째 물건 2번째 물건 3번째 물건 4번째 물건 W(무게) 6 4 3 5 V(가치) 13 8 6 12 dp[i][j] = 첫 번째 물건부터 i번째 물건까지 살펴봤을 때, 베낭의 용..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. N은 최대 1,000,000 까지 이고 파이썬은 1.5초까지 시간초과 나지 않습니다. 그러므로 O(N) 시간내에 해결해야합니다. N의 개수만큼 dp 리스트를 만들고 0으로 초기화시킵니다. 1일때는 0, 2일때는 1, 3..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 일반적인 백트래킹을 이용한 스도쿠문제이다. 1 ~ 9 사이의 숫자를 넣어보고 3x3, 가로, 세로 조건을 충족하면 다음 숫자를 넣고, 충족하지 않으면 이전의 조건으로 되돌리면 된다. 시간초과 풀이 import sys input = sys.stdin.readline sdoku = [] for _ in range(9): row = list(map(int, input().split())) sdoku.a..

https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 ..

카운팅 정렬(Counting Sort)는 각 항목의 개수를 세어 저장해 두고, 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘 입니다. 오름, 내림차순 정렬과정, 시간 복잡도, 특징등에 대해서 알아보겠습니다 ! 카운팅 정렬이란? 정렬하고 싶은 배열 항목들의 순서를 결정하기 위해 각 항목(요소)들이 몇 개씩 있는지 세어서 적절한 위치에 정렬하는 방법입니다. 각 항목의 개수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 알고리즘입니다. 예를 들어 배열 [1, 2, 3, 1, 5, 6]이 있다고 하면 1은 2개가 있고 나머지 원소들은 1개가 배열 내에 존재합니다. 그러므로 배열 내에서 가장 큰 수를 반드시 알아야합니다. 파이썬에..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 문제 설명 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합..