문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 내 스스로 풀지 못했다. DP문제인데, 식 세우는 게 아직도 .. 부족하다. 더 열심히 하자. 일단 이중 for문으로 모든 경우를 탐색하는 건 n이 최대 100,000이라서 불가능하다. arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 크다면 최댓값이 계속 갱신되는 것이고, arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 작다면, arr[i-1]이 음수라는 것이고, 그러..

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 DP문제이다. i번째 coins를 쓰는 경우, 안쓰는 경우를 비교한다. i번째 coins을 쓰면 dp[j-coins[i]] + 1이 점화식이다. 5원을 써서 11원 만드는 방법을 고안한다 하면, dp[11]과 dp[11-5] + 1을 비교한다. 어렵다.......................... dp어케하냐 코드 n,k = map(int,input()...

문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 처음에는 일일히 다 구현하느라 힘들어 죽는줄알았는데... 분명 잘 했는데... 맞왜틀? 이라서 그냥 해설을 봤다.. 알고보니 한 번에 좋아하는 학생수, 비어있는 칸을 계산해두고 정렬을 하는 문제였다. 그리고 candidate = sorted(candidate, key=lambda x:(-x[0],-x[1],x[2],x[3])) 여기서 sorted는 정렬을 해서 candidat..

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 이진탐색을 사용하는데, 설치 간격을 이진 탐색 한다는 것을 이해하기 어려웠다. 가장 작은 설치거리, 큰 설치거리를 시작점과 끝점으로 두고 이진 탐색을 시작한다. 설명은 코드에 자세히 해 두었다. 코드 import sys read = sys.stdin.readline n,c = map(int,read().split()) #n, c 입력 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 스테이지에 도달한 플레이어 수와 스테이지에 도달했으나 아직 클리어하지 못한 플레이어수를 if문을 통해 각각 구해주니 시간 초과가 떴다. 따라서 if문을 줄이고자, 실패한 유저만 계산하고, 스테이지에 도달한 플레이어 수는 처음 스테이지 길이에서 실패한 유저수를 빼주는 식으로 코드를 바꾸었더니 정답! 정렬을 연습하고자, lambda를 사용하였다. lambda 사용법은, arr=sor..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS로 문제를 풀었다. dq.popleft한 값을 저장하고 그 값에 연결된 노드를 탐색해야하는데.. 계속 삽질했다 코드 from collections import deque def solution(n, computers): answer = 0 vis = [False]*n for i in range(n): #컴퓨터 개수만큼 순회 if(vis[i] == False): #i번째 방문 안했으..

문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 변수 temp가 추가되었다. temp를 통해 직전에 구한 수랑 같은지 비교해준다. 그리고 start번호를 통해 중복되는 수열을 여러 번 출력하면 안되는 조건을 만족시켜준다. 코드 import sys read = sys.stdin.readline n, m = list(map(int, read().split())) num = list(map(int, read().split())) #입력..

문제 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 변수 temp가 추가되었다. temp를 통해 직전에 구한 수랑 같은지 비교해준다. 코드 import sys read = sys.stdin.readline n, m = list(map(int, read().split())) num = list(map(int, read().split())) #입력받은 수 저장 arr = [0 for _ in range(m)] vis = [0 for _ i..

문제 https://www.acmicpc.net/problem/15657 풀이 7번에서 start만 추가해주면 된다. 코드 import sys read = sys.stdin.readline n, m = list(map(int, read().split())) num = list(map(int, read().split())) arr = [0 for _ in range(m)] num.sort() def choose(k,start): if (k == m): print(" ".join(map(str, arr))) else: for i in range(start,n): arr[k] = num[i] choose(k + 1,i) choose(0,0)

문제 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 같은 수를 여러 번 골라도 된다.라는 조건이 추가되었다. 따라서 visit 조건을 지워준다. 코드 import sys read = sys.stdin.readline n, m = list(map(int, read().split())) num = list(map(int, read().split())) arr = [0 for _ in range(m)] num.sort() def ch..