메모/알고리즘
-
[백준] Python - 음식물 피하기메모/알고리즘 2022. 3. 25. 15:11
1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net FloodFill 알고리즘을 공부해보려고 문제 몇 개를 풀기로 했다. 새로운 알고리즘은 아니고 기존의 DFS/BFS 등을 통해서 풀 수 있는 쉬운 문제였다. 2차원 배열을 생성해서 각 좌표 별 정보를 저장한다. 현재 좌표 기준으로 상하좌우 좌표 중 2차원 배열의 범위 내에 있으면서 음식물이 존재한다면 한 덩어리로 간주하고 Deque에 추가한다. 기존의 BFS를 해결할 수 있는 방법을 통해서 가장 큰 덩어리의 사이즈를 구하..
-
[백준] Python - 집합의 표현메모/알고리즘 2022. 3. 24. 13:10
1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net DisJoint Set과 Union-Find에 대해 공부하기 위해서 새로 문제를 선택했다. DisJoint Set은 서로소 집합 또는 분리 집합이라고 한다. 자식이 자신의 부모를 가리키는 형태로 존재하고 집합 간의 교집합은 존재하지 않는다. 이 문제의 경우 Union과 Find를 구현하는 기본적인 문제이다. 입력으로 주어진 값에 따라 합집합을 수행할 것인지 값을 찾을 것인지 선택한다. Union의 경우 합치려는 두 대상의..
-
[프로그래머스] Python - 네트워크메모/알고리즘 2022. 2. 14. 16:20
코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 프로그래머스의 DFS/BFS 레벨3 문제다. 네트워크 노드의 개수와 각 노드가 연결된 노드의 정보가 주어지면 총 네트워크의 개수가 몇 개 인지 확인해야 한다. 나는 우선 위 그림 처럼 가상의 Root를 주고 시작했다. Root로부터 깊이 우선 탐색을 수행한다. 접근하는 모든 노드의 인덱스를 키로 딕셔너리에 저장하고 현재의 탐색의 시작 노드 번호를 값으로 추가한다. 첫번째 경우에서는 1번 노드에 접근하고 자기 자신을 제외한 연결된 모든 노드를 탐색한다. 1번..
-
[프로그래머스] Python - 타겟 넘버메모/알고리즘 2022. 2. 14. 16:07
코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 프로그래머스의 DFS/BFS 레벨2 문제다. 숫자들이 리스트로 주어지고 각 숫자들을 서로 더하거나 뺀 결과가 타겟과 같은 경우가 몇 개 인지 확인하는 문제다. # target is 3 numbers = [1,1,1,1,1] -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 여러 경우의 수 중 위와 같이 타겟인 값을 찾아야 한다. 나는 DFS를 이용해서 풀었..
-
[프로그래머스] Python - 가장 큰 수메모/알고리즘 2022. 2. 3. 00:33
코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 프로그래머스의 정렬 레벨2 문제다. 사전식 정렬을 이용하는데 반례가 존재한다. "30" ,"3" # 답 "330" # 반례 "303" 위와 같은 두 수를 문제의 의도대로라면 큰 수가 앞에 와야하는데 사전식 정렬을 이용하면 "30"이 "3"보다 앞에 오게 된다. 이 문제 해결을 위해 각 값에 3을 곱했다. 3을 곱한 이유는 천의 자리의 조건을 맞추기 위해서다. "3" -> "333" "30" -> "..