본문 바로가기
반응형

분류 전체보기1306

[BOJ] 백준 2583 영역 구하기 출처: https://www.acmicpc.net/problem/2583 Input 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2 Output 3 1 7 13 직사각형의 정보는 아래와 같습니다. 문제에서 주어진 인덱스를 아래와 같이 해석해도 무방. 3개의 분리된 영역과 그 넓이는 아래와 같습니다. ① 모눈 종이를 순회하며 직사각형으로 안 덮여진 지점을 찾습니다. ② BFS를 통해 분리된 영역을 구분합니다. ③ 분리된 영역의 개수와 각각의 넓이를 구합니다. import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Queue; imp.. 2021. 2. 23.
[BOJ] 백준 10819 차이를 최대로 출처: https://www.acmicpc.net/problem/10819 Input 6 20 1 15 8 4 10 Output 62 배열 A 원소 순서를 적절히 바꿔 다음 식의 최댓값을 구하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 구현 |A[0] - A[1]| + |A[1] - A[2]|의 최대값을 구하기 위해서는 A[1] 기준으로 양 옆에 최솟값 최대값을 배치하는 것입니다. 주어진 Sample을 풀이하면 다음과 같습니다. → |10 - 4| + |4 - 20| + |20 - 1| + |1 - 15| + |15 - 8| = 6 + 16 + 19 + 14 + 7 = 62 즉, 전체 수식에서 마찬가지로 가장 가운데를 기준으로 채워갑니다. ①.. 2021. 2. 23.
[BOJ] 백준 4963 섬의 개수 출처: https://www.acmicpc.net/problem/4963 Input 5 4 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 5 5 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 Output 1 9 ① 지도 배열을 탐색하며 땅(1) 탐색 ② BFS로 땅끼리 연결된 섬을 구분 ③ 찾은 섬의 개수 출력. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static Queue queue; static int w, h; static int[][] arr; static int[] rows, cols;.. 2021. 2. 23.
접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열. ex) S = "banana"에는 접미사가 총 6 개 있습니다. "banana", "anana", "nana", "ana", "na", "a" ▶Suffix[i] = [5, 3, 1, 0, 4, 2] ※ 문자열 매칭이나 압축 등과 같은 작업에 사용. 문자열 길이 N 이 너무 크지 않을 때, 접미사를 일일이 구한 다음 (O(N)) 정렬 (O(N logN))하면 되기 때문에 시간복잡도: O(N2 × logN) - [BOJ] 11656 접미사 배열 (단순히 접미사를 오름차순으로 정렬하는 문제) [BOJ] 백준 11656 접미사 배열 출처: https://www.acmicpc.net/problem/116.. 2021. 2. 23.
프로그래머가 가장 힘들어 하는 것은? IT 혹은 SW 업계에 있다보면 가끔 "프로그래머가 가장 힘들어 하는 것"이 무엇일까? 물론 개인 역량, 역할에 따라 비중은 달라질 수 있지만 아래 항목들이지 않을까 생각이 든다. ① 이름 짓기 코드 공유 및 리뷰 등 혼자 사용하던 협업을 하던 Naming 고민은 항상 존재한다. 📌 네이밍 컨벤션 (Naming Convention) 네이밍 컨벤션 (Naming Convention) Naming Convention은 언어마다 권장하는 것과 팀 내부에서 사용하는 방법이 다를 수 있다. 하지만 하나의 프로젝트에서 여러 Case가 섞이면 가독성이 떨어지기 때문에 최대한 정해진 Rule을 준수할 필 zoosso.tistory.com ② 구현 가능성 설명 개발 업무는 결국 고객의 요구사항을 구현하는 것이다. - 비.. 2021. 2. 23.
고객과 SW 개발자 의사소통 개발은 고객의 요구사항을 실현하는 작업이다. 고객은 자기가 원하는 것이 정확히 무엇인지 모른다. 가령, 단순 로그인 기능만 생각했던 초기 제안과 달리 서비스 내용, 벤치마킹, 법령(보안)에 의해 변경 및 추가 되는 경우가 많다. ex) Front-End 개발자는 기획자, 디자이너, 서버 개발자와 협업을 합니다. 실제로 기획과 디자인 과정에도 참여하게 되는 경우가 많습니다. 회의 과정에서 기술적인 피드백이 가능해야 합니다. ex) 중고 제품 거래 전에 판매자가 올린 제품 상태글 확인 기능 추가 네고왕 Ep.3 (당근마켓 편) 12:31분 요구사항은 반드시 변한다. 초기 협상 시 / 개발 작업 과정 / 검수 과정 등 어느 단계든 개발자를 힘들게 하는 순간이다. 개발자는 영향도를 파악해야 하고, 다른 유관부서.. 2021. 2. 23.
선택 정렬(Selection Sort) 선택 정렬(Selection Sort) - O(N2) 배열의 위치에 맞는 적절한 원소를 선택해서 배치하는 것입니다. - 첫번째 순서에 배열에서 가장 작은 최솟값 - 두번째 순서에 배열에서 두번째로 작은 최솟값 - 세번째 순서에 배열에서 세번째로 작은 최솟값 - ... ▷ 배열 인덱스 1...N까지 순회하며 해당 인덱스에 맞는 최솟값을 찾습니다. # include int swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void selectionSort(int arr[], int n) { for (int i = 0; i < n; i++) { int min = i; // 최솟값을 탐색한다. for (int j = i + 1; j < n; j++) { .. 2021. 2. 23.
[BOJ] 백준 9663 N-Queen 출처: https://www.acmicpc.net/problem/9663 Input 8 Output 92 체스판에서 퀸(x, y)의 이동은 같은 행, 열 그리고 대각선 방향입니다. 두 좌표가 (x1,y1), (x2,y2)일 때, |x1- x2 | = | y1 - y2|이면 좌표상 대각선상에 있다고 볼 수 있습니다. ex) A=(1,1) / B=(5,5)가 존재하면, |5-1| = |5-1| 이므로 대각선상의 위치. 1행을 기준으로 퀸을 한개씩 놓아서 재귀 탐색처리. 1~N행까지 서로 공격하지 않게 퀸을 놓을 수 있는 모든 경우를 구합니다. ex) 4 x 4 크기의 체스판 만약 1행에 두번째에 퀸을 두었다면 아래의 형태가 됩니다. (특정 행에서는 여왕이 하나입니다.) 다른 풀이: [Jungol] 1889 .. 2021. 2. 23.
[Jungol] 정올 1889 N Queen 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162 Input 4 Output 2 N이 4일 때, 나오는 경우는 두 가지이다. 한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다. 그렇기 때문에 행마다 DFS 탐색을 하면서 1~N까지의 열에 놓을 수 있는지를 확입합니다. chk_vertical[i] = i 열에 여왕 존재 여부 check_diagonal_1[row + i] = 아래 그림의 대각선은 위치가 (x, y)일 때, (5, 5) ↔ (4, 6) ↔ (6, 4) ▶ x + y가 같습니다. check_diagonal_1[10] = 1에 해당 check_diagonal_2[row - i + N] = 아래 그림의 대각선은 위치가 (x,.. 2021. 2. 23.
개발자 IT 포트폴리오 왜 포트폴리오를 작성해야 할까? 개발자에게서 포트폴리오는 어떤 것에 관심이 있는지 보여줄 수 있는 도구 중 하나입니다. 특히, 잘 만들어진 포트폴리오는 구직활동에 유용합니다. 어떤 내용으로 작성해야할까? 포트폴리오 내용은 평가자의 입장에서 다양합니다. 대기업처럼 인사팀 → 실무자가 평가하는 경우에는 포트폴리오 보다는 Spec 자체가 중요시 되기도 하며, FrontEnd, BackEnd 등 포지션에 따라 평가되는 요소가 다릅니다. FrontEnd: 포트폴리오의 디자인, 프로젝트의 UX/UI BackEnd: 코드의 주석, 모듈화, 문서화 이 밖에도 일상 샐황 개선을 위한 프로젝트(→ 개발에 대한 관심정도 어필) 오픈 소스 기여 활동 ex) GitHub (→ 개발에 대한 관심과 수준 어필) Toy Projec.. 2021. 2. 23.
반응형

티스토리툴바