본문 바로가기
  • 시 쓰는 개발자

알고리즘23

12/23 스터디 어떤 블로그에서 봤는데, 이분탐색은 숫자 맞추는 up down 게임이라고 하더라... 좋은 예시인 것 같다.. 2110 공유기 설치 ㅇ 9663 N-Queen python으로는 실패하고... 동일 코드로 pypy로는 통과하는 문제인데 간혹 이런 문제가 나오는데 로직이 문제인지 잘 모르겠다... pypy로만 통과되는 문제면 그만큼 시간관리가 엄격하다는 건데, 그래서 그런지 검색해서 나오는 코드마다 모두 일차원 배열로 풀었다. 이차원 배열은 시간이 더 많이 걸려서 그런가보다 ... 일차원 배열 board를 선언했는데 이것의 의미는 board[ i ] = j 일 때 [ i, j ]에 퀸을 놓겠다는 의미이다. 이것을 잘 기억해두어야 한다. 우리가 문제를 풀 때 사용하는 함수는 2가지이다. 퀸을 놓을 수 있는지 .. 2022. 12. 23.
12/20 스터디 15651 N과 M(3) N과 M(1) 문제와 매우 비슷한 문제였다. 애당초 N과 M 문제들 자체가 순열 조합 문제라서, 순열 조합 중복순열 중복조합으로 이해하고 접근하면 바로 풀 수 있었다. 이 문제는 순열과 똑같은 맥락에, 중복을 추가한 문제였기 때문에 순열 코드에서 중복을 제거하는 부분만 없애주면 중복을 추가해줄 수 있게 되고 그러면 중복순열을 구현할 수 있었다. 따라서 for문 안에 if i not in s부분을 지워주면 된다. 나머지 코드는 15649 N과 M(1) 문제의 코드와 동일하다. n, m = list(map(int, input().split())) s = [] def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i i.. 2022. 12. 20.
12/7 스터디 1920 수 찾기 전형적인 binary search 문제였고, 이분탐색을 위해 먼저 정렬을 해주었다. 정렬 후 각 숫자들에 대해 모두 binary search 알고리즘을 적용해주었다. 이때, 한가지 다른 점은 flag를 각 숫자마다 0으로 설정해놓고 숫자를 찾으면 flag = 1, 없으면 그대로 0으로 설정을 해서 마지막에 flag 값에 따라 숫자 유무를 검사해서 1 혹은 0을 출력해주는 형식으로 진행해주었다. binary search에 대해 간단히 설명하면, 반씩 쪼개서 탐색을 하는 알고리즘인데 탈출 조건은 start와 end가 서로 엇갈리는 순간이다. 즉, start 2022. 12. 9.
12/1 스터디 11054 가장 긴 바이토닉 부분 수열 쉽게 생각하면, 11053의 LIS를 두번 적용하는 것 뿐인 문제였다. 바이토닉 부분 수열이라는 것이, 특정 element를 기점으로 쭉 증가하다가 감소하는 형태를 보이는 수열인데, 이것은 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열의 합쳐진 형태였기 때문이다. 가장 긴 감소하는 부분수열 문제도 있었기에 그것을 그대로 인용해도 됐지만 가장 긴 감소하는 부분수열이라는 것이 다르게 생각하면 마지막에서부터 거꾸로 올라간다면 그것도 역시 거꾸로 가장 긴 증가하는 부분수열이었기 때문에 결국 LIS를 2번 적용하되 하나는 거꾸로 적용하면 되는 형태였다. 따라서 증가하는 부분수열 increase, 감소하는 부분수열 decrease를 선언해놓고 두개를 합칠 예정인 re.. 2022. 12. 1.
11/27 스터디 11053 가장 긴 증가하는 부분 수열 [ tip ] input을 sys.stdin.readline 으로 선언해놓으면, 귀찮게 저렇게 다 안치고 input()으로만 쳐도 sys.stdin.readline을 친 것과 같은 효과를 볼 수 있다. 속설에 따름녀 sys.stdin.readline은 input보다 속도가 거의 2배 빠르다고 하므로 ... 저렇게 써서 하는 것이 좋아보인다. LIS 문제였는데, dp는 A[i]에서 가장 긴 부분수열의 길이를 넣어놓는다. 10 20 10 30 20 50 이라고 할 때 dp값은 다음과 같다. A 10 20 10 30 20 50 dp 1 2 1 3 2 4 생각보다 단순할 수 있는데, 처음에는 생각하기 어렵다. A[i]에서 자기 앞에 자기보다 작은 수가 몇개인지 세면 됐기 .. 2022. 12. 1.
11/23 스터디 10844 쉬운 계단 수 수정 예정 # 계단 수는 자리수를 하나씩 줄여도 그대로 계단 수 이어야 한다. # 즉, 자리수가 3개일 때 계단수인 수들은 자리수가 2개였어도 계단수이다. # ==>> 자리수 2개인 계단수들 중에서 하나씩 추가하는 매커니즘 # ex. 45656 => 4565 로 바뀌어도 계단수여야한다. n = int(input()) dp = [[0 for i in range(10)] for j in range(101)] # [자리수][비교 대상인 숫자] # 맨 마지막 숫자가 곧 비교대상이 되는 숫자 # 자리수 한개일 때 초기화 -->> 1~9 for i in range(1, 10): dp[1][i] = 1 # 자리수가 1일 때, 그리고 뒤에 숫자가 i인 경우에 계단수 개수가 dp값 # 자리수 2.. 2022. 11. 24.
11/20 스터디 [ tip ] 같이 공부하는 분께서 알려주신 건데, 일차원 배열만을 고집하기 보다는 이차원 배열도 적당히 섞어가며 생각해보면 좋은 답이 나올 수 있다고 하셔서, dp문제를 다음 2가지 방법으로 생각해보는 연습을 해보면 좋을 듯 하다. 1. 하나의 배열을 가지고 값을 추적하면서 값 업데이트. 2. 이중배열을 사용해서 각각의 경우의 수를 따지기. 1463 1로 만들기 여느 dp 문제가 그렇듯, 코드는 간단한데 이것을 생각해내기가 매우 어려웠다. 이 문제를 못푼 가장 큰 이유는 내가 dp문제를 풀 때 항상 top down 식으로 생각했던 것이었다. 첫번째 수와 두번째 수가 주어지면 점화식을 세우기 수월하므로 이것을 bottom up 상향식 풀이로 풀었어야 했는데 무조건 값 n에서 시작해서 내려가려고 하다보니 .. 2022. 11. 21.
코딩 문제들 느낀점 list[index+1]나 list[index-1] 처럼 다룰 때는 쉽게 out of index 나곤 함. for문을 length - 1까지만 돌리는 것들이 하나의 방법이 됨 ★★중요★★ 코드 작성할 때 주의할 것은 경계값이다. 시작지점과 끝지점에서도 정상작동 하는지 체크하는 게 중요. 안그러면 IndexError: list index out of range 가 쉽게 난다. ex. index가 0일때, 1일때 혹은 끝 인덱스일 때 등등. 테스트 케이스에서 입력값이 1억처럼 큰 경우도 있으니 for문 돌릴 때 혹은 list 초기화 할 때 함부로 입력값만큼 돌리게끔 해놓으면 안됨 그럼 시간이나 메모리 초과 날 수도 있다. 3번과 같은 맥락으로, 그래서 무지성 리스트로 풀 게 아니라, 가지고 있는 값들을 어떻.. 2022. 11. 17.
11/16 스터디 1149 RGB 거리 약간 greedy처럼 생각해서 풀었는데, 1번째는 그 다음 2,3번째만 더할수 있고 2번째는 1,3번째만, 3번째는 1,2번째만 더할 수 있는 것을 이용해서 매번마다 최소인 것들만 더해주는 식으로 진행하였다. 경우의 수가 3가지밖에 없기 때문에 하나씩 다 진행해도 상관없다고 생각했고, 마지막에 나온 3개의 값들 중 가장 작은 값을 선택하면 됐다. n = int(input()) lst = [] for i in range(n): lst.append(list(map(int, input().split()))) for i in range(1, n): lst[i][0] += min(lst[i-1][1], lst[i-1][2]) lst[i][1] += min(lst[i-1][0], lst[i-1.. 2022. 11. 16.

티스토리툴바