알고리즘 10

[Nexters] 넥스터즈 (URL 단축팀) 정기활동 1주차 기록 - URL 단축 알고리즘 구현 및 코드 리팩토링

난 시간이 이렇게 빨리 갈 줄 몰랐다. 넥스터즈의 겨울 정기활동 2개월이 끝이 났다. 결과는 감사하게도 우수팀 선정! 매 주 세션 후 기록을 하려고 했지만, 너무 바빠서 기록할 틈이 없었다. 결론 적으로는 우리팀은 무사히 런칭을 마쳤다. 팀원들에게 너무 고맙다. 여태 했던 것들을 까먹을 까봐 적어 놓는다. 일단 우리 팀은 URL을 단축 하는 서비스를 개발하는 팀이다. 팀 구성은 (서버3, 디자인2, 프런트엔드3) 이렇게 되었다. 나는 서버 개발을 맡았다. URL을 단축 한다는 것은 큰 의미가 있다. 일반인들이 보기에는 저걸 굳이 줄여야할 필요가 있나라고 생각을 한다. 하지만 알게 모르게 그들도 일상속에서 단축 URL을 사용한다. 일례로, 가장 큰 서비스인 bit.ly가 있다. 원래 google의 단축 서..

[백준] 11279 최대 힙 풀이

힙은 쉬우면서 어려운 자료구조이다. 개념은 매우 쉬운데 구현에 있어서 놓치기 쉬운 부분들이 있기 때문이다. 문제 자체는 단순한 힙의 구현이다. 힙에 저장하는 부분이다. 저장할 때에는 위에 있는 노드와 비교를 진행한다. public static void push(int n) { heap[++index] = n; // 정렬 for (int i = index; i > 1; i /= 2) { if (heap[i] > heap[i/2]) { int temp = heap[i]; heap[i] = heap[i/2]; heap[i/2] = temp; } else { break; } } } 여기서 중요한 것은 인덱스의 범위이다. for 문안의 조건을 잘 생각해야 한다. 두 번째로 조금 까다로운 값 꺼내기 작업이다. pu..

[백준] 7576 토마토 풀이

창고에 보관되는 토마토가 인접하면 서로 익는다고 한다. BFS로 풀면 되는 문제이지만 BFS문제마다 하나씩 포인트가 있다. 이 문제는 한 점에서만 탐색이 이루어지는 것이 아니라 동시에 여러 곳에서 BFS가 일어난다. 상자 안에 토마토가 여러개 있을 수 있으므로 각 지점부터 BFSF를 진행해 주어야 한다. 그래서 배열을 초기화 하는 과정에서 토마토가 들어 있다면 큐에 하나씩 넣어주어야 한다. 전체 소스 import java.util.*;import java.io.*; public class Q7576 { static int row; static int col; static int[][] tomato; static int[] moveX = {0, -1, 0, 1}; static int[] moveY = {-..

[넥스터즈] 개발 일지 1주차 개발 내용 및 아이디어 선정

넥스터즈 활동이 시작 되었다. 여러 기수 회원들이 참가한 이번 시즌에는 좋은 아이디어들이 많이 나왔다. 아이디어가 선정이 된 회원들은 (대략 10개정도) 발표를 하고 팀 모집을 시작했다. 모바일, 웹, 게임 등 다양한 프로젝트 아이디어들이 나왔다. 발표를 쭉 들어보고 원하는 팀에 가서 상담(?)을 받는 형식이었다. 내가 중요하게 생각한 부분은 스택과 아이디어 였다. 아이디어들은 다들 너무 좋았기 때문에 하고 싶은것이 몇 개 있긴했지만 그 중 제일 재밌어보이고 현실성 있는 아이디어가 있는 팀으로 갔다. 게다가 내 스택과 맞는 팀이었다. 현재 내가 새로운 언어를 공부하면서 진행하기에는 무리가 있기 때문이다. 프로젝트 기간이 2달이기 때문에 1주차부터 바로 개발에 투입되어야 해서 처음부터 배우면서 한다는 것은..

[백준] 11052번 카드 구매하기

문제 출처 : https://www.acmicpc.net/problem/11052 이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 문제가 장황하여 주의력이 산만해지지만 침착하게 읽어보자. 카드팩의 배열이 배열의 인덱스는 카드의 갯수이고 배열의 값은 카드의 금액이다. 이 두가지 정보가 한 배열에 들어 있기 때문에 조금 헷갈릴 수 있다. 123456789101112131415161718192021222324import java.util.*; public class Q11052 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] card = new int[n+1]; in..

[백준 알고리즘] 2156 - 포도주 시식

백준 알고리즘 2156번 Dynamic Programming 문제를 풀어보았다. 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 ..

[알고리즘] 알고리즘 수업내용정리

알고리즘 : 문제를 해결 하는 방법, 추상적, 개략적으로 기술한 조리법 알고리즘을 구체적으로 표현한 것이 프로그램이다. * 알고리즘의 정확성 (Correctness)허용된 입력에 대해서 제대로 동작해야 함정확히 우리가 기대하는 것을 수행해야 함 * 프로그램 오류1) 문법 오류 (Syntax Error)- 명령문 끝에 세미콜론 등 2) 의미상의 오류 (Semantic Error)- 2 * 5 와 2 ** 5 3) 논리적인 오류 (Logical Error, Algorithmic Error)- 가장 치명적인 오류 * 부정확한 알고리즘 결과- Abort (Abnormal Termination)- 무한 루프 (Infinite Loop)- 정상적으로 끝났지만 잘못된 결과를 출력 * 시간 복잡도 분석- 하드웨어 환경..