메모
-
[백준] Java - 줄 세우기메모/알고리즘 2022. 6. 1. 23:52
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 백준의 위상정렬 문제 줄 세우기의 자바 풀이다. 위와 같이 순서가 정해져 있고 사이클이 없는 그래프를 정렬하는 알고리즘이 위상정렬이다. "진입 차수"와 "인접 리스트"를 통해서 문제를 해결할 수 있었다. 위의 그림에서 6을 보면 4와 5로부터 진입하는 것을 볼 수 있다. 2개의 노드가 6으로 진입하므로 진입 차수는 2이다. 반대로 1이나 2는 진입차수가 0이다. 인접리스트를 통해 연결된 다음 노드를 저장하고 진입차수가 ..
-
[프로그래머스] Python - 거리두기 확인하기메모/알고리즘 2022. 5. 10. 20:10
코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 프로그래머스 레벨2 문제로 카카오 인턴십 코딩테스트 출제 문제다. 주어진 리스트에서 사람들이 거리두기를 지키는지 확인하면 된다. 이 문제의 경우 BFS-FloodFill로 해결할 수 있었다. ..
-
[백준] Java - 미로 탐색메모/알고리즘 2022. 4. 27. 23:01
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1 9 10 11 12 2 8 12 3 7 13 14 4 5 6 14 15 정말 쉬운 BFS 문제이자 FloodFill 알고리즘을 사용하는 문제이다. 파이썬으로 코테를 준비하다가 자바를 새로 준비해보려니 자바 자체의 문법을 이용하는게 좀 오래 걸렸다. 1, 1의 좌표에서 n, m 좌표까지의 최단 거리를 출력하면 된다. 기본적으로 이동할 수 있는 위치를 표시하는 배열과 방문 여부를 확인하는 배열을 입력 값의 크기만큼 할당하고 시작한다. 위의 표 처럼 다음 이동할 위치에는 현재 위치의 값에 1을 ..
-
[백준] Python - 알파벳메모/알고리즘 2022. 4. 13. 10:41
1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백준의 그래프 탐색 문제 알파벳이다. 이 문제는 DFS와 BFS 두 가지 방법으로 접근했다. DFS 같은 경우는 재귀를 사용하여 visited 집합에 방문 여부를 저장하는 방식을 사용했다. DFS와 BFS가 모두 인접 행렬/인접 리스트 각각에서 시간 복잡도가 같은 걸로 알고 있는데 DFS 방식은 PyPy3로 해결할 수 있었고 Python3로는 시간초과가 발생했다. BFS를 사용한 방식은 조금의 변형이 있었다. 일반적으로 우리는 FloodFill과 같은 알..
-
[백준] Python - 바이러스메모/알고리즘 2022. 4. 11. 23:29
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 백준의 그래프 문제 바이러스다. 1번 PC와 네트워크로 연결된 PC들이 주어지고 1번을 제외한 바이러스로 감염시킬 수 있는 PC의 수를 세는 문제이다. DFS나 Union-Find를 사용하면 풀 수 있을 것이라 생각했고 DFS를 사용해서 풀 수 있었다. for i in range(1, c+1): #다음 이동할 컴퓨터 if G[v][i] and visited[i] == 0: # 네트워크 연결이 되어 있는지, 방문한 적이 있는지 visited[i] = 1 infect +..