본문 바로가기
반응형

알고리즘

 (136)
[Python] 226. 트리 데칼코마니 leetcode.com/problems/invert-binary-tree/ Invert Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 바이너리 트리를 데칼코마니 시키는 것을 말한다. 좌측과 우측을 바꾸는 문제 재귀적으로 생각해서 현재 트리의 좌측과 우측을 구한다음 그것을 현재 트리의 좌측-우측, 우측-좌측 이렇게 매핑 시켜주면 된다 class Solution: def invertTree(self, root: TreeNode) -> Tre..
[Python] 206. 링크드 리스트 거꾸로 만들기 class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None stk = [] while head != None: stk.append(head.val) head = head.next new_head = ListNode() cur = new_head while stk: cur.val = stk.pop() if stk: cur.next = ListNode() cur = cur.next return new_head 스택을 이용하는 방법이다. 스택에 값을 하나씩 넣고 빼게 되면 가장 나중 것이 처음에 빠지는 원리는 이용하였다. 다음에는 재귀로 풀 수 있는 방법을 고민해봐야겠다.
그래프에서 사이클 찾는 법 해시 테이블 이용 노드를 해시 테이블에 넣고 그 노드가 다시 방문하면 사이클 존재 투 포인터 slow = head fast = head.next slow는 한칸씩 전진, fast는 두칸씩 전진한다 fast가 slow와 만나면 사이클 존재 만나지 않고 fast가 null 혹은 fast.next가 null이라면 사이클 존재 x https://leetcode.com/problems/linked-list-cycle/ Linked List Cycle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next intervi..
[Python] 위상정렬 위상 정렬은 기본적으로 N번 만큼만 수행한다. N개의 원소의 순서를 알아내는 것이기 때문이다. 이를 이용해 알아낼 수 있는 정보들이 있다. 첫번째: 사이클 발생 첫번째로 N번 만큼 수행할 동안 큐안에 0개의 원소가 들어있다면 사이클이 발생했다는 것이다. 그 이유는 위상 정렬을 할 때 indegree를 감소시키는데 이 값이 0일때만 큐 안에 들어간다. 하지만 사이클이 있어 한번 더 진입을 하게되면 큐 안에 값이 들어갈 수 없기 때문이다. 두번째: 순서 불분명 두번째로 큐 안에 2개 이상의 원소가 들어가있다면 순서가 확실하지 않아 여러 순서가 발생할 수 있는 것이다. indegree 값이 0인 값이 여러개가 존재하게 되면 큐 안에 2개 이상의 원소가 들어가게 되는데 이는 동시에 들어간 노드의 순서가 불분명하..
[Python] 블록 이동하기 https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 1. 이해하기 (1,1)에서 시작하여 (N,N)에 도착하는데 걸리는 최소 시간을 구해야 한다. 로봇은 두 칸을 차지한다. 로봇은 회전과 이동이 가능하다. 회전 시 조건에 맞아야 회전이 가능하다. 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어진다. 2. 구현하기 걸리는 최소 시간을 구하기 위해서는 BFS를 이용하여 구현이 가능하다. 그 이유는 회전, 이동 모두 가중치가 1이기 때문..
[Python] 시간초과가 난다면 1. 입출력 속도를 높여본다. import sys input = sys.stdin.readline 2. 파이썬이라서 시간 초과가 나는 것이 아닌지 고민해본다. 자바 혹은 c++로 풀면 통과가 되는 경우가 있다. 예시> https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접� www.acmicpc.net 위의 경우가 아니라면 대부분 로직이 잘못됐다는 이야기 일 것이다. 새로운 알고리즘을 짜 보자
[Python] set 소소한 팁 set안에 값을 넣고 특정 값이 있는지 찾고 싶다면 x in set 이렇게 사용하면 된다. 예시로 set안에 좌표값을 넣고 그 좌표에 도착했는지 여부를 알고싶다면 (x,y) in set 이렇게 쓰면 유용하다.
[SWEA 1798] 범준이의 제주도 여행계획 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4x9oyaCR8DFAUx&categoryId=AV4x9oyaCR8DFAUx&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 이해하기 장소를 방문해서 만족도를 최대로 높이는 경우를 구하는 문제이다. 하루에 최대 9시간까지 사용할 수 있고 9시간 안에 호텔에 도착을 해야한다. 마지막 날이라면 9시간 내에 공항에 도착을 해야 한다. 그때의 최대 만족도와 경로를 구하는 문제이다. 모든 장소를 방문해 보는 완전탐색으로 푸는 문제이다. 2. 구..

티스토리툴바