알고리즘
-
투 포인터 알고리즘알고리즘/알고리즘 2021. 1. 20. 18:13
시간이 없어 상당히 날림으로 썼으며, 생각나면 수정할 예정 programmers.co.kr/learn/courses/30/lessons/67258 투 포인터 알고리즘 배열에 시작점/끝점 포인터를 설정하고 포인터들을 이동시켜가면서 부분 배열을 비교하며 원하는 결과를 도출한다. 백준2003 - 수들의 합2 문제 (www.acmicpc.net/problem/2003) N개의 수로 이루어진 수열 A에서 A[i]~A[j]의 합이 M이 되는 모든 경우의 수를 구하는 문제다. 즉 부분 수열이 M이 되는 모든 경우의 수를 구하는 것이다. 가장 쉽게 생각할 수 있는 것은 3중 for문을 사용하는 것이다. 모든 수열의 크기에 대해 시작점을 바꿔가며 전부 선형으로 비교해보는 것이다. // 초기 입력 int n = scann..
-
(java) DFS로 순열 구하기알고리즘/알고리즘 2021. 1. 19. 14:38
DFS(Depth First Search)를 사용해서 순열 만들기 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제를 해결하던 중 [+. -. *] 을 포함한 모든 경우의 수가 필요했다. 그래서 DFS를 이용한 순열을 구현해보았다. 아래 두 필드는 클래스(전역) 필드이다. ArrayList permutedOps = new ArrayList(); // 기호들을 담고 있는 리스트를 만들어야 하기 때문에 이중..
-
위상정렬 (Topological Sorting) (백준 3665 최종순위)알고리즘/알고리즘 2021. 1. 15. 10:37
순위를 찾거나, 선수과목(prerequiste) 구하기등 순서가 중요할 때 사용할 수 있다. 백준 3665 최종순위는 위상정렬을 사용해 풀 수 있다. 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬이란? 방향 그래프에 존재하는 정점들의 순서를 구하는 알고리즘이다. 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 순서를 구할 때 선행조건이 지켜져야 한다. (A를 하기 위해 B가 선행되야 한다 등의 조건들) 그러나 최종 순위처럼 한 가지 결과를 원할 때는 조건을 걸어서 2개 이상의 결과가..
-
Queue (큐)알고리즘/자료구조 2020. 12. 30. 00:24
Queue FIFO(First In First Out, 선입선출) 구조를 가지고 있는 자료구조다. 매표소에서 표를 예매하는 것과 같다. 매표소에 줄을 섰을 때, 먼저 온 사람이 앞에 서서 먼저 표를 구매하고 빠져나간다. 나중에 온 사람은 앞에 사람들이 빠질 때 까지 기다렸다가 자기 차례가 오면 구매하고 빠져나간다. 큐에 데이터를 넣는 행위를 enqueue라고 한다. 큐에서 데이터를 꺼내는 행위를 dequeue라고 한다. 두가지 자료구조를 활용해서 큐를 구현했다. 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다. 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다. ListNode로 구현했을 땐 큐 크기 제한이 없다. 테스트코드 포함 전체 코드 ..
-
Stack (스택)알고리즘/자료구조 2020. 12. 29. 23:32
Stack LIFO(Last In First Out) 구조를 가진 자료구조다. 말그대로 나중에 들어온 데이터가 먼저 나간다. 먼저 들어온 데이터가 가장 아래에 위치한다. 아래있는 데이터를 꺼내려면 그 위에 있는 데이터를 모두 꺼내야 한다. 스택에 데이터를 넣는 행위를 push 이라고 한다. 스택에서 데이터를 꺼내는 행위를 pop 이라고 한다. 두가지 자료구조를 활용해서 스택을 구현했다. 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다. 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다. ListNode로 구현했을 땐 스택 크기 제한이 없다. 구현1 (int 배열 사용) 테스트코드 포함 전체 코드 링크 package com.example.wee..
-
Linked List (연결 리스트)알고리즘/자료구조 2020. 12. 29. 21:26
Linked List 리스트 자료구조는 중복 저장을 허용하며 데이터를 나란히 저장한다. 자바에는 리스트 자료구조를 정의해놓은 List컬렉션이 있다. (인터페이스) 객체를 인덱스로 관리하여 객체를 삽입하면 인덱스가 자동으로 부여된다. 그래서 인덱스로 객체에 검색, 삭제가 가능하다. 객체를 직접 저장하고 있지 않고 객체의 주소를 가지고 있다. null도 저장이 가능하다. (아무것도 참조하지 않는 상태) 구현체로 ArrayList, LinkedList, Vector 등이 있다. LinkedList(연결 리스트)는 List 인터페이스의 구현체로 메모리의 동적할당을 기반으로 구현된 리스트다. LinkedList의 모든 노드는 인접 노드를 참조해서 체인처럼 관리한다. 노드를 리스트의 중간에 삽입하여도 인접한 노드들..
-
[백준] 11003 최솟값 찾기알고리즘/백준 문제 2020. 12. 25. 16:32
📘 풀이한 문제 백준 11103 최솟값 찾기 ⭐ 문제에서 주로 사용한 알고리즘 슬라이딩 윈도우 📜 대략적인 코드 설명 첫줄에 입력 숫자의 개수(N)와 인도우 크기(L)를 입력받습니다. 둘째 줄에 숫자를 입력받습니다. deque에는 숫자의 인덱스를 저장합니다. 반복문 (0~N) i번째 deque 마지막값이 입력숫자보다 큰 것을 모두 제거합니다. 제거가 끝나고, deque의 맨 앞숫자가 윈도우 안에 포함되는지 확인하고 벗어나면 지웁니다. 맨 앞 숫자를 정답 문자열에 추가합니다. 메모 컴퓨터네트워크 시간에 배운 적이 있는데, 다시는 보지말자는 마음으로 잊어버렸다. 그리고 이렇게 백준에서 만날줄 몰랐다. 다시 찾아서 정리해봐야겠다. import java.io.*; import java.util.*; public..