알고리즘 (79) 썸네일형 리스트형 [프로그래머스]Lv3. 합승 택시요금(Python) https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 특정 도시 간의 최소 요금을 계산하는 문제 특정 도시 간이므로 플로이드 와샬을 사용하는 건 기억이 났는데 코드를 기억에서 지워버렸나보다.. 반복문이 3겹이었던 기억이 난다. 스스로를 반성하게되는 모먼트.. 알고리즘을 복습하고 다시 접근..!! 알고리즘의 적용과 생각의 흐름 1. 무한대의 값으로 그래프를 초기화 2. 그래프의 대각선 요소는 자기 자신으로 가는 요금이므로 당연하게 0으로 초.. [프로그래머스]Lv2. 행렬 테두리 회전하기(Python) https://school.programmers.co.kr/learn/courses/30/lessons/77485 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 구하려는 것은 각 회전들이 일어난 후에 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담는 것이다. 하지만 이를 구하기 전에는 우선 회전을 제대로 시켜야한다. 접근은 하였으나 너무 시간이 오바된 것 같아 멈추었다.(코드1까지 작성 완) (첫 시도) 1. 우선 배열을 (rows+1) * (columns+1)만큼 선언한 후에 다 0으로 만든 후 (1, 1)에서 .. [프로그래머스]Lv1. 바탕화면 정리(Python) https://school.programmers.co.kr/learn/courses/30/lessons/161990 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 솔직히 그림 하나만 그려봐도 바로 풀 수 있는 쉬운 문제.. 하지만 난 30분 걸림^^ 생각의 흐름 1. wallpaper은 일차원 배열이므로 이를 문자로 분리해서 graph라는 이차원 배열에 저장 2. 각 #의 위치를 저장할 빈 리스트 할당 후 graph의 인덱스 i, j로 표현하면 location[i][j] => i는 행, j는 열 3. 교차하는 선을 쫙쫙 그어보면, 가장 작은 [.. [프로그래머스]Lv2. 문자열 압축(Python) https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 이전에 답을 보고 작성했지만 직접 손으로 써보지 않아 애매하게 이해하고 끝낸 문항.. 이번엔 제대로 끝내자!! 문제..!! 1. 사실 문자열을 자르는 범위가 1부터 시작인 건 쉽게 알 수 있지만 최대를 구하는 것이 문제였다. 2. aaabbb를 생각하면 1개 단위로 자르면 3a3b(=4), 3개 단위로 자르면 aaabbb(=6)이므로 큰 단위로 압축한다고 해서 더 짧은 문자열은 아니다... 세그먼트 트리(Segment Tree) & [백준]2042 구간합(Python) 개념 및 특징 완전 이진 트리를 기반으로, 각 노드가 구간의 정보(구간합, 구간의 최솟값 등에 대한)를 저장하고 있는 자료구조 리프 노드들은 길이가 1인 각각의 구간을 소유 부모 노드는 자신의 자식 노드들의 구간의 합 소유 => 루트 노드는 전체 구간을 포함 모든 구간은 연속적 시간 복잡도 및 공간 복잡도 원하는 구간합을 구하고자 한다면, 시간 복잡도: O(logN) => 장점 공간 복잡도: 메모리가 많이 필요 => 구간합을 모두 저장해야하므로 => 단점 구현 1. Top → Down : 재귀 사용 ✔ 2. Bottom → Up : For 반복문 사용, 코드 구현 간편 초기화 def init(start, end, node): if start == end: # 리프 노드 tree[node] = nums[s.. [백준]11437 LCA(Python) https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 접근 LCA(Lowest Common Ancestor): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 ♣ 동작 방식 모든 노드에 대한 깊이(depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이가 동일하도록 거슬러 올라간다. (첫 번째 while문) 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. (두 번째 .. [프로그래머스]Lv3. 표현 가능한 이진트리(Python) https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 처음에 문제 이해에 다소 어려움을 겪었지만 이진트리를 그려보고 중위순회(L->루트->R)로 노드가 존재하면 1 존재하지 않으면 0 이렇게 읽은 후 이진수로 나열한 후 십진수로 변환하면 해당 숫자를 알아낼 수 있다. 만약 이진트리로 해당 숫자를 나타낼 수 있으면 1을 리턴, 그렇지 않으면 0을 리턴 7 => 111 42 => 0101010 3 => 11 => 011 (O) 5 => 10.. [프로그래머스]Lv2. 혼자 하는 틱택토(Python) https://school.programmers.co.kr/learn/courses/30/lessons/160585 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 정상적이거나 비정상적인 경우를 분리해서 생각하기 힘들었다. 그래서 그냥 그려보고 주어진 테케 3개를 일반화하여 내가 알아낸 부분, 구현할 수 있는 부분(함수)을 먼저 고민해 보았다. 쥐어짜낸 사고의 흐름...정리 이기는 경우(가로3+세로3+대각선2)를 체크하는 함수 만들기 어떤 자료구조를 사용할지 고민 => O와 X를 카운트해서 딕셔너리에 키와 값 형태로 저장 시도 정상/비정상적인 경.. 이전 1 2 3 4 5 6 7 ··· 10 다음
