back-end

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제를 간단히 설명하자면, 임의의 점이 N개 주어진다. 해당 N개의 점을 한 번씩 사용해서 만들 수 있는 벡터들의 합 중 최소값을 찾고, 길이를 구해야 한다. 우선 이 문제를 해결하기 위해 벡터의 성질을 알아야 했다. 점 (x0, y0)에서 점 (x1, y1)을 향하는 벡터: (x1 - x0, y1 - y0) 점 (x2, y2)에서 점 (x3, y3)을 향하는 벡터: (x3 - x2, y3 - y2) 벡터들의 합: (x1 + x3 - x0 - x2, y..

12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 오늘도 여러 문제를 풀었다. 위의 문제는 스택과 같은 자료구조를 이용해서 해결하는 문제였다. 나는 Queue와 Stack을 이용하여 문제를 해결하려고 마음먹었다. 최근에 자료구조 문제들을 많이 풀어서 쉬울줄 알았지만, 위의 문제가 생각보다 쉽게 해결되지 않았다. import java.util.*; public class Main { public static void main(String[] args) { ... while (!queue.isEmpty()) { /..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘은 DFS 알고리즘 문제를 풀었다. DFS DFS는 깊이 우선 탐색(Depth-First Search)의 약어로, 그래프 및 트리의 한 정점에서 모든 정점을 방문하는 알고리즘 중 하나이다. 특징 1. 한 정점에서 시작하여 가장 깊은 곳 (최하위의 자식 노드) 까지 탐색하고, 되돌아와서 다음 가능한 경로를 탐색한다. 2. 스택(Stack) 자료구조를 사용한다. 3. 모든 정점을 방문하여야 할 때 사용된다. 4. 정점의 이웃 정점들을 재귀적으로 방문하여 구현한다. 5. 깊이를 가늠할 수 없을 경우, 스택오버플..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 해결하기 위해 생각했던 방법은 1. 주어진 배열을 다리를 짓는데에 필요한 재화(costs[i][2])로 오름차순 정렬 2. 섬이 직접적으로 연결되어 있는지 확인 3. 직접 연결되어 있지 않다면 간접적으로 연결되어 있는지 확인(dfs, bfs 등 사용) 4. 간접적으로 연결되어 있지 않다면 다리 건설 이렇게 해결하려 하였으나, 3번을 구현하는데에 어려움을 겪어 해결방안을 찾아보았다. Minimum Spanning Tree(최소 신장 트리), Kruskal(크루스칼) 알고리즘, Union Find 이 ..

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 처음에는 Map을 사용하여 구현하였으나, 시간초과가 발생했다. import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int S = scanner.nextInt(); int P = scanner.nextInt(); String dnaString = scanner.next(); H..

오늘은 알고리즘 테스트 시험을 봤다. 난이도 상, 중, 하 이렇게 세문제가 나왔으나 중, 하는 쉬웠다. 하지만 난이도가 상인 문제는 어려웠다. 상하좌우의 값을 비교해 가장 큰 값이라면 별을 출력하게 해야 하는 문제였다 처음에는 배열초과가 일어나지 않게 하기 위해 총 세부분으로 나누어 작업했다 1. 두 부분의 값만 비교하면 되는 꼭짓점 2. 세 부분의 값만 비교하면 되는 모서리 3. 상하좌우 모두 비교하여야 하는 안쪽 부분 public class Test_3 { public void Solution(int[][] checkin){ String [][] answer = new String[checkin.length][checkin[0].length]; // 1 꼭짓점 부분 구현 // 1-1. [0, 0] a..

알고리즘 문제를 풀면서 Stream을 이용하여 문제를 너무 풀어보고 싶었다. 그래서 시간이 날 때 틈틈이 Stream에 대해 알아봤다 처음 볼 땐, 무슨말인지도 모르겠고 걱정이 앞섰지만 코드들이 어떤 역할을 하는지 눈에 익기 시작했다. Stream을 사용하여 풀었던 첫번째 문제이다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 여러 종류의 포켓몬이 주어진다. 포켓몬의 종류는 중복될 수 있다. 포켓몬은 주어진 포켓몬의 절반만큼 가져갈 수 있다. 이때, 다른 종류의 포켓몬은 몇 마리인가? 가 문제이다. 손쉽게 풀 수 있었던 문제였다. 이번에는 Stream을..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제를 보고 스테이지를 key 값, 실패율을 value값으로 구현하여 풀면 되겠다고 생각했다. 최근에 힘겹게 풀었던 문제들을 TIL로 자주 썼었는데, 이 문제는 특히나 어려웠다. import java.util.*; class Solution { public int[] solution(int N, int[] stages) { Map map = new HashMap(); int answer[] = new int[N]; // 1부터 N까지 map 생성 for (int i = 0; i < N; i++) { ma..

문시해알 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 구현해야 할 부분이 너무 많아 막막했다. 해야 할 양은 많지만 그래도 구현하지 못할 부분은 없는 것 같아 하나하나 천천히 구현해 나갔다. // 대문자 -> 소문자로 변환 String lower = new_id.toLowerCase(); // 소문자, 숫자, 빼기, 점, 언더바만 값 넣기 String specialCheck = specialCheck(lower); // 점이 연속해서 두개 이상이라면 하나로 바꾸기 String decimalCheck = decimalCheck(specialC..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘도 알고리즘 문제를 풀었다. 이번 문제는 굉장히 복잡했다. 우선 구현해야 할 목록을 메모장에 작성했다. 1. n번째 글자를 ASCII로 서로 값을 비교해 버블정렬 2. 만약 n번째 글자가 같다면 2-1. 만약 비교중인 두 문자의 길이가 같다면 2-1-1. 두 개의 int 생성, 첫 번째 글자부터 값이 차이가 나게 되는 글자까지 for문을 사용하여 서로 다른 int에 넣음 2-1-2. 만약 뒤에 있는 int가 더 낮을 시, 현재 위치의 문자와 버블정렬을 통해 교환 2-2. 만약 뒤의 문자 길이가 더 짧다면 ..