Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - LinkedList
2023. 1. 15. 17:25
Algorithm/Before Check
들어가며 해당 내용은 앞 글인 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - ArrayList, LinkedList에서 이어진다. 이번 글에서는 Sequence Container에 속하는 LinkedList를 알아볼 것이다. 2023.01.15 - [Algorithm/Before Check] - Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (1) Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (1) 들어가며 해당 글은 아래 알고리즘에 대해 보기 전 Java에서 PS를 할 시 자주 사용할 Collection 클래스 또는 다른 유용한 클래스들을 설명한다. 설명하면서 간단히 예제와 함께 사용방법들 역시 익 sehun5515.tistory...
Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - ArrayList, Deque
2023. 1. 15. 00:16
Algorithm/Before Check
들어가며 해당 글은 아래 알고리즘에 대해 보기 전 Java에서 PS를 할 시 자주 사용할 Collection 클래스 또는 다른 유용한 클래스들을 설명한다. 설명하면서 간단히 예제와 함께 사용방법들 역시 익히는 것이 목표이다. Sequence Containers Sequence Containers는 다음과 같은 특징을 가진다. Sequence Containers의 경우, 데이터를 순차적으로 저장하며 정렬 상태를 유지하지 않는다. 구현이 단순하여 가볍고 빠르다. 기본적으로 만나볼 수 있는 Sequence Containers는 ArrayList(Vector)와 Deque(ArrayDeque)가 있다. ArrayList(구 Vector) 일반적으로 사용하는 배열(Array)의 경우, 랜덤 엑세스가 가능하고 읽고..
23년 삼성 DX부문 동계 대학생 알고리즘 특강에 합격했다.
2023. 1. 13. 18:19
잡담
해당 프로그램에 대해 궁금한게 있으신 분은 다음 링크를 참고하시면 됩니다. https://samsungalgorithm.com/ Samsung 4년제 대학 컴퓨터공학 관련 전공 대학(원)생 *재학생, 휴학생 및 졸업생 포함 초급 S/W 알고리즘 역량을 보유하고 있으며 (SW Expert Academy D3 풀이 가능) 중·고급 수준으로 역량 강화를 희망하는 분 samsungalgorithm.com SSAFY 9기에 지원했다가 코테에 얻어터지고 Java와 Spring/JPA를 공부하고 있던 중에 우연히 해당 공고를 보게 되었다. 처음 봤을때가 저번 주 목요일 점심쯤이었고 마감이 금요일 저녁이었으니 꽤 늦게 본 셈이었다. SSAFY에 지원하고 코테를 본 뒤 알고리즘 풀이에 대한 어떤 강의나 가이드라인이 있었..
프로그래머스 lv2 - 거리두기 확인하기
2022. 12. 10. 14:33
Algorithm/BFS, DFS
문제 https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 input에 들어오는 2차원 배열의 각 행이 하나의 test case로 생각될 수 있고, 각 행들은 적절한 문자열 처리를 하면 2차원 배열로 다시 만들 수 있다. 이 2차원 배열이 문제의 조건인 맨해튼 거리 2 이하로 모든 사람이 배치되어 있는지 확인하는 문제이다. 처음 문제를 해결할 때 DFS로 해결했었다. 각 방을 탐색하며 원래 위치와 현재 위치의 좌표를 이용해 맨해튼 거리를 구..
[BOJ 18428] 감시 피하기
2022. 12. 10. 00:31
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 접근 방법 3개의 위치를 선정하여 장애물을 놓고 그 장애물이 학생을 걸리지 않게 해 줄 수 있는지 판단하는 것이다. 즉, 문제는 2가지로 나눌 수 있다. 첫 번째로 3개의 위치를 선정해야 한다. 두 번째로 선정한 위치에 대해 감시를 피할 수 있는지 판정하는 로직을 넣어야 한다. N과 선생님의 전체 크기가 작고, 연산량 자체도 크지 않은 동시에 시간도 널럴하기 때문에 모든 위치에 대한..
[BOJ 2193] 백준 2193 이친수
2022. 12. 1. 14:03
Algorithm/DP
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 접근 조건 기본적인 dp 문제이다. dp 테이블을 정하자 이때 dp[i]를 길이 i일 때 가질 수 있는 이친수의 가짓수로 정의할 것이다. 이친수의 조건에 따라 길이 1, 2일때의 이친수는 각각 1, 10으로 1개씩이 될 것이다. 길이 3이후의 이친수의 가짓수를 살펴보면 다음과 같다. 3일때 가질 수 있는 이친수는 101, 100으로 2가지이다. 4일때 가질 수 있는 이친수는 101..
Hash, map의 문제 유형 탐구
2022. 11. 23. 16:56
DataStructure/Hash, map, set
개념탐구 Python에서 Dictionary 자료형에 대한 것을 본 적이 있을 것이다. 해당 자료형은 [key: value]의 쌍으로 묶여있으며 일반적인 배열/리스트 접근방식으로는 접근할 수 없고 해당 key를 사용해야 접근이 가능하다. 가령 다음과 같이 과일의 이름과 그 개수가 담겨있는 Dictionary가 있다고 가정해보자 my_dic = { 'apple': 1, 'banana': 2, 'grape': 3 } 이때, 'apple'은 key라고 정의하고 옆의 숫자 1은 value라고 정의한다. my_dic에서 바나나의 개수를 알고 싶다면, 다음과 같이 접근 할 수 있다. print(my_dic['banana']) # 2 보통 이러한 자료구조를 python에서는 Dictionary라고 하나, 알고리즘에서..
[Programmers] 전력망을 둘로 나누기 - python
2022. 11. 23. 02:59
Algorithm/BruteForce
문제 접근 방법 문제의 유형이 일반적인 완전 탐색과는 달라보인다. 이 문제는 완전 탐색의 개념 + DFS/BFS 알고리즘이 합쳐진 문제로 개인적으로 꽤 좋은 문제라고 생각한다. 전선들 중 하나를 끊어 둘로 나뉘어진 송전탑의 개수를 구해야 한다. 이번 문제를 그래프로 모델링해보면 아래와 같을 것이다. 입력 예제로는 첫번째 샘플 예제를 사용한다. 이 그래프에서 우리는 어떤 간선을 잘라 두 개의 트리로 만들고 각 트리에 속한 정점의 개수들을 계산해야 한다. 간선은 단 한번만 자를 수 있다. 그럼 여기서 생각할 수 있는 경우의 수는 몇 가지일까? 이 문제의 경우의 수는 조합으로 환원할 수 있다 정점의 수가 N개라고 할 때 간선의 수는 N - 1개라고 문제에서 정의하고 있다. 여기서 1개를 선택하는 것이므로 경우..
[Programmers] 카펫 - python
2022. 11. 23. 01:19
Algorithm/BruteForce
문제 설명 접근 방법 그림을 유심히 보면 다음과 같은 특성을 얻을 수 있다. 둘레에 놓인 갈색의 가로는 노란색의 가로 + 2와 같다. 둘레에 놓인 갈색의 세로는 노란색의 세로와 같다. 다만 노란색이 항상 1 x w의 형식으로 놓이지는 않기 때문에 노란색이 배치될 수 있는 경우의 수를 찾아야한다. 노란색의 영역이 w x h 일때 w, h이 될 수 있는 조건은 노란색의 개수의 약수여야 한다는 것에 포인트를 맞추어야 한다. 그렇다면 w, h은 다음과 같이 될 수 있을 것이다. W H 1 24 2 12 3 8 4 6 6 4 8 3 12 2 24 1 이때 문제에서 카펫의 가로 길이 w는 세로 길이 h 보다 크거나 같다는 조건을 본다면 경우의 수가 반토막이 난다. 따라서 최종적으로 생각해볼 수 있는 w, h는 다음..
[Programmers] 모의고사 - python
2022. 11. 22. 23:59
Algorithm/BruteForce
문제 설명 문제 접근 방법 lv1의 문제인 만큼 경우의 수를 찾는게 매우 쉽다. 각 수험자는 찍는 패턴이 나오고 이것을 답과 비교하여 맞으면 맞는 개수를 올려주면 된다. 찍는 패턴은 일정 길이만큼 가다가 다시 반복되므로 인덱스에 배열의 길이만큼 나눈 나머지로 반복을 표현할 수 있다. 가장 많이 맞춘 사람을 골라야 하므로 1, 2, 3번이 맞춘 개수를 표현해야 한다. 정렬을 수행할 시에 인덱스가 뒤섞여 답을 내지 못하므로 [맞춘 개수, 수포자 번호]로 score을 정의하면 된다. 이후 정렬을 수행해 최대 값을 찾고, 해당 최대 값과 같은 값을 가진 친구의 수포자 번호를 answer에 넣으면 해결된다. 동일한 값을 가지는 경우에도 순서대로 찾으니 조건을 만족한다. 풀이 코드 def solution(answe..