본문 바로가기

Algorithm/Baekjoon

 (21)
Algorithm/Baekjoon Baekjoon #2606 - 바이러스 풀이(단방향과 양방향 그래프) 문제 문제의 내용을 요약하자면, 서로 연결된 여러 대의 컴퓨터 중 첫 번째 컴퓨터가 바이러스에 걸렸을 때 바이러스에 감염되는 컴퓨터의 수를 구하는 것이다. 예를 들어, 아래 그림과 같이 컴퓨터가 연결되어 있고, 이 중 1번 컴퓨터가 바이러스에 감염되었다면 1번 컴퓨터와 연결된 모든 컴퓨터(2, 3, 5, 6)의 수량을 출력해야 한다. 입력으로 주어지는 값은 다음과 같다. 이때, 컴퓨터의 수가 7이면, 1번부터 차례대로 번호가 매겨진다. 줄 기호 내용 예시 첫 번째 줄 N 컴퓨터의 수 7 두 번째 줄 M 직접 연결된 컴퓨터 번호 쌍의 수 6 세 번째 줄 + M 직접 연결된 컴퓨터 번호 쌍 1 2 2 3 1 5 5 2 5 6 4 7 풀이 총 두 번의 시도 끝에 성공하였다(소스코드). 정말 놓치기 쉬운 부분을..
Algorithm/Baekjoon 2869번(달팽이는 올라가고 싶다) 파이썬(Python) 풀이 공유 들어가며 문제의 내용을 보기 전에 꽤 낮은 정답률(28.049%)을 보고 흥미가 더 생겼던 문제이다. 그런데, 생각보다 매우 간단한 문제라서 허무하게 끝난 것 같다. 아래 그림은 어려울 것 같은 문제는 비교적 쉽게 풀리고, 쉬울 것만 같은 문제는 생각하지 못한 곳에서 오류가 발생하는 상황을 너무나도 잘 나타내주어 정말 공감된다. 문제 2869번 달팽이는 올라가고 싶다 시간 제한 메모리 제한 0.15 초(추가 시간 없음) 128 MB 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구..
Algorithm/Baekjoon 2292번(벌집) 파이썬(Python) 풀이 공유 들어가며 나를 알 수 없는 늪으로 빠지게 한 문제이다. 문과 출신이라 그런지 수학이랑 그다지 친하지는 않은데도 불구하고 가우스 공식을 코딩에 접한 이후로 공식 만드는 재미에 빠져서 공식을 세우기 위해 약 한 시간 가량을 삽질했지만, 결국에는 whlie 문으로 해결하였다. 1. 문제 2292번 벌집 시간 제한 메모리 제한 2 초 128 MB 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3..
Algorithm/Baekjoon 1712번(손익분기점) 파이썬(Python) 풀이 공유 들어가며 처음 문제에 접근했을 때에는 while 문으로 수량을 파악하려고 하였으나, 세 번째 테스트케이스를 보고난 이후에는 생각이 완전히 바뀌었다. 세 번째 테스트케이스를 적용하는 경우 약 20억 번의 반복을 수행해야 하는데, 이럴 경우에는 문제에서 요구하는 시간 제한(0.35초)를 초과하기 때문이다. 따라서, 문제에서 요구하는 손익분기점의 의미를 먼저 파악한 다음에 규칙을 찾고, 코드를 작성하였다. 1. 문제 1712번 손익분기점 시간 제한 메모리 제한 0.35초 128 MB 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다..
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보다..

티스토리툴바