가누의 코딩로그

기억할 것 1. 큐, 덱이라고 해서 무조건 import deque로 해결되진 않는다. (시간 초과가 나거나 ..등등) 2. 이럴 때 딕셔너리를 사용하는 것이 한가지 방법이 될 수 있다. 딕셔너리로 같은 key 값을 입력받았을때 value값이 변하는 것을 큐처럼 사용할 수 있다. 문제 국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 ..

틀린 이유 1. 1자로 연결되었을 때 생각 못함 반례 예시 입력) 4 -1 0 1 2 2 2. 항상 0만 -1을 가질 것이라고 생각함(=0은 부모 노드가 없을 줄 앎) 반례 예시 입력) 9 1 6 4 1 3 3 8 8 -1 3 안풀리시는 분들은 한번씩 넣어보시길.. 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드..

기억할 것 1. DFS(깊이 우선 탐색) 2. BFS(넓이 우선 탐색) 3. DFS는 재귀함수에서 기저 상태를 정의하지 않음(정의할 수도 있겠으나 대부분의 사람들은 사용하지 않는 듯 ..? 사실 추가적인 학습이 필요할 것 같다. 한달 전에 못 푼 문제 그래프 탐색 배우고 푸니까 기쁘다 ㅎㅎ 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸..

풀이: 1. N이 3의 배수여야 하는데, 각 자리 숫자의 합이 3의 배수면 N은 3의 배수라고 할 수 있다. ex) 810 은 8+1+0 = 9, 9가 3의 배수이므로 810은 3의 배수라고 할 수 있다. 2. 그리디가 정렬 과정에서 쓰였다.(큰 수부터 정렬하므로) 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 ..

기억할 것 1. 분할정복 문제를 풀 때는 웬만해선 재귀함수를 사용할 것 2. 재귀함수 변수는 한번에 설정한다는 생각보단 풀면서 조정해야 함 문제 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 행렬을 2×2 정사각형으로 나눈다. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다. 2번 과정에 ..

방학 때 열심히 풀었더니 실버에 가게 되었다. 실버 4까지는 노력하면 풀 수 있는데, 실버 3부터는 정말 많은 노력이 필요한 것 같다. 이제는 알고리즘 강의를 본격적으로 들어야 골드를 갈 수 있을 것 같다. 아자아자 화이팅

주의할 점 1. 입력이 1, 8 등일때 1같은건 0이 나와야 하고 8같은건 4가 나옴(4+4) 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다..

기억할 것 1. 초기값을 1로 설정하기 2. 등호 사용하지 않기(본인하고 똑같은 키와 몸무게인 사람이 count 되는 것 방지) 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의..

기억할 것 1. input을 sys.stdin.readline()로 받을 것 2. box.sort(key=lambda x: (x[0], x[1])) 3. print('\n'.join([f"{x[0]} {x[1]}" for x in box])) print('\n'.join([f"{x[0]} {x[1]}" for x in box]))는 리스트 컴프리헨션을 사용하여 box 리스트의 각 요소를 형식에 맞추어 문자열로 변환하고, 그 문자열들을 줄바꿈 문자('\n')로 연결하여 출력하는 코드이다. 해당 코드는 box 리스트의 요소를 반복하면서 각 요소를 문자열로 변환하고, 이들을 리스트로 모아서 [f"{x[0]} {x[1]}" for x in box]로 만든 후, '\n'.join(...)을 사용하여 리스트의 요소..

기억할 것 1. 조합을 튜플 형태로 저장 : 모듈 itertools 사용 arr = [a,b,c,d,e] com = list(itertools.combinations(arr, 3)) 2. 최소공배수 구하는 법 : 모듈 math 사용 math.lcm(A,B,C) 문제 다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다. 서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다. 출력 첫째 줄에 적어도 대부분의 배수를 출력한다. 예제 입력 1 복사 30 42 70 35 90 예제 출력 1 복사 210..