메모/알고리즘
-
[Softeer] Java - 통근버스 출발 순서 검증하기메모/알고리즘 2023. 2. 16. 22:28
Softeer 문제에서 주어진 조건을 만족하는 서로 다른 (i, j, k) 순서쌍의 개수를 출력한다. 첫 번째 위치에는 2번 버스, 두 번째 위치에는 3번 버스, 그리고 세 번째 위치에는 1번 버스가 기다 softeer.ai 너무 허탈하고 열 받아서 오랜만에 알고리즘 포스팅 한다... 문제 문제 설명은 위 링크에서 자세하게 확인할 수 있지만 간단하게 요약하면 "스택 정렬을 만들 수 없는 원인의 개수를 찾아라." 이다. 예를 들어서 6, 7, 5 과 같은 순서로 숫자가 있다. 이런 3개의 숫자가 쌍을 이뤘을 때, 가운데 수가 제일 크고 첫 번째 수가 두 번째로 크면 스택 정렬을 할 수 없다. 위와 같은 경우의 수의 개수를 찾는 문제다. 물론 각 숫자는 늘 연속적으로 존재하지는 않는다. 풀이 솔직히 보자마자..
-
[백준] 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과 같은 알..