목록전체 글 (68)
Front-end Developer
백준 알고리즘 1010 [파이썬]
배운 내용 이 문제는 문제만 봤을 때 어렵게 느낄 수도 있지만 조합에서 이항계수의 개념만 알면 쉽게 풀 수 있다. 이항계수 문제 문제풀이 이항계수가 n개의 원소에서 k개의 부분집합을 고르는 경우인 것처럼, 이 문제에서 N개의 장소들을 어느 M개의 장소들에 연결해야할지 정하는것도 이항계수라고 볼 수 있다. 그래서 이항계수의 공식을 사용해야하는것을 이해하는게 이 문제의 키 포인트인것 같다. # 조합을 이용해서 문제를 풀어야한다. from sys import stdin read = stdin.readline for _ in range(int(read())): N, M = map(int, read().split()) num_n = 1 num_m = 1 num_d = 1 for i in range(1, N+1):..
백준 알고리즘 1932 [파이썬]
배운 내용 이 문제는 동적 계획법(DP)를 사용해서 풀어야 하는 문제이다. 동적 계획법으로 문제를 풀어봤지만 이번 문제를 통해서 동적 계획법이 무엇인지 정확하게 이해할 수 있었다. 동적 계획법 (Dynamic Programming) 동적 계획법은 재귀적으로 함수가 계속 실행될 때 소요 시간을 줄여주기 위해서 새로운 문제 값을 저장하고 해당 문제값이 저장되어있으면 다시 계산해서 그 값을 얻어내는게 아니라 미리 저장해두었던 값을 사용함으로써 재귀적으로 함수가 실행되는 시간을 대폭 줄여준다. 동적 계획법에도 여러가지 방법이 있는것으로 알고 있는데, 이 문제에서는 기존 값에다가 필요한 값을 덧붙이면서 저장한다. 문제 문제풀이 from sys import stdin read = stdin.readline lst ..
백준 알고리즘 9184 [파이썬]
배운 내용 이 문제는 동적 계획법(DP)를 사용해서 풀어야 하는 문제이다. 동적 계획법으로 문제를 풀어봤지만 이번 문제를 통해서 동적 계획법이 무엇인지 정확하게 이해할 수 있었다. 동적 계획법 (Dynamic Programming) 동적 계획법은 재귀적으로 함수가 계속 실행될 때 소요 시간을 줄여주기 위해서 새로운 문제 값을 저장하고 해당 문제값이 저장되어있으면 다시 계산해서 그 값을 얻어내는게 아니라 미리 저장해두었던 값을 사용함으로써 재귀적으로 함수가 실행되는 시간을 대폭 줄여준다. 동적 계획법에도 여러가지 방법이 있는것으로 알고 있는데, 이 문제에서는 문제 값을 저장할 공간(리스트 또는 딕셔너리)을 만들고 그 곳에다 저장하고 필요할 때 사용한다. 문제 문제풀이 from sys import stdin..
항해 99 2주차 알고리즘 [WIL]
2주차 알고리즘 항해99 2주차는 알고리즘을 공부하는 주간이다. 3주차까지 포함하여 총 2주동안 알고리즘에대해서 전혀 몰랐던 사람도 2주 후에는 코딩테스트 시험을 보고 통과 할 수 있도록 만들어주는 그런 프로그램으로 스케쥴이 짜여져 있다. 알고리즘 첫주차에는 조원들과 함께 일주일동안 주어진 문제를 풀고 마지막날에 간단한 알고리즘 테스트를 본다. 이번 첫 알고리즘 주차는 상당히 재밌었다. 2가지 이유가 있는데, 첫번째는 문제 푸는것 자체가 재밌었다. 두번째는 항해99 크루원들과 같이 공부할 수 있어서 재밌었다. 내가 느끼기에 알고리즘 공부는 어려운 수학문제를 푸는 느낌이다. 문제를 이해하고 이 문제를 어떻게 접근할지 고민하고 또 고민하고 계속 고민하다가 유레카!하고 풀이방식을 찾아내는게 뭔가 수학같다. 수..
백준 알고리즘 10815 [파이썬]
배운 내용 이 문제는 시간초과 때문에 이분탐색을 사용해야한다. 이분탐색은 리스트안에서 내가 원하는 값이 있는지 탐색할 때 첫번 째 index와 마지막 index 사이에 중간 index를 찾아서 그 중간 값이 원하는 값이면 탐색이 거기서 끝나고 만약 중간값보다 작으면 찾는 값이 중간 값을 기준으로 왼쪽에서 찾아보면 된다. 그리고 만약에 찾는 값이 중간값보다 크면 중간 값을 기준으로 그 오른쪽에서 찾아보면 된다. 또 하나 더 배운것은 만약 lst = [10, 20, 30, 40] 이 리스트 값을 10 20 30 40 이라는 형태로 출력하기 위해서 " ".join(map(str, lst)) = 10 20 30 40 사용하면 된다. join() int에 사용할 수 없기 때문에 string으로 바꿔줬다. 문제 문..
백준 알고리즘 4949 [파이썬]
배운 내용 이 문제는 스택을 사용해서 문제를 풀었다. Stack은 데이터를 일시적으로 저장하고, 후입 선출(LIFO, Last In First Out) 구조를 가지고있다. 파이썬에서는 append를 사용해서 데이터를 저장하고 pop을 사용해서 데이터를 꺼낸다. 리스트로된 stack을 string값으로 바꿀 때. string 변수값을 따로 만들고 그 안에 리스트 element를 하나씩 더해주면 된다. string = "" for ele in stack: string += ele 만약 string에 아무값도 없으면을 코드로하면 if not string: 문제 문제풀이 stack = [] answer = [] while stack != ['.']: stack = [] answer = [] while stack..
백준 알고리즘 11651 [파이썬]
배운 내용 숫자나 문자를 정렬할 때 sort 사용법에 대해서 배웠다. sort() 함수 만으로 생각보다 할 수 있는것이 많았다. [x, y]라는 숫자값이 여러개가 있는 리스트에서 x 크기가 작은 순서대로 x 크기가 같을 때는 y 크기가 작은 순서대로 정렬시킬 때 리스트.sort() 만 하면 된다. 그러면 알아서 정렬시켜준다. 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 ..
백준 알고리즘 11729 [파이썬]
배운 내용 재귀함수관련 문제중에 제일 유명하다고 할 수 있는 하노이 탑 이동 순서 문제를 풀어보았는데, 재귀함수 알고리즘 문제를 풀어본적 없는 나에겐 너무 어려운 문제였던것 같다. 하지만 이 문제를 풀고 이해하면서 재귀함수에대해서 잘 이해할 수 있었다. 문제 풀이 설명은 코드안에 해놨습니다. 문제 문제풀이 # 재귀함수 # 조건에 맞으면 function을 계속 반복시킨다. n = int(input()) def hanoi_recursive(n, a, b, c): if n == 1: print(a, c) return else: hanoi_recursive(n-1, a, c, b) # 제일 밑에 있는 원판을 제외한 다른 원판들을 보조지역에 옮긴다. print(a, c) # 제일 밑에있는 원판을 목표지점에 옮긴다..