알루 코딩

이 문제는 유니온-파인드 집합 문제입니다. DFS나 BFS로 풀 때, 유의해야 할 점은 결국 자기자신으로 돌아오는 여행루트도 존재한다는 점입니다. 가장 직관적이게 풀 수 있는 알고리즘은 union-find 인데요, 여행계획이 어떻게 주어지더라도 결국 여행이 가능하려면, 각 도시는 같은 사이클에 존재해야 한다는 전제가 있어야 합니다. 하나의 사이클에 같이 존재하지 않는다면, 다시말해 어떠한 도시에서 어떤 도시로 갈 수 있는 방법이 존재하지 않는다면, 여행은 불가능하겠죠. 풀이는 코드를 토대로 설명드리겠습니다. import sys input = sys.stdin.readline def find_parent(parent,x): if parent[x] != x: return find_parent(parent,p..

더보기 문제 사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다. ((1 - 5) - 3) = -7 (1 - (5 - 3)) = -1 위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다. (((1 - 3) + 5) - 8) = -5 ((1 - (3 + 5)) - 8) = -15 (1 - ((3 + 5) - 8)) = 1 (1 - (3 + (5 - 8))) = 1 ((1 - 3) + (5 - 8)) = -5 위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, ..

모각코 두번째 회의 후 각자 코딩 테스트를 위한 문제풀이를 진행했습니다! 저는 구름 LEVEL 에서 2시간의 시간제한을 두고 챌린지 문제들을 풀어봤습니다. 그 중에서 복기할만한 문제들을 추려보겠습니다. ✏️ 준비운동 PART3. 각자 문제풀이 1. 개미와 진딧물 한 변의 길이가 N 인 정사각형 모양의 평면에 진딧물 집과 개미 집이 있다. 개미 집은 고유의 영역 범위 안의 모든 진딧물에게서 수액을 수집한다. 이 수액이 없으면, 개미 집은 부족한 식량으로 제거된다. 길이가 4 인 정사각형 평면을 1X1 크기의 작은 정사각형으로 나누면 아래와 같은 그림으로 표현할 수 있다. 위와 같은 상태로 arr[i][j] 값들이 주어진다. arr[i][j] 의 값은 0,1,2 중 하나이며, 1은 개미 집이고, 2는 진딧물..

모각코 두번째 회의 후 PART2. 약점체크를 풀며 준비운동을 했습니다! 확실히 저번주보다는 난의도가 높은 문제들인 것을 체감했습니다. ✏️ 준비운동 PART2. 약점체크 재귀 탐색의 기본: 연산자 끼워넣기 (🥈실버 1티어) 스택의 응용: 괄호의 값 (🥈실버 2티어) 시뮬레이션 기본: 빗물 (🥇 골드 5티어) 완전탐색의 유연한 생각: 가르침 (🥇 골드 4티어) 그리디의 기본: 멀티탭 스케줄링 (🥇 골드 1티어) 투 포인터의 기본: 부분합 (🥇골드 4티어) 벨만포드 뼈대문제: 최소비용 구하기 (🥇 골드 5티어) Prime, Kruskal 뼈대문제: 최소 스패닝 트리 (🥇 골드 4티어) KMP 뼈대문제: 부분 문자열 (🥉 브론즈 2티어) 위상정렬: 줄 세우기 (🥇 골드 3티어) 1. 연산자 끼워넣기 impo..

모각코 첫번째 회의 후 PART1. 튼튼한 기본기를 풀며 준비운동을 했습니다! 쉬운 문제를 풀며 자신감도 올리고 기본적인 문법을 복기하기 좋았습니다. ㅎㅎ ✏️ 준비운동 PART1. 튼튼한 기본기 약수 구하기 (🥉 브론즈 3티어) 이진수 (🥉 브론즈 3티어) 최소, 최대 (🥉 브론즈 3티어) 지능형 기차 2 (🥉 브론즈 3티어) 피보나치 수 5 (🥉 브론즈 2티어) 일곱 난쟁이 (🥉 브론즈 2티어) 최대공약수와 최소공배수 (🥈실버 5티어) N번째 큰 수 (🥈실버 5티어) 소수 찾기 (🥈실버 4티어) 쉽게 푸는 문제 (🥈실버 4티어) 소수 (🥈실버 4티어) 1. 약수 구하기 import sys input = sys.stdin.readline N, K = map(int,input().split()) answ..

단순한 그리디 문제였다. 맨 처음에는 그리디가 아니라 dp문제인가 싶었다. 이전에도 풀었던 기록이 있어서 단순한 그리디로도 풀릴 듯해서 바로 푼 문제였다. 코드는 아래와 같다. import sys input = sys.stdin.readline height = [] for _ in range(9): height.append(int(input())) diff = sum(height)-100 # 9명의 난쟁이 키의 합과 100의 차이를 구한다 find_two_false = False # find_two_false라는 초기변수를 False로 설정한다. for i in height: for j in height[1:]: if i + j == diff: # height를 돌면서 두 난쟁이의 합이 diff와 같으면..

비교적 쉬운 문제이지만, strip()을 안해서 처음에 index오류가 났고, 2 all check 20 했을 때, 1이 나와야 하는데 0이 나와서 계속 왜 안될까 고민하다가, number라는 입력받은 숫자를 int로 변환하지 않아서 check를 할 때 이상값이 나왔다. discard도 remove와는 다르게, 해당 값이 없으면 remove는 오류를 출력하지만, discard는 해당 값이 있을 때만 없애주고, 없으면 무시한다. 코드는 아래와 같다. import sys input = sys.stdin.readline M = int(input()) queue = set() for _ in range(M): in_put = input().rstrip() if in_put == "all": queue.updat..

차근차근 문제에서 주어진 로직을 풀어보면, 그다지 어렵지 않은 문제였다. 문제의 로직은 따로 설명하게 없을 정도로, 문제에서 주어진 대로 그대로 구현하면 다들 풀 수 있을 것이다. 처음 입력받는 N과 M은 각각 '주차장 공간의 수'와 '차량의 수'이다. 모든 차량은 한 번씩 주차장에 들어갔다가 나오므로 (차량의 수 *2) 만큼의 출입 순서를 입력받아야 했다. 우선 index오류를 막기 위해, '요금을 나타내는 리스트'와 '각 차량의 무게를 나타내는 리스트'를 빈 리스트 [] 가 아닌 [0]으로 시작했다. 들어오는 출입 순서를 덱으로 큐화 시켰다. popleft()를 쓰기 위함이다. 이 출입리스트가 빌 때 까지, 계산을 반복한다. 이 문제에서 생각해야 할 관건은 크게 2가지만 생각해주면 됐다. 주차 가능한..

일단, 나도 처음에 틀렸던 문제다. 그리디 문제로 접근을 했었고, 문제를 풀었는데, '예제 입력 5' 와 같은 반례에 부딪혔다. 나의 로직은 이러했다. 문제에서 1번 사람부터 N번 사람까지 순서대로 잃는 체력리스트와 얻는 기쁨 리스트를 입력받는다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 것이므로, [hp(체력), joy(기쁨)]을 쌍으로 갖는 새로운 리스트를 만든 후에, joy(기쁨)을 기준으로 내림차순 정렬을 한다. 그러면, 큰 joy(기쁨)를 가지는 쌍이 앞에 오겠고 해당하는 hp(체력)을 초기 HP(100)에서 빼가면서 음수나 0이 아니면, 해당 joy(기쁨)을 그대로 더해주면서 for문을 순회하도록 로직을 짰다. 처음에 짠 로직은 아래와 같다. import sys input = sys.std..

작년에 풀었던 문제인데, 제대로 이해를 하지 않고 넘어갔었던 느낌이 들어 다시 풀어본 문제이다. 거의 기억이 안나서 새로 푼 문제나 다름이 없었는데, 총 3번의 시련을 겪었다. 가장 먼저, 잘못된 로직으로 문제를 풀어나가기 시작했다. 예를 들어, 입력값이 3 1 98 98 99 99 100 이 주어졌다고 하면, 답은 어떻게 나올까? 답은 3이 나와야 한다고 생각한다면, 나와 똑같은 실수를 한 셈이다. 답은 1이 나와야 한다. 1~98 , 98~99, 99~100 이렇게 겹치지 않고, 1강의실만을 이용해서 강의를 배정할 수 있기 때문이다. 첫 번째 시련을 겪고, 빠르게 로직에 대해서 생각해봤다. 대충 로직은 이러했다. 입력 받은 "강의가 시작되는 시간"과 "강의가 끝나는 시간"을 강의 리스트를 (강의 시작..