본문 바로가기

프로그래밍74

[알고리즘] Moore's voting algorithm leetcode의 169. Majority Element 문제를 풀다가 알게된 알고리즘입니다. 이 알고리즘은 처음 들어봐서 공부하고 정리했습니다.  1. 배경문제를 간단하게 요약하면,array 에 (array의 length // 2) 번 넘게 나타나는 원소를 찾는 것입니다. 처음에는 sort를 이용하려고 했는데, O(nlogn) 시간복잡도가 생기고 공간은 O(1) 를 사용하게 됩니다.하지만 문제 맨 마지막 줄에 선형 시간 + 공간 O(1) 만 사용해서 풀 수 있다는 글이 있었습니다.  도저히 모르겠어서 결국 해답을 봤고, Moore's voting 알고리즘을 알게 되었습니다.  2. 알고리즘 이 알고리즘은 stream algorithim 입니다.(데이터 스트림을 처리하는 알고리즘) 배열에 중복되는 데이터.. 2025. 3. 27.
[swea] 4615 재미있는 오셀로 게임 재미있는 문제라서 들고 왔습니다. 1. 해당 방향으로 쭉 탐색하면서 해당 칸 놓는 돌로 변경. 2.1 만약 끝에 같은 돌이 없다면, 다시 원래대로. 2.2 만약 끝에 같은 돌이 있다면, 그대로 유지 dfs를 이용해서 풀었습니다. t = int(input()) directions = [[0,1],[0,-1], [1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]] def dfs(board, y,x, dy, dx, c, n): if y = n or x >= n: return True if board[y][x] == 0: return True if board[y][x] == c and board[y][x] != 0: return False tmp = boa.. 2023. 5. 20.
[프로그래머스] 블록 이동하기 bfs를 이용하여 해결했습니다. bfs에 들어가는 값으로는 [[로봇위치1, 로봇위치2], 시간] 이 들어갑니다. 그리고 위치1의 값은 위치2보다 항상 작습니다. [[0,0],[0,1]] [[0,0],[1,0]] 문제는 다음에 방문할 위치에 대한 정보입니다. 회전에 대해서는 정사각형을 만들어서 처리했습니다. 만약 이 사각형에 1이 있다면 회전을 하지 못한다는 것을 의미합니다. 1이 없고 회전시킨 위치를 방문하지 않았다면, 큐에 (현재 시간+1)과 회전시킨 위치를 넣어줍니다. 방문했는 지 확인하기 위해서 set을 이용했습니다. 문제는 list는 set에 들어갈 수 없기 때문에 tuple로 바꿔서 넣었습니다. 상하좌우는 일반적인 bfs문제와 동일하게 처리했습니다. 큐에서 꺼낸 위치에서 보드의 맨 마지막 위치가.. 2023. 3. 7.
[프로그래머스] 표 병합 이번 문제는 3단계 같지 않은 문제입니다. 단순하게 생각해서 각각의 셀을 그룹으로 지정합니다. 그리고 각 그룹의 값을 저장하고 있는 딕셔너리를 만듭니다. 그래서 업데이트를 할 경우에는 해당 셀의 그룹을 가져와서 딕셔너리의 값을 업데이트합니다. merge는 모든 셀 중에서 merge하고자 하는 그룹에 해당하면, 그룹을 대상 그룹으로 업데이트 합니다. 2500 * 1000 이기 때문에 충분히 가능합니다. unmerge는 그룹에 해당한다면, 새로운 값으로 그룹을 할당해줍니다. 중복되지 않게 하기 위해서 자기 위치에 해당하는 값을 넣어줍니다. dic = {i : "" for i in range(50*50)} board = [[j*50 + i for i in range(50)] for j in range(50)].. 2023. 2. 16.
[프로그래머스] 표현 가능한 이진 트리 이번 문제는 완전탐색에 대한 문제입니다. 일단 포화 이진 트리로 만들고, 탐색을 시작합니다. 루트노드부터 시작해서 제일 왼쪽 리프노트의 부모노드까지 내려옵니다. 이 서브트리가 올바른 트리인 지 확인합니다. 어려운 점은 자식노드나 부모노드 간의 이동이 어려웠습니다. from collections import deque import itertools import math flag = True def solution(numbers): answer = [] for i in numbers: if i == 1: answer.append(1) else: an = ans(dec_to_bin(i)) if an == -1: an =0 answer.append(an) return answer def dec_to_bin(nu.. 2023. 2. 15.
[다익스트라] 백준 9370 이번 문제는 다익스트라를 통해 풀었다. 원래 처음에는 경로를 추적할 수 있도록, 거리를 측정하는 배열에 [이전 노드, 거리] 값을 저장하도록 했었다. 문제는 다익스트라는 해당 노드까지 최단거리로 갈 수 있는 경로가 많은 경우, g와 h를 포함하지 않을 수 있기 때문에 문제가 되었다. 그래서 s -> g -> h -> 목적지, s -> h -> g -> 목적지를 구하기 위해, s ,g, h를 시작점으로 각각 다익스트라 통해 최단 거리를 구한다. import heapq import sys from collections import deque def djk(board, s, n): hq = [] dst = deque([987654321 for _ in range(n+1)]) heapq.heappush(hq, .. 2023. 1. 29.

티스토리툴바