파이썬 (30) 썸네일형 리스트형 백준 1948 임계경로 (파이썬) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 나의 풀이(틀림) 위상정렬에 대한 개념을 응용해서 풀어야 하는 문제입니다. 문제에서 요구하는 정답은 두개로 하나는 도시를 탐색하는 경로의 수 그리고 나머지 하나는 모든 탐색이 끝났을때의 시간입니다. 저는 경로를 구할때 도로들이 2이상의 진입차수들의 합이라고 생각하였습니다. 또한 문제에서 구하는 도로를 탐색하는 인원들이 모두 모이는 시간은 다음과 같이 구현하였습니다. 위상.. 백준 20442 ㅋㅋ루ㅋㅋ (파이썬) https://www.acmicpc.net/problem/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 풀이 문제를 처음 보았을때 DP를 이용해 문제를 푸는건가 싶어 이리저리 생각을 해보았지만 마땅한 해결책이 나오지 않아 다른 분이 푸신 것을 참고하여 풀었습니다. 참고한 블로그 글 해당 문제는 투 포인터를 이용해서 푸는 문제였습니다. 그러나 저는 투 포인터에 대해 몰랐기에 나동빈님의 강의 영상을 보고 투 포인터에 대한 개념을 잡고 다른 분이 푸신 것을 참고하여 이해하고 풀었습니다. 강의 링크 이미 참고한 블로그 글에서 자세히.. 백준 1493 박스 채우기 (파이썬) https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 풀이 직사각형 박스에 주어진 정육면체 큐브들을 채워넣는 문제입니다. 처음 문제를 접하였을때 부피로 어떻게든 풀어야 겠다고 생각은 하였지만 어떻게 해결을 해야할지 고민을 하였지만 구현을 하기 까다로운 문제였다고 생각합니다. 제가 처음 접근한 방식은 주어진 상자에 주어진 큐브들을 정해진 갯수만큼 채워넣고 남은 부피를 갱신시켜 가며 풀고자 하였지만 구현으로 옮길 자신이.. 백준 22870 산책(large) (파이썬) https://www.acmicpc.net/problem/22870 22870번: 산책 (large) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 풀이 이 문제는 다익스트라를 응용해서 푸는 문제이다. 문제에서 요구하는 풀이방법은 "시작 정점 ~ 도착 정점"과 "도착 정점 ~ 시작 정점"의 최소 경로가 서로 겹치면 안된다 이다. 이를 차근차근 풀어서 설명하면 다음과 같다. 다익스트라 알고리즘을 통해 출발점 S에서 도착점 E까지 가는 최소 경로(dist_s)와 도착점E부터 출발점 S까지 가는 최소경로(dist_e)를 구한다... 백준 9202 Boggle (파이썬) https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 풀이 이전에 풀었던 백준 전설19585 와 비슷한 문제이다. 이전 문제가 단순히 트라이를 사용하는 문제라면 해당 문제는 트라이와 DFS를 같이 조합해서 푸는 문제이다. 핑계처럼 들리겠지만 오랜만에 알고리즘 푸니까 쉽게 풀지는 못했다... 풀이법은 다음과 같다. 1. 문제에서 주어진 단어들로 트라이를 생성한다. 2. 주어지는 board를 기준으로 모든 칸마다 조건을 만족하면 DFS.. 백준 19585 전설 (파이썬) https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 나의 풀이 (시간 초과) 문제자체는 쉬우나 데이터의 양때문에 시간초과가 났다. 문제 접근은 다음과 같이 하였다. 주어진 값 색상의 종류C, 닉네임의 개수 N의 범위는 1이상 4000이하이다. 그리고 팀 Q의 수는 1이상 20000이하이다. 모든 팀명은 2000이하이다. 팀명을 처음부터 마지막까지 같은 순회하면서 슬라이싱을 한다. 문제에서는 색상의 이름 + 닉네임일 경우를 판별해야 한.. 백준 2900 프로그램(파이썬) https://www.acmicpc.net/problem/2900 2900번: 프로그램 창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다. void something(int jump) { int i = 0; while (i < N) { a[i] www.acmicpc.net 풀이 문제를 푸는 로직은 단순하나 중복되는 곳을 찾아서 최적화하는게 문제 풀이의 핵심였다. 나는 중복되는 곳을 두군데를 찾아 최적화를 진행하였는데 하나는 "something"이라는 문제에서 제시해준 함수이고 나머지 하나는 구간 사이의 총합을 구하는 함수이다. 문제에서 원하는 답을 구하기 위해서는 X1, X2, X3, ... Xk의.. 백준 16938 캠프 준비(파이썬) https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 주어지는 입력은 N, L, R, X와 문제의 난이도인 A이다. 이때 문제에서 주어진 조건은 두 개이다. 1. 문제 난이도의 합은 L이상 R이하이다. 2. 문제 난이도의 가장 큰 편자는 X이하이다. 위의 조건을 그대로 파이썬에서 구현하기 위해 itertools.combinations를 사용하면 된다. 문제를 풀기위한 로직은 다음과 같다. 문제들의 난이도를 모아놓은 A리스트에서 itertools.combinations를 사용해서 2부터 N개만큼 원소를 뽑아 a라는 리스트에 담는다. a에 속한 원소들의 합이 .. 백준 15486 이진수 덧셈(파이썬) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 모든 경우를 고려했을때 최댓값을 구하라는 것 문제의 요구사항에 따라서 DP문제임을 알 수 있다. 나는 특정일에 얻을 수 있는 최대 이익을 구하는데 집중을 하였다. 먼저 특정일에 주어진 일을 기간안에 완수할수 있는지 없는지를 확인하여야 한다. 그렇기에 특정 일에 주어진 일을 마무리 할 수 있는 날을 구한다. fin_date = idx + T[idx] - 1 이후 .. 백준 2812 크게 만들기 (파이썬) https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 숫자를 지웠을때 만들수있는 수 가운데 가장 큰 수를 만들어야 하는 문제이다. 이 문제는 그리디 문제로 일종의 규칙을 발견하는 것이 중요하다. 입력 예제로 주어진 값들을 직접 지우다 보면 다음과 같은 규칙들을 발견할 수 있다. 순서 예제 입력1 예제 입력2 예제 입력3 1 1924 1231234 4177252841 2 924 231234 477252841 3 94 31234 77252841 3234 7752841 775841 값을 지우다 보면 idx의 값과 idx+1의 .. 이전 1 2 3 다음
