백준 (88) 썸네일형 리스트형 백준 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 풀이 직사각형 박스에 주어진 정육면체 큐브들을 채워넣는 문제입니다. 처음 문제를 접하였을때 부피로 어떻게든 풀어야 겠다고 생각은 하였지만 어떻게 해결을 해야할지 고민을 하였지만 구현을 하기 까다로운 문제였다고 생각합니다. 제가 처음 접근한 방식은 주어진 상자에 주어진 큐브들을 정해진 갯수만큼 채워넣고 남은 부피를 갱신시켜 가며 풀고자 하였지만 구현으로 옮길 자신이.. 백준 21277 짠돌이 호석 (파이썬) https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 풀이 구현 문제이다. 그러나 회전한다는 점을 생각하는게 까다로웠다. 그러나 풀이 자체는 그리 어려운 편이 아니다. 아래의 글을 참고하여 풀었다. https://ongveloper.tistory.com/526 백준 21277 짠돌이 호석 Kotlin (완전탐색) 문제 출처 : https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호.. 백준 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이하이다. 팀명을 처음부터 마지막까지 같은 순회하면서 슬라이싱을 한다. 문제에서는 색상의 이름 + 닉네임일 경우를 판별해야 한.. 백준 16988 Baaaaaaaaaduk2 (Easy) (파이썬) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 문제를 풀지 못하여 다른 블로그의 글을 참고하였으나...가독성이 떨어지고 불필요한 코드가 있어 고생했다. 나같은 사람들이 없기를 바라면서 글을 정리한다. 풀이 이 문제는 BFS와 조합탐색을 이용해서 해결하는 문제이다. 문제를 해결하는 방법은 다음과 같다. 상대측 돌의 그룹을 찾고 만약 상대측 돌의 그룹에 인접해 있는 빈 칸이 2개 이하이면 해당 그룹과 인.. 백준 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의.. 백준 1030 프렉탈 평면 (파이썬) https://www.acmicpc.net/status?from_problem=1&problem_id=1030 채점 현황 www.acmicpc.net 문제 풀이 문제 이해를 시도하다가 도저히 안되어서 블로그를 참고했지만...이해하는데 오래 걸린 문제이다. 푸는데 이해를 하는데 고생을 한 만큼 글로 정리하고자 한다. 이 문제는 분할정복을 이용해서 푸는 문제로 재귀를 이용해서 풀었다. 문제를 푸는 순서는 다음과 같다. 입력값들을 받는다. 전체 프렉탈을 구성해 놓고 출력을 하는 것이 아닌 문제에서 원하는 지점에 대해서 검사를 한다. (전체 프렉탈을 구성할 경우 최대 2^30 * 2^30 인 프렉탈이 나오고 메모리 공간이 부족한 것은 물론 시간 복잡도 적인 측면에서 보아도 얻을 이점이 존재하지 않기 때문이다.).. 이전 1 2 3 4 ··· 9 다음
