본문 바로가기

알고리즘

[프로그래머스] 경주로 건설 (Python 파이썬) programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제 설명 문제의 설명이 위 링크에 상세하게 나와있습니다. (0,0) 칸 부터 (N-1, N-1)칸 .. 더보기
[백준] 1806 부분합 (Python 파이썬) www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 설명 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는것 중, 가장 짧은 것의 길이를 구하는 문제이다. 풀이 과정 전형적인 투포인터 문제이다. 시작점과 끝점을 적절히 이동시키며 그 사이에 있는 부분들의 합을 이용해 정답을 찾는 문제이다. 처음에 시작점과 끝점을 0으로 둔다. 그 후 시작점과 끝점을 움직이면서 구간의 길이를 조절하게 되는데, 현재 구간이 S보다 작다면, 구간을 더 늘.. 더보기
[백준] 2003 수들의 합2 (Python 파이썬) www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 설명 N개의 수열 A[1],A[2], ..., A[N]이 주어졌을 때, 수열의 부분 합이 M이 되는 경우의 수를 구하는 문제입니다. 즉, 중간중간 A[2]+A[3]+A[4] = M이라면 경우의 수가 하나 추가가 되는 문제입니다. 풀이 과정 전형적인 투포인터 문제입니다. 시작점과 끝점을 먼저 시작점에 놓습니다. 주어진 수들은 모두 자연수이기 때문에 현재 구간의 합이 .. 더보기
[프로그래머스] 보석 쇼핑 (Python 파이썬) programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 설명 위 링크에 나온 설명처럼, 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제입니다. 풀이 과정 이 문제는 투 포인터 유형의 문제입니다. 변수로 주어진 보석들의 목록인 gems에는 보석들이 중복되어 포함되어 있습니다. 그래서 보석의 종류만을 구하기 위해 set을 이용해 setlen에 보석의 종류를 넣어줬습니다. start와 end를 처음지점으로 놓고, 최초의 길이는 처음부터 끝까지로 지정합니.. 더보기
[프로그래머스] 수식 최대화 (Python 파이썬) programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제 설명 문제의 설명이 굉장히 길어 위 링크를 참고하시는 것을 추천드립니다. 수식 ex ("100-200*300-500+20") 이 주어졌을 때 +, -, *의 우선순위를 매번 다르게 하여 나타나는 값들 중 최댓값을 구하는 문제입니다. 원래는 * > +,- 의 우선순위를 갖지만, 이 문제에서는 *>+>- 가 될 수도 있고 +>->* 가 될 수도 있습니다. 풀이 과정 per.. 더보기
[백준] 1593 문자 해독 (Python 파이썬) www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 문제 설명 W를 이루고 있는 g개의 문자와, 문자열 S가 주어졌을 때, 단어 W가 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열 S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다. 예를 들어, W = cAda S = AbrAcadAbRa 이라면 W로 만들 수 있는 순열이 S안에 몇개 등장하는지.. 더보기
[백준] 15658 연산자 끼워넣기 2 (Python 파이썬) www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 문제 설명 주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다. 풀이 과정 DFS의 백트래킹을 이용해서 풀어도 되고, 아래의 코드처럼 변수로 변하는 변수를 넘겨주어도 됩니다. 핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 합니다. 백트래킹을 이용한 코드는 https://hongcoding.tistory.com.. 더보기
[백준] 17413 단어 뒤집기2 (Python 파이썬) www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 설명 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, ' 더보기

티스토리툴바