본문 바로가기

알고리즘133

[백준 15650- N과 M(2)][파이썬]-16일차 https://www.acmicpc.net/problem/15650 https://blue-coding-story.tistory.com/99 N과 M(1) 문제 풀이에서 문제의 로직에 대해서는 다 설명되어 있다. 여기서는 오름차순이라는 조건만 추가된거고, If 문에 data==sorted(data)를 추가해서 오름차순으로 정렬된 쌍만 출력하게 만들었다 2022. 6. 10.
[백준 15649- N과 M(1)][파이썬]-16일차 https://www.acmicpc.net/problem/15649 Key point: dfs 로직으로 접근하는 것 1. dfs 로직을 풀어서 보면 n=4 m=2 1. def dfs() 호출 2. if문에 걸리지않음 len(data)=0이라 3. for문 호출 i=1 부터 1은 data에 없으니까 추가해주고 dfs()를 또 호출 4. 두번째 dfs()호출 5. if문에 걸리지 x len(data)=1 이라 6. for문 호출 i=1 은 data에 있으니까 i=2 -> data에 추가 dfs()를 또 호출 7. if 문에 걸리니까 1,2 print한거 물고, pop으로 data를 다시 []로 만들어줌 이 로직을 계속 처리 2022. 6. 10.
[DFS 알고리즘][파이썬]-16일차 1. DFS 알고리즘의 정의 Depth-First Search, 깊이 우선 탐색. 탐색 하는 기준은 깊이가 우선이 된다 DFS를 공부할 때 자주 보게 되는 그림인데, 숫자가 써져있는 동그라미 자체를 'node' 라고 한다. 이 알고리즘을 이해하려면, 스택,큐, 재귀함수의 개념들에 대해서는 미리 공부를 해두어야 한다. 2. DFS 알고리즘의 로직 이 알고리즘은 무조건 깊게 들어간다. 계속 깊게 들어가고 갈 곳이 없으면 한 칸 위로 올라와서 더 깊게 갈 길이 있나? 하고 찾고, 있으면 그 길을 또 쭉 깊게 간다. 만약 없다면, 또 한 칸을 위로 올라가서 같은 로직을 반복한다. 이 코드를 말로 표현해보자. 1. 28번에서 dfs 코드를 실행 2. visited[1]=True 가 된다 3. print(1) en.. 2022. 6. 10.
[백준 2108번- 통계학][파이썬]-16일차 https://www.acmicpc.net/problem/2108 KEY POINT: 최빈값 Counter -> 각각 요소 하나하나별로 몇번씩 나왔는지 count 해주고, 자동으로 크기 순으로 정렬된다 두 번째로 작은 수를 출력하라고 했으니까, 앞 2개만 비교해서, 로직을 진행해주면 된다 단순해보이지만 여러 디테일한 부분을 요한 문제다. 생각보다 까다롭거나 시간이 많이 걸릴 수도 있겠다 Counter를 안 쓰거나 sys를 안쓰면 시간초과납니다 2022. 6. 10.
[헷갈리는 문법 정리][while :/ round][파이썬] -15일차 알고리즘 문제를 풀면서 개념이 2%씩 부족하다는 느낌이 들었고, 다른 사람들의 코드를 보고 참조할 때도 어려움이 있다.\ 1. while while 뒤에는 조건이 오고 : 가 오게 되는데, while list: 아니면 while len(list): 이렇게 오는 경우가 있었다. while 뒤에 condition 이 오면, True로 간주하고, 무한루프가 돌게 된다 그래서, while 문 밑에 break를 걸어주게 되는데, while len(list): 는 while 문 내부에서 list의 원소를 지우거나 해서 len(list)>=1과 같은 의미다. 그래서 while True: 로 접근하고 내부에서 if len(list)==0: break 와 같이 끊어줄 수 있었다 while list: 도 마찬가지고 lis.. 2022. 6. 9.
[프로그래머스- 소수 찾기][파이썬]-15일차 https://programmers.co.kr/learn/courses/30/lessons/42839 --시간 초과 코드 -- 정답 코드 key point: permutations, 소수 로직에서 제곱근으로 시간 초과 해결하기 1. permutations 로 모든 경우의 수 구하기 모든 경우의 수를 구하고 ''.join( )으로 깔끔하게 구하고, sum(data,[]) 로 2차원 -> 1차원으로 바꾸고, 각 요소들에 int로 바꿔줌 map을 이용해서! 2. 소수 로직 원래는 부르트포스로 2부터 target 숫자 -1 까지 탐색하는 로직을 사용했는데, 시간 초과가 났다 ex) 9 1 x 9 =9 3 x 3=9 9 x 1=9 9의 소수 => 1,3,9 9의 제곱근=3 만약 3까지 돌았는데도 나눠지지 않는다 .. 2022. 6. 9.
[프로그래머스- 기능개발풀이][파이썬]-15일차 https://programmers.co.kr/learn/courses/30/lessons/42586 --오류 코드(정답에서 정답률이 50%가 나옴) -- 정답 코드 여러개의 for문을 돌리지 않고, 스택/큐 유형임을 이용해서 계속 pop을 해주면서 len을 줄여가고, len이 0보다 클 경우에만 계속 반복하게 하여, 다 pop 되면 자동으로 끝내는 로직 선택! time이라는 변수를 설정해서 time에 따라 증가하게 설정하고, 100보다 크다면 pop하고 cnt를 올린다 -> 그럼 저절로 앞선 인덱스가 100이 아니라 출시되지 못한 인덱스들도 저절로 계산된다 2022. 6. 9.
[프로그래머스- 프린터][파이썬]-14일차 https://programmers.co.kr/learn/courses/30/lessons/42587 --풀이 key point: deque, enumerate, while 로직 유형: 스택/ 큐 유형 1. deque 리스트의 앞 뒤의 요소들을 다루는 문제이기 때문에, deque로 접근! 2. enumerarte index와 원소에 동시에 접근할 수 있는 방법 for x in enumerate(['1','2','3']): print(x) -> (0,'1') (1.'2') (2,'3') 이 문제에서는 0, 1 ,2 처럼 생성되는 인덱스 순서를 location에 매칭하는데 사용, 원소 번호를 max값과 비교하는게 사용 3. while 로직 좌측의 아이템부터 뽑아서 if 가장 큰게 아니라면: 다시 뒤로 보내고.. 2022. 6. 8.
[1주일 복습][파이썬]-14일차 복습 1. 딕셔너리 사용/ from collections import defaultdict https://blue-coding-story.tistory.com/52 defaultdic은 ()안에 지정해둔 '디폴트' 값으로 value를 지정하지 않은 키 값의 밸류를 채워주는 것이다 본래의 dictionary에서는 value 값 없이 key를 호출하면 오류가 뜨는데, defaultdict은 굳이 필요 없는 값까지 for문으로 처리를 해주어야 하는 번거로움이 있어서, 이를 해결해줄 수 있다! 필요한 값들만 딕셔너리에서 골라 쓰고 싶을 때 사용해보자 -> https://dongdongfather.tistory.com/69 참조 2. set 형태 https://blue-coding-story.tistory.com/56.. 2022. 6. 8.
[프로그래머스- 124나라의 숫자][파이썬] -13일차 https://programmers.co.kr/learn/courses/30/lessons/12899 [1,2,4] 리스트를 만들어두고 리스트를 뺑뺑이 돌려야지! 라는 접근을 했지만, 2자리가 넘어가는 로직을 처리하지 못해서 실패해버렸다 key point: while문으로 접근(n을 계속 빼면서), 자리수가 커지는 로직 처리 1. key point 먼저, while의 기준을 1이상으로 두고, 즉 1보다 작아지면 while문을 종료하게 설정한다. n에 1을 빼고, %3으로 한 값을 인덱스로 두고 계속 뺑뻉이를 돌리는 식이다 ex) n=3 -> (n-1) %3 = 2 -> nation-124[2]= 4 여기서 포인트는 2자리가 넘어가는, 즉 3진법으로 생각하면 0을 처리하는 방식이었다. 위의 로직대로라면 n.. 2022. 6. 7.
[백준- 1436 영화감독 숌][파이썬] -13일차 https://www.acmicpc.net/problem/1436 key point: while문으로 접근, 666을 str형으로 접근 -부르트포스 1. while 문 for문으로 접근하기엔 range 범위를 지정하기 힘들었고, 무한으로 돌리면서 원하는 조건이 나왔을 때를 노리자는 마인드로 접근함 2. str형 이 문제의 가장 키포인트였다. 666이 나오는 조건을 int형이 아닌 str형으로 생각을 돌리고, str형에 if something in str: 라는 형을 떠올렸고, 작은 수부터 모든 수를 돌리다가 666이 나오는 것마다 data에 더해주면, 별 다른 규칙을 주지 않아도 가장 작은 수부터 666이 들어간 숫자대로 정렬이 될것이고, 'n번째로 작은 종말의 숫자'가 되는 것이다! 만약 while에서.. 2022. 6. 7.
[프로그래머스- 예상 대진표][파이썬] -13일차 https://programmers.co.kr/learn/courses/30/lessons/12985 --잘못된 코드 실패 이유: if len ~ 부분에서 볼 수 있는 것 처럼, 8->4 는 되는데 4->2로 좁혀서 원하는 대진을 만나게 할 수가 없다 --> 뭔가 새로운 규칙이 있을 것 같아서 고민 후 다른 사람 코드를 참조했다 --풀이 번호(player 번호) 몫 나머지 합 1 1//2=0 1%2=1 1 2 2//2=1 2%2=0 1 3 3//2=1 3%2=1 2 4 4//2=2 4%2=0 2 5 5//2=2 5%2=1 3 6 6//2=3 6%2=0 3 7 7//2=3 7%2=1 4 8 8//2=4 8%2=0 4 1번, 2번은 다음 라운드에서 1, 3번, 4번은 다음 라운드에서 2, 5번, 6번은 다음.. 2022. 6. 7.

티스토리툴바