본문 바로가기

Algorithm

 (38)
Algorithm/Baekjoon 1316번(그룹 단어 체커) 파이썬(Python) 풀이 공유 들어가며 문제를 이해하자마자 문자열을 구성하는 모든 문자의 인덱스를 알아내면 문제를 풀 수 있을 것 같았다. 하지만, 3차원 리스트, 여러 반복문 사용으로 구현하기에는 꽤나 복잡할 것으로 예상되는 문제였는데, 생각보다 쉽게 통과하였다. 1. 문제 1316번 그룹 단어 체커 시간 제한 메모리 제한 2초 128 MB 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 1.1..
Algorithm/Baekjoon 1193번(분수 찾기) 파이썬(Python) 풀이 공유 들어가며 여러 방면을 고려해야 하는 문제라 그런지 약간 복잡하게 느껴지는 문제였다. 다른 분들이 올려놓은 코드와 비교해보았을 때 방향성은 비슷했으나, 구현 방식에는 약간의 차이가 있다. 1. 문제 1193번 분수 찾기 시간 제한 메모리 제한 0.5초 (추가 시간 없음) 256 MB 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. col1 col2 col3 col4 col5 1/1 1/2 1/3 1/4 1/5 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … … 4/1 4/2 … … … 5/1 … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. ..
Algorithm/Baekjoon 1011번(Fly me to the Alpha Centuari) 파이썬(Python) 풀이 공유 들어가며 약 2개월 이라는 기간을 두고 총 두 번 풀었던 문제인데, 수열을 다룰 줄 안다면 훨씬 쉽게 해결 가능한 문제이다. 문제 풀이 문제에서 최종적으로 요구하는 사항을 정리해보면, x에서 y로 이동하기 위한 공간이동 장치의 최소 작동 횟수를 찾는 것이다. 단, 아래의 조건을 만족시켜야 하는데, 이 중에서 세 번째 조건이 문제의 핵심 포인트라고 할 수 있다. 공간 이동 장치를 처음 작동시킬 때 이동 가능한 범위는 -1, 0, 1 광년이다. 공간 이동 장치로 이동한 거리를 k 광년이라고 할 때, 다음에 이동할 수 있는 거리의 범위는 k-1, k, k+1 광년이다. y에는 반드시 1 광년 만큼만 이동해서 도착해야 한다. 만약, X가 1, y가 6으로 주어질 때로 가정해보자. 먼저, x에서 y로 이동하기 위..
Algorithm/Baekjoon Baekjoon #1744 - 수 묶기 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1744번 수 묶기 2. 입출력 예시 입력 예시 출력 예시 4 -1 2 1 3 6 3. 문제 풀이 이 문제는 코드를 총 3번 제출하여 통과하였는데, 그 이유는 테스트케이스 선정에 오류가 있었기 때문이었다. 따라서, 이 문제를 해결할 때에는 테스트케이스를 잘 선정하여 예외사항을 처리하여야 한다. 최종 제출할 때 선정한 테스트케이스는 아래와 같다. 수열의 개수(N) : 11 수열 : [9, 8, 7, 6, 5, 4, 3, 2, 0, -10, -20] 실패하였을 때는 수열을 오름차순으로 정렬 후 x번째의 수와 x+1번째의 수를 더한 값과 이 둘을 곱한 값 중 큰 값을 최종 값에 더하는 경우만 적용하였다. 그러나, 이와 같이 한 ..
Algorithm/Baekjoon Baekjoon #13305 - 주유소 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 13305번 주유소 2. 입출력 예시 입력 예시 출력 예시 4 2 3 1 5 2 4 1 18 4 3 3 4 1 1 1 1 10 3. 문제 풀이 문제에서 도시 간 이동거리와 도시 별 주유비에 대한 정보가 주어진다. 이 중 가장 마지막 도시는 도착지이며, 도착지에서 주유할 필요가 없기 때문에 주유비의 마지막 정보는 필요하지 않다. 또한, 도시가 2개일 경우 첫 번째 도시에서 주유를 하고 다음 도시로 이동해야 하므로, 별도의 비교는 할 필요가 없으며 첫 번째 도시의 주유비와 이동 거리를 곱하면 된다. 이 점을 참고하여 문제를 요약 후 순서로 나타내면 다음과 같다. 도시의 수(N)를 입력받는다. 도시 간 이동 거리(route)를 ..
Algorithm/Baekjoon Baekjoon #1715 - 카드 정렬하기 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1715번 카드 정렬하기 2. 입출력 예시 입력 예시 출력 예시 3 10 20 40 100 3. 문제 풀이 이 문제는 시간관리에 있어서 애먹었던 문제이다. 문제를 해결하기 위한 논리는 매우 단순하다. 비교할 카드 묶음의 수량(n)을 입력받는다. 만약에 카드 묶음의 수량이 1개일 경우는 비교할 필요가 없으니 결과값을 0으로 출력하고, 그 외에는 결과값(total)을 0으로 초기화한 후 카드 묶음의 수량만큼 반복하여 카드 묶음의 크기를 입력받아 리스트(lst)에 추가한다. 비교를 할 때 카드 묶음의 크기가 작은 순으로 연산을 수행해야 최솟값이 나오므로, 리스트를 오름차순으로 정렬한다. while문을 통해 리스트의 크기가 1보다..
Algorithm/Baekjoon Baekjoon #4796 - 캠핑 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 4796번 캠핑 2. 입출력 예시 입력 예시 출력 예시 5 8 20 5 8 17 0 0 0 Case 1: 14 Case 2: 11 3. 문제 풀이 주어진 입력/출력 예시를 통해 점화식을 세워보도록 하자. 휴가를 사용할 수 있는 총 기간이 20일이다. 그리고 이 중 연속된 8일은 2번(20 ÷ 8) 존재한다. 캠핌장 사용은 연속된 8일 중 5일만 사용 가능하므로 연속된 2일에 대한 캠핑장 사용 일수는 10일(20 ÷ 8 × 5)이다. 그렇다면 연속되지 않은 나머지 4일은 어떻게 될까? 이 역시 휴가 전과 후에 연속된 또 다른 8일이 존재한다. 즉, 나머지 4일은 캠핑장 사용 가능 일수 5일보다 작으므로 모두 캠핑장 사용이 가..
Algorithm/Baekjoon Baekjoon #1339 - 단어 수학 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1339번 단어 수학 2. 입출력 예시 입력 예시 출력 예시 2 AAA AAA 1998 2 GCF ACDEB 99437 10 A B C D E F G H I J 45 2 AB BA 187 3. 문제 풀이 이 문제는 딕셔너리를 활용하면 어렵지 않게 해결할 수 있다. 각 단어의 알파벳을 key로 설정 후 알파벳의 위치를 10의 제곱으로 나타내기로 하였다. 이를 표로 나타내면 아래와 같다. 단어 내용 GCD G(100), C(10) + D(1) ACEBF A(10000) + C(1000) + E(100) + B(10) + F(1) 위 표에 나타난 단어의 알파벳을 중복제거 후 값이 큰 순으로 정렬하면 아래와 같다. 이 알파벳 정렬..
Algorithm/Baekjoon Baekjoon #10162 - 전자레인지 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 10162번 전자레인지 2. 입출력 예시 입력 예시 출력 예시 100 0 1 4 189 -1 3. 문제 풀이 이 문제의 유형은 거스름돈과 동일했으며 딕셔너리를 사용하여 간단히 해결할 수 있었다. 문제를 해결하기 위한 순서는 아래와 같다. 딕셔너리(btn)의 각각 key를 버튼으로 하고 value를 0으로 초기화한다. 이때 각각 버튼은 모두 초 단위로 바꾸어주며, 초 단위가 큰 순으로 key에 저장한다. 냉동식품의 요리시간(T)를 입력받는다. 딕셔너리의 key를 기준으로 반복하며 해당 key의 value를 요리시간에 버튼의 초로 나눈 몫으로 변경하되 정수형이 아닌 문자열(str)로 변환한다. 이후 요리시간은 요리시간을 버튼의..
Algorithm/Baekjoon Baekjoon #1946번 - 신입 사원 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1946번 신입 사원 2. 입출력 예시 입력 예시 출력 예시 2 5 3 2 1 4 4 1 2 3 5 5 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 4 3 3. 문제 풀이 이 문제는 어찌보면 매우 간단하게 해결가능하나, 시간초과를 고려해야 하기 때문에 골치아픈 문제이다. 이 문제 흐름의 핵심은 정렬 후 값의 크기 비교이다. 서류심사 순위와 면접심사 순위가 주어지는데, 다른 사람들과 비교하였을 때 두 개 순위 모두 뒤처질 경우 탈락하는 방식이다. 즉, 둘 중 하나는 다른 사람들보다 높아야하므로 이를 알아보기 쉽게 서류심사 순위를 기준으로 오름차순 정렬을 해주어야 한다. 주어진 예시를 통해서 확인해보자. 먼저 5명인 ..

티스토리툴바