Carry On Progamming Carry On Progamming

내가 알고리즘을 정말 못푸는 건가싶다. 이 문제 푸는데 3시간 걸렸다. 몇달 뒤에 다시 풀어도 이정도 걸릴 것 같아서 기록해두기. 이 문제는 anagram을 찾는 문제인데, anagram이란 철자 바꾸기 놀이를 뜻하는데, 철자를 재배열해서 다른 문자로 만드는 것이다. 즉, 어떻게 배열되어있든 두 단어를 비교했을 때 알파벳만 맞으면 된다.(순서가 뒤죽박죽이라도) 위의 예시 중 하나를 들자면, ifailuhkqq는 ifa 와 fai는 순서는 다르지만 동일한 알파벳을 가지고 있다. 단일 알파벳이라도 i와 i는 순서를 바꿔도(의미가 없지만) 같다. 내 풀이의 시간복잡도는 O(n^4) 이다. 아주 비효율적인 시간복잡도 같지만, 다 풀고 나서 다른 풀이들도 봤는데 O(n^4)의 시간복잡도를 가지고 있었다. 예시 하..

bfs 공부했던 BFS 슈도코드로 끄적여보기 본사로 출장을 가던 중, 전날 공부했던 BFS를 떠올리며 java로 어떻게 구현할까 슈도 코드 방식으로 끄적여봄. 본사 도착하자마자 붕 뜨는 시간에 얼른 구현해보았는데 잘 돌아갔다. 예쓰! int[][] adjacencyMatrix = new int[][] // if node exist = 1, non exist = 0 Queue queue = new Queue int[] distancePath = new int[adjacency.length] int[] predecessor = new int[adjacency.length] Arrays.fill(distancePath, -1) // -1 means unvisitied node enqueue(시작점) dinst..

해당 알고리즘은 2진수~36진수까지 진법 변환이 가능한 알고리즘이다. 아래 사진에서 보는 것과 같이 구현해낸 알고리즘이다. 나머지를 통해 거꾸로 읽어서 원하는 진수로 변환된 수를 알아낼 수 있다. * 소스 123456789101112131415161718192021222324252627282930313233 public class CardinalConversion { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWr..

덱은 스택과 큐의 특징을 골고루 가지고 있다. First In, First Out도 가능하고, First In, Last Out도 가능하다. 양방향으로 이동이 가능하다. 자바에서 덱을 제공해준다. 덱을 활용해 문제 해결. * 풀이 소스 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 public class Baekjoon10866{ static StringTokenizer st; public static void main(String[] args) throws IOException { Buffe..

풀이 방법은 백준 알고리즘 11866번 문제와 같다. 풀이 방법 보러가기 : Click 내 풀이 방법은 input 값이 올라갈수록 시간이 오래 걸리는 알고리즘이다.(그다지 좋은 알고리즘을 만들어내지 못했다.) 여기 올린 풀이소스는 나 혼자 힘으로 풀어냈던 코드를 올린 것이고, 더 효율적인 알고리즘은 나머지 연산자(%)를 활용해 푼 알고리즘이 메모리면에서나 시간면에서나 더 좋다. * 풀이 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243 public class Baekjoon1158 { static StringTokenizer st; public static void main(String[] args) throw..

List의 원리를 잘 이해하면 풀 수 있는 문제다. LinkedList는 index에 대해 자유로운 편이기 때문에 index 중간에 삽입하고 삭제하기가 쉽다. arrayList는 index 기반이라 list 중간 index가 빠지면 다른 index의 데이터까지 복사해야하는 불상사가 생긴다. 그에 비하면 LinkedList는 index가 아닌 노드와 다음 노드 값만 연결하고 있어서 list 내의 값에 대한 복사가 없다. LinkedList로 넣은 값에 순서에 맞는 index만 계속해서 삭제해주면 된다. ** arrayList를 사용하면 안되는 건 아니다. index 기준이므로 상관없지만, 개념적으로 값의 삽입과 삭제가 빠른 건 LinkedList로 배웠기 때문이다. 원하는 삭제 index보다 배열의 크기가..

- DFS(깊이 우선 탐색) - BFS(너비 우선 탐색) - 피보나치 수열 - LCS(최장 공통부분 수열) - 병합정렬 - 힙정렬 - 카운팅 정렬 - 기수정렬 - 퀵 정렬: Click - 연쇄행렬 최소곱셈 - 메모이제이션 - 에라토스테네스의 체(소수 구하기)

큐의 개념을 공부하기 위한 문제이다. 큐는 스택과 반대되는 개념으로 FIFO(First In, First Out)이다. 먼저 들어간 녀석이 먼저 나오는 것이다. 예를 들어 급식을 받는다고 일렬로 줄을 서있으면 먼저 배식을 받는 사람이 먼저 배식 줄을 나오는 것과 같은 원리! 아래는 이해를 돕기위한 발 그림... 자바에서 라이브러리를 통해 큐를 사용할 수 있지만, 배열을 통해 직접 한 번 만들어보고 싶었다. 일반 배열을 큐처럼 만들기 위해 사이즈(dynamicSize)와 0번째 순서(bottom)를 동적으로 만들었다. 큐에서 pop이 되면 0번째 순서의 다음 순서로 +1로 올라가게 만들고, 사이즈는 -1로 줄어들게 했다. 반대로 push를 하면 사이즈는 +1로 만들었다. 제약조건 중 정수가 들지 않았을 경..