728x90 반응형 알고리즘16 [백준/연결리스트/JS] 거울냥이는 죽어서 거울을 남긴다 문제 설명 16226번: 거울냥이는 죽어서 거울을 남긴다 격자판으로 이루어진 디디몬 어드벤쳐의 어느 섬. 그 곳에는 거울냥이들이 모여 살고 있다. 거울냥이들의 생태계를 조사하던 디디는 충격적인 사실을 알게 되었다. 거울냥이들은 닿는 생명체를 www.acmicpc.net 거울: 거울냥이의 하단, 냥이가 죽어도 거울은 남음, 거울 있으면 빔 통과하지 못함 (1,1)부터 시작 빔은 상하좌우 발사 거울냥이가 사라지면 자기 차례와도 빔 쏘지 못함 입력값: 거울냥이 마릿수, 빔 쏘는 순서대로 거울냥이 위치 출력값: 살아남은 거울냥이 갯수 시간 복잡도 시간 초과도 났고, 정답을 확인해보니 방향성도 틀렸다. 알고리즘 설계 처음 설계 방식 - 틀린 방식 1. 2차원 배열 생성 2. 거울 위치 구하기 => mirror로 .. 2023. 7. 6. 자료구조 - 배열 1. 읽기 1단계로 배열에서 값을 찾을 수 있다. 2. 검색 값이 어떤 인덱스에 있는지 찾는 것이 검색이다. 선형 검색(한 번에 한 셀씩 확인하는 방법)의 경우 N개의 셀로 이루어진 배열은 최대 N 단계가 소요된다. 3. 삽입 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다. 배열을 할당할 때 항상 배열의 크기를 기록하기 때문이다. 맨 뒤에 데이터를 삽입하는 경우 => 1단계 그 외(N개의 원소 전부 이동 + 실제 삽입 단계) => N + 1 단계 4. 삭제 최대 N단계(삭제 + 데이터 이동) 질문이나 잘못된 점은 댓글로 남겨주세요 :)💖 2023. 7. 5. [JS] 순열, 조합 (재귀) 순열과 조합을 코드로 작성하기 위해서는 재귀에 대해서 어느정도 코드를 작성할 줄 알아야 한다. 내가 생각한 재귀 코드를 작성하는 꿀팁은 아래와 같다. 알고리즘 초보라서 이러한 방식을 차용하고 있는데 다른 꿀팁이 있다면 알려주세요.. 1. 가장 쉬운 1항의 값으로 코드를 작성한다. 2. 2항 값으로 코드를 작성하고, 이때 재귀 종료 조건도 같이 생각한다. 3. 완성된 코드로 1항을 다시 테스트한다. 4. 최종적으로 3항을 테스트 하며 코드를 수정한다. 조합 조합은 순서를 상관하지 않는다. 즉, [1, 2, 3]과 [3, 2, 1] 은 순서가 바뀌었지만 같은 구성이기 때문에 하나의 조합으로 취급된다. function combination(array, cnt) { let result = []; for (let.. 2023. 4. 28. [프로그래머스-문자열 다루기 기본] 지수 표기법, 그게 뭔데? 프로그래머스 문제를 풀면서 엄청나게 간단한 문제인데 모든 테스트가 통과되지 않았다. // 테스트 미통과 코드 function solution(s) { if ((!isNaN(s) && s.length === 4) || (!isNaN(s) && s.length === 6)) return true; else return false; } 그 이유는 바로 지수 표기법(e) 때문이였다. 문제는 매우 간단하다. 만약 문자열이 모두 숫자로 구성되어 있다면 true를 리턴하고, 그렇지 않다면 false를 리턴해주면 되었다. 하지만, 여기서 문제점은 문자열이 "3e10"처럼 지수 표기법으로 표현되었을 경우이다. 대개 프로그래밍 언어에서 실수를 표기할 때 지수 표기법을 지원한다. 예를 들어 5e3은 5 * 1000을, -4.. 2023. 4. 19. 다익스트라(Dijkstra) 알고리즘 - 자바스크립트 코드 예제 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 참고로 거리가 양수일 때만 사용할 수 있다. 다익스트라 알고리즘은 다이나믹 프로그래밍 문제이기도 하는데, 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다익스트라 알고리즘은 그래프와, 우선순위 큐(이진 힙 버전) 개념을 알고 있어야 한다. 작동과정 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 거리을 저장한다. 3. 방문하지 않은 노드 중에서 가장 거리가 작은 노드를 선택한다. 4. 해당 노드를 거.. 2023. 3. 31. 이전 1 2 3 4 다음 728x90 반응형
