이아손의 아르고호

문제출처: https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 풀이법: 그냥 생각대로 풀었다 Comment: 1) 이클립스에서 이 코드는 문제없지만 프로그래머스에선 테스트 케이스 통과 못함 (hands가 매개변수라서) 2) String에서 equals 랑 == 연산자 차이 import java.util...

문제 출처: https://www.acmicpc.net/problem/2667 풀이법: 지도 배열의 모든 칸마다 방문하면서 1 값을 찾을때 마다 dfs를 진행한다. Comment: 1) 입력: 배열 정보를 받을땐 string -> char형 배열 -> int형 배열로 변환하였다. 2) 단지 묶음 구분: 재귀함수 특성을 기억하면 제일 먼저 들어간 dfs함수가 끝난 시점 한 그룹에 대한 dfs가 끝난다는 사실을 알 수 있다. 3) dfs 함수 내 칸 이동 구현: 처음엔 if else if 문으로 오른쪽 이동 > 아래쪽 이동 > 왼쪽 이동 > 위쪽 이동 순으로 할려고 했으나 지도 밖 으로 움직일 시에 대한 예외처리를 함께 하던 중 코드가 계속 꼬이는 문제가 발생하였다. -> 이러한 문제는 칸 이동 전에 칸 이..

문제 출처: https://www.acmicpc.net/problem/2606 풀이법: 인접행렬을 이용한 dfs 알고리즘으로 풀었다. Comment: 1) class 이름을 Main으로 하지 않으면 컴파일 에러가 난다. 2) 인접행렬은 사이즈에 + 1 만큼 행, 열을 생성하는게 편리하다. (방문 노드 체크 행렬도 마찬가지) -> 이유? : 행렬의 인덱스는 0으로 시작하는 반면에 코테 문제에서 나오는 그래프에선 0번 노드가 잘 등장하지 않기 때문. 코드: import java.util.*; public class Main { public static int count = 0; public static void main(String[] args) { // TODO Auto-generated method st..

class Solution { public boolean solution(String[] phone_book) { for(int i = 0; i < phone_book.length; i++){ for(int j = 0; j < phone_book.length; j++){ if(i != j && phone_book[j].startsWith(phone_book[i])){ return false; } } } return true; } } 해시를 사용하면서 얻는 이점을 전혀 모르겠다.

import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { String fail = ""; HashMap answer = new HashMap(); int value = 0; for(int i = 0; i< participant.length; i++){ if(answer.containsKey(participant[i])){ value = answer.get(participant[i]); answer.put(participant[i], value + 1); }else{ answer.put(participant[i], 1 ); } } for(int i = 0; i < complet..

1. 탄생 배경 이 알고리즘의 저자인 다익스트라는 1956년 암스테르담에서 ARMAC이라는 새로운 컴퓨터의 성능을 보여주기 위한 적절한 주제를 고민하고 있었다고 한다. 그러던 어느 날 오전에 쇼핑을 하던 중 지쳐서 카페에서 커피를 마시다가 최단 경로 탐색 법을 고민하게 되었고 이 알고리즘을 약 20분(...!) 만에 완성했다고 한다. 2. 이해하기: 다익스트라 알고리즘 2-1. 기본 로직 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 점들까지의 최단 경로를 구한다. 어떠한 원리로 최단 경로를 찾아가는지 직관적으로 이해를 돕기 위해 아래의 예시처럼 가장 기초적인 그래프부터 살펴보겠다. 1) 첫 단계는 현재 노드를 기준으로 나머지 노드들까지의 거리를 계산을 하는 것이다. 인접해 있는 노드들은 해당 거리(..

1. 탄생 배경 Trie는 1959년 René de la Briandais의 라는 논문에서 처음으로 등장하였다. (Trie라는 단어 자체는 2년 후에 만들어졌지만 Trie의 기본 알고리즘은 이 논문이 최초라고 한다) 논문의 내용을 정말 간단하게 요약하자면, 모든 Search의 성능은 주어진 데이터의 크기 (N)가 가장 큰 결정 요소인데 이것을 해결하기 위해 고안된 자료구조이다. 즉, Search 연산에 대한 전체 복잡도를 주어진 데이터 크기와 최대한 상관이 없도록 만들어진 것이다. 하지만 이러한 문제점을 극복하기 위해 HashTable이라는 자료구조도 나오지 않았는가? 그러나 당시 컴퓨터들에게는 Hash 방식을 비롯한 기존 방식들이 가지고 있는 몇 몇 문제점들이 있었다. 1) Hashing의 문제점 Tr..