코딩테스트 코딩테스트> 그래프 고급 탐색 ( 다익스트라, 크루스칼) 2021. 8. 29. 다익스트라 10282번 백준 아이디어 다익스트라로 시작점에서 모든 점의 최저 거리가 있는 배열을 만들고 지나가는 점과 가장 긴 거리를 골라서 출력 5719번 백준 아이디어 최단 거리로 나온 결과값은 빼고 거기서 또 최단 거리를 뽑는다. 다익스트라 이중 처리 다익스트라를 점검할 때 이전에 적용이 되었는지 조건문에 추가 최단 거리를 다 구하면 최단 거리 값에서 역순으로 경로를 찾는다. 경로를 찾아가면서 이전에 적용됐다는 표시를 한다. 크루스칼 1774번 백준 아이디어 우주신인지 뭔지 복잡하게 씌여있지만 크루스칼 알고리즘을 사용하면된다. 이 문제의 특징은 이미 연결되어 있는 간선이 있다는 점이다. 그리고 기존은 간선이 있는 그래프를 정렬하여 사용했지만 이번에는 모든 간선을 만들고 정렬하는 방법을 사용했다. 코딩테스트> 그래프 기본 탐색 ( BFS, DFS ) 2021. 7. 20. 백준 1697번 if not 의미는 if not 다음에 False가 오면 실행한다는 뜻이다. 0은 False를 의미하므로 array_list 배열 안 값이 0이면 실행한다는 뜻 이 유형은 BFS 와 DFS 를 약간 변형해서 푼다. 따라서 BFS와 DFS의 구조를 외워야 한다. 핵심은 BFS는 0번째 요소를 뽑고, DFS는 마지막 요소를 뽑는 것 리스트가 오름차순이라면 순서가 뒤에서 앞으로 방향이다. 앞에서 뒤로 하려면 sort로 내림차순으로 정렬하고 마지막 요소를 뽑으면 된다. 2606번 백준 백준 1012번 백준 1325번 코딩테스트> 동적 프로그래밍 2021. 7. 12. 백준 1904번 수열 문제를 풀듯이 점화식을 세워서 푸는 문제 유형이다. 대부분의 문제가 그렇듯 나열을 하고 규칙을 찾아서 풀면 된다. 백준 12865번 처음에는 물건 가치의 최대값을 구하라고 해서 그리디 알고리즘을 이용하는 줄 알았다. 하지만 그리디 알고리즘을 사용하지 말아야 한다. 백준 11053번 백준 9251번 백준 1495번 백준 2655번 내가 쓴 답변 결과는 나오나 비효율의 극치인 것 같고 답이 틀리다고 나옴... 문제 푸는 원리는 같은데 말이지... 넓이 순서로 나열하고 순서를 깨지 않고 거기서 무게 순서대로 뽑는다는 원리는 맞게 접근했으나 최대값을 뽑는 동적프로그래밍을 어떻게 해야 할 지 아이디어가 떠오르지 않았음. 최대값을 가지고 역으로 뽑는 것도 떠오르지 않았음 원리를 이해하고 그걸 .. 코딩테스트> 고급 탐색 알고리즘 2021. 6. 28. 백준 2250번 백준 1939번 이것은 마치 다익스트라와 푸는 방식이 유사하다.. 처리하는 노드를 리스트에 넣고 하나씩 꺼내면서 인접한 노드값을 꺼내 방문한 적이 있는지 확인하고 방문한 적이 없으면 처리하는 리스트에 집어넣는 방식.. 깊이 우선 탐색과 연관되어 있다.. 백준 1927번 최소값을 구하는 것. 물론 sorted 를 이용하여 최소값을 뽑을 수 있지만 heap을 이용하면 쉽게 뽑을 수 있다. 백준 1715번 sorted를 이용하여 key 값에 기준을 잡고 그리디로 뽑을 수 있지만 heap으로 최소값을 뽑을 수 있다. 백준 1766번 위상정렬의 원리를 이용해서 풀면된다.. 부모에서 자식으로 관계를 설정할 때는 배열을 이용하고 자식에서 부모 연결 관계를 확인할 때는 차수를 이용한다. 코딩테스트> 기본 탐색 알고리즘 2021. 6. 22. 백준 1543번 등호 부등호를 잘못써서 틀렸지만 고치니까 맞았다. 백준 1568번 백준 1302번 이렇게 하면 max 함수로 최대값이 나오긴 하는데 문제가 같은 값이 있을 경우이다. 그럴 경우 먼저 나온 값이 뽑힌다. a가 j 보다 알파벳이 앞에 있어도 먼저 들어간 j가 나온다. 위에는 print(bookList)를 임의로 넣어서 테스트해봤다. 해결책은 최대값을 따로 배열에다가 정리하고 sorted( ) 함수를 이용하여 알파벳 순서를 적용하는 것이다. 그런 다음 맨 앞에 값을 뽑으면 된다... 백준 1668 백준 1236 문자열을 각 글자마다 쪼개고 싶다면 list( 문자열 ) 이렇게 안에다가 넣으면 된다. 백준 2100 코딩테스트> 고급 정렬 알고리즘 연습문제 2021. 5. 5. 재귀함수 글을 쓰다가 실수로 날려버렸다. 열심히 썼던 건데.. 눈물난다... 언젠가 다시 써야하는데.. 그게 언제일까.. 백준 2751 병합정렬 퀵정렬 힙정렬으로 풀 수 있다는데 나는 병합정렬을 이용해서 풀었다.. 하지만 역시나 문제풀이 사이트에서 재귀함수를 쓰면 뻗어버린다. 주피터노트북에서는 잘 되는데 .. 위 코드에서 실수 한 것은 number를 2로 나눌 때 /을 두 번 써야한다는 것이다. 한 번만 쓰면 float이 나오기 때문이다. 그래서 //를 하여 정수가 나오도록 해야한다. 위 풀이법은 틀렸다고 나와서 내장함수인 sorted로 답변을 제출했다.. 백준 11004 코딩테스트> 기본 자료 구조와 정렬 연습문제 2021. 4. 16. 백준 2920 문제 이게 머리속에는 풀이가 생각나는데 파이썬 문법이 익숙하지 않아서 처음부터 막혔다.. 바로 list와 map을 이용해서 사용자에게 입력받는 구문을 몰랐다. 다음부터는 알도록 하자. 그랬더니 런타임 에러가 났다.. 왜 문제인가 봤더니 인덱스 에러 그래서 바로 고쳤다. map 함수란.. map()은 반복 가능한 객체(리스트 등)에 대해 각각의 요소들을 지정된 함수로 처리해주는 함수입니다. 백준 2798 문제 나는 이런 문제를 풀 때 그냥 언저리 값 대충 때려잡아서 3장 고른 다음에 값이 비슷해질 때까지 더하거나 빼서 맞춘다. 근데 컴퓨터는 사람이 아니잖아.. 이걸 코딩으로 어떻게 구현해야할 지 생각을 많이했다.. 그러다가 너무 복잡한 거 같아 다르게 생각했다. 컴퓨터는 단순반복을 잘하니까 .. 이전 1 다음
