오구의코딩모험

문제 3줄 요약 1. 색깔 별 영역을 나눈다. 2. 적록색약은 빨강과 초록을 같은 색으로 인지하여 구역을 나눈다. 3. 일반인이 보는 색깔 별 영역과 적록색약이 보는 색깔 별 영역을 구해라 BFS로 기준으로 잡은 색과 다른 색이 나오면, 다시 돌아가는 방식으로 코드를 작성하였다. 조금 차이점이 있다면, 적록색약일 경우엔 빨강과 초록을 같게 인지하는 조건문을 추가해주었다. 문제가 어렵진 않았지만, 문제를 해결하고 난 후 다른 사람과 코드를 비교해보았을 때, 상하좌우 비교와 구조체 생성을 리스트 하나로 해결하는 코드를 주로 작성하는게 보였다. 지금 나의 코드는 직관적이라고 생각하지만, 코드의 길이가 길고 복잡한 기능이 필요한 BFS, DFS 일 경우 잦은 오류가 발생하는 것 같다. 이후의 DFS, BFS 문..

문제 3줄 요약 1. 상덕이는 도둑이다. 2. 보석은 총 N개, 무게는 M, 가격은 V 3. 상덕이 가방 개수 K개, 담을 수 있는 무게는 C이며 가방 당 최대 한 개, 최대 얼마까지 훔칠 수 있을까? 문제를 읽고 직관적으로 느낀 해결법은 가방에 담을 수 있는 최대 무게가 작은 가방부터 무게 당 가격이 높은 보석을 넣어야한다는 것이었다. 따라서 무게 당 가격이 높은 보석 순으로 정렬하고 차례대로 가방에 넣고 해당 보석은 제외시키는 방법을 하니 바로 시간 초과 ㅎ.. 아무래도 리스트에서 값을 지우는 것은 리스트를 한바퀴 돌아야하므로 효율적이지 못했던 것 같다. 그리고 한번 거쳤던 보석들도 다시 재비교 한다는 것을 알 수 있었다. Ex) 무게가 1, 2, 3 가격이 5,6,7인 보석이 있다. 가방이 1,2,..

문제 3줄 요약 1. 상근이는 심심하다. 2. N개의 숫자가 종이에 있다. 3. 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게하는 M을 모두 찾아라 정수론 관련 문제는 딱 봐도 직관적으로 느껴지는게 없어서 힘든 것 같다.. (나는 그렇다. 다른 사람들은 직관적으로 보인다고 하더라) 저번 문제의 에라토스테네스의 체 같은 경우는 나름 이해하기 쉬웠지만, 이번엔 최대공약수를 구하는 "유클리드 호제법" 과 관련된 문제였다. 물론 위의 호제법을 몰랐기에 1부터 수를 늘려가며 비교해볼까 했지만, 당연하게도 수가 10억보다 같거나 작은 자연수기에 빠르게 포기하고 유클리드 호제법을 구글링하였다. https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED..

문제 3줄 요약 1. 연속된 소수의 합으로 자연수를 나타내고자 한다. 2. 위의 예시는 연속된 소수의 합으로 나타낼 수 있지만, 20과 같이 연속된 소수의 합으로 나타낼 수 없는 경우도 있다. 3. 주어진 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수는? 입력이 최대 400만이었다. 먼저 든 생각은 400만 이하의 자연수 중에 소수는 몇 개이고, 어떻게 구해야하나..? 문제의 카테고리가 정수론인만큼 정수론의 에라토스테네스의 체를 참고하였다. https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4 에라토스테네스의 체 - 나무위키 임의의 자연수 n에 대해 그 이하의 ..

문제 3줄 요약 1. 알칼리성 용액(음의 정수), 산성 용액(양의 정수)이 있다. 2. 같은 종류든 서로 다른 종류든 두 용액을 섞어서 0과 가깝게 만든다. 3. 0에 가장 가까운 경우가 두 개 이상일 경우, 그 중 아무것이나 하나 출력 스페셜 저지 딱지가 붙어있는 것을 보고 등골이 쎄했다. 이 딱지는 도대체 뭘 의미할까... 내가 생각한 방법은 두 종류의 용액을 나눠 절댓값을 최소값으로 갱신해주는 방법이었다. 근데 하나씩 비교해주니, 첫 번째 관문 "시간 초과" 최솟값인 0인 경우는 빠르게 break를 해주었다. 그 결과, 응 그냥 틀렸다. 자세히 생각해보니 문제 요약 두 번째 줄.. 최소가 같은 용액일 때를 고려해주지 않았다.. 결국 질문게시판에 있는 투포인터 코드를 활용하여 개선해주었다. from ..

문제 3줄 요약 1. 알파벳 대문자로 이루어진 문자열들을 더한다. 2. 각 알파벳은 0부터 9 사이의 숫자 중 하나로 대체한다. 3. 문자열 합의 최댓값은? 처음엔 떠오른 방법은 1. 수의 단위가 높은 곳에 있는 알파벳 2. 수의 단위가 같고 빈도수도 같다면, 그 다음으로 높은 단위에 있는 알파벳 이 두 가지 규칙을 적용하여 코드를 작성하고 제출하였다. Ex) GCF + ACDEB = 만의 자리(A : 1), 천의 자리(C:1), 백의 자리(G:1, D:1), 십의 자리(C:1, E:1), 일의 자리(F:1, B:1) → 방향 순으로 9부터 차례대로 부여 제출하니.. 런타임 에러는 -1까지 값이 내려가서 생긴 오류이고, 위의 규칙을 적용한 코드는 틀렸다고 나온다.. 반례를 찾다보니, 10, ABB, BB..

문제 3줄 요약 1. 두 묶음(A,B)의 숫자 카드를 합치려면, A+B 만큼의 비교가 필요하다. 2. A(10), B(20), C(40) 세 묶음을 비교하는 최소는(A(10)+B(20)) + (A+B(30)+C(40)) = 100이다. 3. N개의 숫자 카드 묶음의 최소 비교 수는 몇 일까? 비교 횟수가 최소가 되는 경우는 묶음의 수가 작은 묶음끼리 비교하는 것이다. 왜냐하면! 더해진 묶음을 결국 다른 묶음과 비교를 해야하는데, 숫자가 많은 카드 묶음은 가장 나중에 비교를 하는만큼 그 숫자만큼 덜 더한다. 그렇다면, 카드 묶음을 오름차순으로 정렬하고 더해주는 것을 반복해주면 되지 않나? 매번 비교를 해준 결과를 반복문을 통해 자리를 찾아주거나, 리스트의 첫 번째 원소를 가져오는 pop(0)을 연산을 할 ..

문제 3줄 요약 1. 문자열에서 지워야할 '폭발 문자열'이 라는 것이 있다. 2. 위의 3 가지 과정으로 폭발이 진행된다. 3. 폭발이 끝난 후, 남은 문자열을 출력하되 남은 문자가 없을 경우엔 "FRULA"를 출력한다. Python에는 문자열에서 문자를 지울 수 있는 replace 함수가 존재하지만... replace를 사용하여 구현한다면? 펑 시간 초과가 터져버린다. 최대 길이가 100만인 문자열을 replace로 지워가며 새로운 문자열까지 검색하는 과정이 있다보니 100만 * 검색횟수 만큼 시간이 소요된다고 생각된다. 그래서 생각해낸 방법은 이해를 돕기위해 허접한 그림판에 써보았다. Input이 ACCBB고 폭발 문자열이 CB라면, 1차 폭발 후, ACB 2차 폭발 후, A가 될 것이다. 위 과정을..

문제 3줄 요약 1. 두 문자열이 주어진다. 2. 문제가 간단하구만? 3. 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아라 문제 이름처럼 최장 공통 부분 수열을 구하는 LCS 알고리즘 문제이다! LCS가 무엇인지 모른다면, 아래 링크를 참고하면 좋을 것 같다! https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=power2845&logNo=220677085876 [Python] LCS 알고리즘(Longest Common Subsequence) LCS 알고리즘(Longest Common Subsequence) 특징 LCS 알고리즘은 두 열(Sequence) S1과 S... blog.naver.com 짧게 설명 해본다면, ..

문제 3줄 요약 1. 새로운 언어인 AC에는 R(배열의 순서 뒤집기), D(첫 번째 값 버리기) 기능이 있다. 2. 배열이 비어있는데, D를 사용하면 ERROR 3. 최종 결과를 구해라 문제를 읽어가며.. 뒤집기는 reverse, 버리기는 pop.. 너무 쉬운데? 라고 생각하자마 배열의 개수 n이 최대 10만..! (0 ≤ n ≤ 100,000) 모든걸 고려하고 작성한 첫 제출은.. 런타임 에러? 질문 게시판을 보니, 필독 문서가 내 모든 궁금증을 해결 해주었다. https://www.acmicpc.net/board/view/25456 글 읽기 - ★☆★☆★ [필독] AC FAQ ★☆★☆★ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 출력에 띄어쓰기가 없다는 점, 비어있는 배열은 "..