Algorithm

최대공약수를 구하면 최소공배수는 a \* b / (최대공약수)최대공약수를 구하는 가장 간단한 방법은 유클리드 호제법 이를 이용하여 최소공배수와 최대공약수를 구하면

입력받은 4보다 큰 짝수를 두 홀수 소수의 합으로 나타내기isPrime(a) : a가 소수인지 판단하는 함수goldBach(n) : n이 소수의 합으로 이루어졌는지 판단하고 그 중 작은 소수를 return 하는 함수. 만약 소수의 합으로 이루어지지 않았다면 "Goldb

isVisitable(x,y) : x, y 위치의 점에 집이 있으면 true, 없으면 false 값을 return 한다.visitAll(x,y) : 주어진 x,y와 연결된 모든 위치를 방문하여 집이 있는 지 확인하고, 방문한 곳을 모두 0 (집이 없는 것처럼) 만든다.

intertools / backtracking 이용

순열이므로 index를 이용했다.visit 은 부분수열 숫자들의 index의 리스트들로 이루어진 리스트. 해당 부분수열의 마지막 index보다 큰 index가 visit 에 추가된다.

python3 특성상 시간초과가 뜰 수 밖에 없고pypy3로 제출해야.메모리 초과가 뜬다.visit 에 너무 많은 요소가 들어가서인듯.

N 번째 피보나치 수에서 0과 1을 호출하는 횟수를 각각 출력한다. 새로운 수를 입력받을 때마다 그 때 그 때 계산해주면 시간 초과가 걸린다.fibbo_nums 에 계산이 완료된 값을 넣어주어 재사용이 가능하도록 했다.

s_max1 : 연속 1번 계단을 밟았을 때 (해당 계단을 처음 밟았을 때) 계단 합의 최댓값s_max2 : 연속 2번 계단을 밟았을 때 계단 합의 최댓값연속된 계단 3개를 밟는 것을 불가능하므로 연속 2번까지만 생각해주면 된다. n 번째 계단의 s_max1 값 : n

n_triangle : 삼각형의 크기triangle : 삼각형→ ex : \[\[7], \[3, 8], \[8, 1, 0], \[2, 7, 4, 4], \[4, 5, 2, 6, 5]] s_triangle : 삼각형 각 자리에서의 최댓값. 삼각형 위부터 계산된다.i 열

익은 토마토들을 visit 에 저장하고 findUnRipenTomato() 를 통해 새로 익게되는 토마토들을 new_visit에 저장만약 new_visit 이 비어있으면 while 문을 종료하고 비어있지 않으면 visit 으로 옮겨준 후 날짜(count)를 증가시킨 후

computeAbility(team) : team 배열에 속한 사람들과 team 배열에 속하지 않은 (다른 팀) 사람들을 이용하여 두 팀의 능력 차이를 계산하여 returnmakeTeam() : 가능한 조합의 팀을 만들어낸다.예를 들어 4명의 사람이 있으면 0,1, 0

coin_values : 가지고 있는 동전의 가치들의 배열. reverse 를 이용하여 내림차순으로 정렬한다getMaxCoin(sum, start) : start 이후의 index 를 가지는 coin_value 들 중 sum 보다 작거나 같은 최대 가치 (낼 수 있는

https://suri78.tistory.com/128 참고 > 사이클은 visit에 넣는 group 의 숫자로 구분한다. → 연결된 index들의 visit[index]에 같은 값의 group 숫자를 넣어준다. 이미 다른 group이나 현재 group에 연결된

문제이전문제 에서 참고했던 예시들을 이용하였다.

bfs를 이용했다. 처음엔 가장자리가 모두 default로 공기인 것을 모르고 가장자리 중 공기가 있는 부분을 찾아 start 리스트에 넣어준 후 bfs를 돌렸는데 실패가 떴다. (0,0)만 넣어주게 바꾸니 바로 성공했는데 왜일까,,

제일 어렵다. 그 때 그 때 가장 최적의 선택을 하는 것. 이중 for 문으로 모든 경우의 수를 찾아주는 순간 시간초과가 걸린다.회의실 배정의 경우, 회의의 시작시간과 끝시간을 이용하여 가장 많은 회의를 할 수 있는 경우의 수를 찾는 것. 그 순간부터 시작할 수 있는

문제로 바로가기매번 minimum 값을 찾아주면 시간이 오래 걸린다.내림차순으로 정렬한 후 index를 이용하면 바로 min 값을 얻을 수 있다.

0-9 사이의 값을 가지는 순열 중 해당 부등호 조건을 만족시키는 최솟값과 최댓값을 출력하는 알고리즘.check 함수는 입력받은 string 이 현재시점까지 부등호 조건을 만족시키는 지를 확인한다. perform 순열을 만든다. 부등호조건을 만족시키지 않으면 더이상 순

병합정렬을 구현하고, 그 기준을 문제의 정렬 기준으로 설정하였음

greedy algorithm 너무 어렵다.기본적으로 끝의 자리를 기준으로 정렬해준 후,그 리스트를 이용하여 조건에 해당하는 지 확인해준다.

문제 바로가기우선순위 큐를 이용하면 어렵지 않은 문제. 카드들 중에서 가장 수가 적은 카드 묶음 두개를 합치고, 그 카드들을 다시 우선순위 큐 리스트에 넣어주는 과정을 반복한다. (리스트에 카드가 하나 남을때까지)

문제로 가기

mid == 0이 되는 경우가 발생하면 런타임오류.ex :

list += element 는 항상 extend의 형태로 작용한다. tuple 이나 리스트의 형태로 element를 추가해주려면 append를 이용해야 한다.deque에 list나 tuple append 가능함항상 index 범위 주의해줄것..!truck_weight

문제 바로가기(https://programmers.co.kr/learn/courses/30/lessons/49993skill은 선행스킬 순서 abc는 a → b → c 의 순서로 반드시 스킬을 배워야 한다는 것을 의미한다skill_trees 유저들이 만든 스킬

10진법이 아닌 자신만의 방법으로 수를 표현하는 124 나라. 자연수 n 이 10진법으로 주어졌을 때 124 나라에서 사용하는 수를 return 해야 한다.기본적으로 수 3개를 사용하는 3진법과 동일.but 0 대신 4가 존재하기에 3의 배수의 경우 다른 값이 나온다.

문제 바로가기초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.바로 for 문 돌려버렸다.끝까지 주식 가격이 떨어지지 않은 경우만 추가로 고려하였다

정직하게 문제 조건대로 압축한 후 그 길이를 비교해줬다. 다른 사람들 풀이를 보니까 길이만 구하면 되니까 개수만 가지고 풀더라. n개 단위로 자르고 남은 조각을 고민하기 귀찮아서 그냥 패스. formatting formatting 을 통해 코드를 더 깔끔하게 할

compare 함수를 추가로 만들어서 해결numbers = \[0,0,0,0] 일 경우 0000 을 return 하기에 만약 numbers 의 첫번째가 0일 경우, 즉, numbers 에서 가장 큰 수가 0일 경우 0 만 return 하도록 코드를 추가해줬다.처음엔 n

문제 바로가기(https://programmers.co.kr/learn/courses/30/lessons/4288310번 case 에서 시간 초과가 난다.첫번째 시도에서 리스트에서 값을 삭제하는 데에 시간이 많이 소요되는 듯 하여 본 리스트에서 삭제하는 대신

문제balance : s = u + v 로 분리할 때, 더 이상 분리될 수 없는 균형잡힌 괄호 문자열 u을 만드는 index를 리턴한다correct : 올바른 문자열인지 확인reverse : 문자열 뒤집는 함수문자열을 뒤집는 reverse 함수를 람다 함수로 바로 이용

문제 삼각달팽이 이런 식으로 시계 반대방향으로 숫자를 넣은 후 그 값을 배열로 나타내기 풀이 ![](https://images.velog.io/images/jujube0/post/761e3f13-f8e4-4cb3-9f69-989cbd238f68/image.pn

complete binary tree 단 두개의 자식 노드만을 갖는 이진트리 중 노드가 왼쪽부터 차례대로 채워져있는 트리를 말한다. Heap 최소 힙을 기준으로 부모 노드가 항상 자식 노드보다 작은 형태의 완전 이진 트리

중복을 허용하지 않고순서가 없는 것이 특징 s1 & s2set(range()) 를 하면 range 내의 숫자가 set이된다. isPrime 으로 각각 소수인지 확인하는 대신 전체에서 그 배수들을 제거해주는 것

enumerate(, start = 1) 을 이용하면cite 이상 인용된 논문이 i 개 이상이 된다. 원하는 것은 h 이상 인용된 논문이 h 개 이상 즉 인용 수와 논문 수를 동일하게 맞춰야 하므로 min 을 이용. answer 는 그 중 가장 큰 것..

딕셔너리도 한 번 써봤는데 시간이 더 걸리는 것 같다. 같은 type 에 대해 여러번 값을 계산해서인 것 같다.

improvision

String 을 포맷 한 후 작업을 해야함더 깔끔한 format 방법

문제가기내풀이. 효율성 테스트를 하나도 통과하지 못했다...

문제 바로가기방법은 똑같지만 더 간단한 방법. 코드는 간단하지만 시간은 2배정도 더 걸린다. 여기에서는 max 값을 매번 새로 계산하지만 기존 코드에서는 행마다 max 값을 한 번 계산하여 이용하기 때문.

문제 바로가기(https://programmers.co.kr/learn/courses/30/lessons/68936!\[](https://images.velog.io/images/jujube0/post/2840c666-b6a4-467b-9f79-f7a

문제 바로가기\+,-,\* 의 연산기호만으로 이루어진 연산수식(expression) 에서 연산기호의 우선순위를 재정의하여 얻을 수 있는 최댓값을 구하는 문제nums 는 숫자들 배열,ex 는 연산기호들의 배열만약 expression = "100-200\*300-500+2

문제 바로가기queue 이용

문제 바로가기다이나믹 프로그래밍으로 풀려고 했는데 효율성 테스트를 하나도 통과하지 못했다. 2진법을 꼭 이용해야 통과할 수 있는 문제인듯

문제 바로가기 딕셔너리를 이용했다. Others 파이썬에서 정규표현식 이용하기 ▶︎ match 문자열이 정규식과 매치되는 지 확인,

문제 바로가기find4 : 전체 board 를 돌며 0(비어있는 칸)이 아니면서, 해당 블록을 좌상향으로 하는 4칸이 일치하는 좌표를 찾아 list 에 넣는다. delete4 : find4 에서 찾은 좌표들을 이용하여 이를 좌상향으로 하는 4칸 블록을 '0'(비어있는

문제 바로가기res = \[tuple(\[item\[key] for key in ls]) for item in relation]이런 식으로 할 수도 있음a.issubset(b)b.issupperset(a)나는 len(set(a) - set(b)) == 0 을 이용했다.

문제 바로가기meantime : 시작시간과 끝 시간을 이용하여 음악 재생 시간을 return 한다parsemelody : melody 에서 \`\`\`target = parsemelody(m)candidates=\[]for i, m in enumerate(musicin

문제 바로가기파일명을 HEAD 알파벳 순(대문자, 소문자 구분 없이), number 숫자 순으로 정렬하는 것.열심히 head, num, tail 을 분리하는 parse 함수를 짰다. 아 re 모듈을 좀 더 공부해야겠다... 여기에서 \\d+ 는 숫자가 하나 이상...

문제 바로가기ls 에 순서대로 때려박고 가져오기

문제 바로가기힌트를 썼다. 어렵다. x/y 를 추가하는 것과 x//y 를 추가하는 것에 큰 시간 차이가 있었다. number는 자연수로 주어주기에 x//y 를 추가하지 않아도 괜찮았다.

print('Hello, {}'.format('World!'))값을 여러 번 사용하는 법print('Hello, {0}{0}'.format('World!'))앞자리를 0으로 채우는 방법'{:03d}'.format(35) 소수점 5자리까지 출력하고, 전체 길이를 9로 출

문제 바로가기아 어렵다.

문제 바로가기인접한 두 개의 풍선을 선택하여 더 큰 값이 적힌 풍선을 터뜨리기단 한 번은 더 작은 값이 적힌 풍선을 터뜨릴 수 있다풍선이 하나 남을 때까지 풍선을 터뜨렸을 때, 최후에 남아있는 것이 가능한 풍선의 개수?일단 가장 작은 값이 적힌 풍선은 무조건 남아있을

rotate: 회전된 열쇠를 return 한다 isMatch : 열쇠와 자물쇠가 맞는 지 확인한다 isMatch 에 lock 을 바로 넣어주었는데 계속 실제 lock 의 값을 변화시키더라. lock.copy() 를 넣어줘도 계속해서 실제 lock 값이 변화하였다.

cur : 현재 방문할 node 들이 들어있다.한번 while 문을 돌 때마다 한 단계를 거친다고 생각했다. while 문 내에서는 다음 노드들의 집합인 new 를 만들어주고, cur 에 들어있는 node 들에 대해서 방문하지 않은 (not in visited) nod

dfs 로 풀려고 했으나 시간 초과로 실패dynamic programming 을 이용하더라.arr\[i] 는 i원의 거스름돈을 주는 경우의 수이다. money 의 각 화폐단위를 이용할 수 있는 경우의 수를 for 문을 돌면서 더해준다. 5원을 예로 들면, 1원을 만드는

문제 바로가기lines 와 bo 에는 기둥과 보의 시작 좌표들을 넣는다. 기둥은 시작좌표가 (x,y) 라면 (x,y+1) 만큼 영향을 끼치고, bo 는 시작 좌표가 (x,y) 라면 (x+1,y) 로 오른쪽 하나만큼 이어진다. 어떻게 저장할 지가 중요하다. 처음에는 배열

배울 점이 많은 코드.오른쪽, 왼쪽으로 가는 걸 다 생각해줘야한다고 생각했는데, 굳이 그럴 필요가 없었다. 모든 점에서 출발하기 때문에 한 방향으로만 생각해주면 됐다! set 에 list나 set을 추가할 수 없다는 게 아쉬웠는데 tuple()로 바꿔주면 set 을 쓸

문제 바로가기처음엔 쉬운 문제인줄 알았는데..! 생각보다 시간 제한이 까다로웠다.dfs 에 dp 까지 추가해야 문제를 풀 수 있었다.nums 에는 문제에서 주어진 각 지점의 높이를 저장하고dots 에는 해당 점에서 끝 점까지 갈 수 있는 경우의 수를 저장한다. 단순히

16236 아기 상어 bojdef distance(cur) : cur(현재위치)에서 다음으로 갈 점의 위치와 거리를 return 한다현재 위치에서 다음에 어느 점으로 가야할 지, 그리고 그 점까지 얼마나 걸리는 지를 확인하기 위한 함수이다. v는 현재 d번 이동한 후

14891 톱니바퀴문제에서 헷갈렷던 점은, 톱니바퀴를 회전하기 전의 톱니바퀴를 비교하여 회전할 지 여부를 결정해야한다는 것. 오른쪽과 왼쪽 각각 회전 가능한 index 까지 nxt 를 증가/감소 시킨 후 해당 톱니바퀴들을 회전시켜줬다.양쪽 톱니바퀴를 모두 회전한 후에

BOJ 2661 골드 4bfs 를 이용하려고 했는데 시간초과가 났다.그래서 일단 가능한 값 중 가장 작은 값을 골라나가면서 visited 에 방문한 것을 저장하고, 수열이 더 만들어지지 않는 상황이 생기면 v의 끝을 지워나갔다. 그 후에는 visited 에 존재하는 것

2638번 치즈: 골드4가장 먼저 chz 와 inair set 을 만들어줬다. inair 은 일단 공기가 존재하는 모든 좌표를 담은 후, (0,0) 에 연결된 점들을 모두 제거해줬다. isMelting(dot) : dot 에 있는 치즈가 현재 녹는 상황(4면 중 2면

BOJ 1806 부분합 골드 4완전탐색이나 파라메트릭 서치를 이용하려고 했을 때 시간초과가 났다.

Union-Find, 크루스칼 알고리즘 이용

14502 연구소 골드 5완전탐색(브루스포스) 문제. 완전탐색을 쓰기 싫어서 고민하다가 시간이 많이 갔는데 완전탐색밖에 방법이 없었다. n, m 이 모두 8 이하니까 최대 8C3 (56) 정돈데 괜히 고민했다. 시간 복잡도 고민하는 것을 습관화해야겠다. 편의를 위해 바

최대한 코드를 간결하게 짜는 것을 연습해야겠다. 내가 보고 생각하기에도 어려운 코드는 실수가 생기기 너무 쉽다. isCrossable 은 배열을 전달받아 건너는 것이 가능한 지 확인한다.

15683 감시 골드5cctv가 8개 이하이기 때문에 모든 가능성을 확인하는 BFS 로 문제풀이를 하였다. watchTop, watchBottom, watchRight, watchLeft 들은 y,x 좌표를 기준으로 위쪽, 아래쪽, 또는 왼쪽 오른쪽에 cctv가 감시할

15684: 사다리 조작 Python 골드4 아 어려웠다. 아 너무 어려웠다..

12865 : 평범한 배낭 골드 5DP 문제 maxvalueperweight 각 weight 조건에 맞는 maxvalue 를 저장한다. maxvalueperweight 의 value 보다 weight 이 클 때에만 그 뒤 검색을 개시한다.

boj 골드 1시간제한이 까다로웠다. Python3으로 통과한 사람이 한 명도 없었다. PyPy3 풀이를 찾아보니 각 빙하가 녹는 시간을 찾고 + 파라메트릭 서치로 찾았다.nxt 에 새롭게 녹은 얼음 좌표들을 넣고 계속해서 얼음을 녹여가서 다른 swan 을 찾을때까지

12015 가장 긴 증가하는 부분 수열 골드 2나무위키(https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4save\[i] : 길이

2536번 버스 갈아타기 : 골드 1buses에는 각 idx에 맞는 bus를 넣어준다 -> 사실 그냥 .append로 넣어도 상관 없다.start와 s는 시작점인 sx, sy 점에서 탑승 가능한 버스를 저장한다. target은 목적지인 dx, dy점에서 탑승 가능한 버

제가 만든 추가 테스트 케이스를 공유합니다.기본적인 풀이법은 BFS입니다.함정 x에 처음 방문하면 x와 연결된 길들의 방향이 바뀝니다. 다시 함정 x에 방문하면 x와 연결된 길들의 방향이 바뀝니다. 길들의 방향은 함정들의 정보를 통해 알 수 있습니다. -> 함정의 정보