코딩테스트166 [ 파이썬(python) ] 백준 1926 - 그림(BFS) 📌 백준 1926 - 그림 문제 설명 💡 나의 풀이 BFS를 이용해서 풀었는데, queue에 있는 원소를 pop할 때마다 cnt+=1해주는것을 while문에 쓰지 않고 엉뚱한 곳에 썼다가 답이 안 나와서 헤맸다. 또 중요한것은 함수가 실행될때마다 each_cnt를 1로 초기화 해주자. 아니면 값이 계속 누적된다. 그리고 최대값을 갱신해줄 때 굳이 파라미터로 넣지 않아도 return each_cnt을 해주고 나오는 값과 0부터 max로 비교해주면 나중에 제일 큰 값만 빼낼 수 있다. 가장 간단한 비교방법이니 외워두자. 외부에서 모든 좌표를 하나씩 넣을 때 BFS를 사용하는 조건이 충족되면 cnt+=1 해준다. BFS 함수 내부에서 원소를 pop할때 each_cnt+=1을 해준다. return each_cn.. 2021. 4. 20. [ 파이썬(python) ] 백준 2606 - 바이러스(DFS) 📌 백준 2606 - 바이러스(DFS) 문제 설명 💡 나의 풀이 코드 업에서 풀었던 문제인데, 다시 풀어봤다. DFS를 이용해서 방문하지 않은 노드가 있을 때 cnt를 누적하는 방법으로 구현했다. 중요한 점은 cnt를 전역변수로 사용했기 때문에 파라미터로 전달하지 않았다. import sys input = sys.stdin.readline def dfs(graph, v, visited): global cnt visited[v] = True for i in graph[v]: if not visited[i]: cnt += 1 dfs(graph, i, visited) PC = int(input()) network = int(input()) graph = [[] for _ in range(PC + 1)] vis.. 2021. 4. 19. [ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(BFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS를 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 dfs가 48m/s정도 빨랐다.) 방향 그래프가 없을 때는 간단하게 입력값을 반대로 바꿔서 넣어주면 된다. 이후에 몇 번 노드끼리 이어졌는지를 graph에 입력하면 되는데 무 방향 그래프기때문에 순서가 바뀌어도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. from collections import deque import sys input = sys.stdin.readline def bfs(graph, start, visited): # BFS implementation queu.. 2021. 4. 19. [ 파이썬(python) ] 백준 2468 - 안전 영역 📌 백준 2468 - 안전 영역 문제 설명 💡 나의 풀이 문제를 이해하는 데는 어렵지 않았지만, 구현하는데 나름대로 어려웠던 문제였다. 아직 구현 실력이 뛰어나지 않아서 그런 것 같다. N의 최대 범위가 100 * 100이어서 시간 복잡도가 O(N^3)이어도 시간초과가 나지 않을 것이라고 판단했는데, 같은 지역에서 내리는 비의 양에 따른 모든 경우를 조사해야 하기 때문에 이중 반복문에서 삼중 반복문으로 늘어났다. 모든 높이를 조사할때는 입력값 중 가장 작은 값부터 가장 큰 값을 범위로 잡았다. 여기서 pythonic코드를 배웠는데 2차원의 배열에서 min, max값을 찾을 때 map함수를 사용하면 간단하게 출력할 수 있다. 반복문 안에서 가장 큰 값의 범위를 설정할 때는 +1을 해주자 아니면 오답 판정 .. 2021. 4. 19. [ 프로그래머스 ] 월간 코드 챌린지 시즌2 1차 대회 후기 ✏️ 서론 이 글을 작성하는 이유는 내가 취업준비를 하면서 이런 대회도 참가했었지..라고 남기고 싶어서이다. 내가 본격적으로 코딩테스트 공부를 한지 약 3개월 정도가 되었고(12월 22일 월요일부터 시작), 그동안 얼마나 공부했는지 자가진단?을 하기 위해 시험을 봤다. 처음 시작할 때 알고리즘의 ' 알 '자도 몰랐고, 내 실력으로 알고리즘 대회를 나갈 수 있는 건가?! 했는데, 대회를 나가기 위해 신청하기 버튼을 누른 게 신기했다. 시험을 보기전에는 그냥 어떤 문제 유형이 나오는지 확인만 하고, 편한 마음으로 임해야지라고 생각을 했다. 그러다가 알고리즘 오픈 채팅방에 다른 사람들이 하는 대화를 보다 어떤 사람들은 이 대회를 위해 많은 시간을 투자했다고 하는 글을 봤다. 나는 문제유형만 살펴보려고 참가했는.. 2021. 4. 18. 이전 1 ··· 20 21 22 23 24 25 26 ··· 34 다음
