우당탕탕 코딩일기

틀린 이유 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..

기억해야할 것 1. lambda 함수를 sorted 함수와 같이 사용할 것. sorted(dic.items(), key=lambda x: x[1]) 다음과 같이 사용하면 딕셔너리의 value 값 기준으로 정렬됨 ! 2. lambda 함수 사용 시 list 안에 tuple 형태로 저장이 되는데, 이를 list 형태로 변환할 것. 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문..