전체 글158 [백준] 11403 경로 찾기 Floyd Warshall 문제 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 : 이 문제는 플로이드 와샬 방식으로 접근해보았다. 백준 논의 보니까 DFS, BFS 로도 풀 수 있는 것 같아 보였다. 플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 정점에서 모든 정점으로의 최단 경로를 찾는데 사용되는 알고리즘이다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬은 거쳐가는 정점을 기준으로 접근해야 한다는 점이 포인트였다. 플로이드 와샬은 다이나믹 프로그래밍에 의거한다고 한다. 가장 이해되는 .. 2021. 2. 18. [백준] 2178 미로 탐색 bfs 문제 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 분석 : 이 문제는 경로 탐색 문제이다. DFS, BFS 둘 중 아무거나 풀어도 상관 없어 보인다. 나는 BFS 연습을 위해 BFS 방식으로 풀었다. cin 은 공백 기준으로 input을 받는 것 같아서 scanf의 도움을 받았다. cin 으로 풀 수있는 방법 알면 알려주시면 감사하겠습니다. 🥺 2차원 행렬에 값이 1 (지나갈 수있는 칸) 인경우 true로 담았고 아니면 false로 값을 초기화 하였다. 이 문제는 input 값이 0.. 2021. 2. 17. [백준] 1931 회의실 배정 문제 : www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 분석 : 이 문제는 대표적인 greedy algorithm으로 푸는 문제이다. 회의실, 가방 배낭 등 고전적인 문제 유형인거 같다. 벡터에 인풋값을 모두 담은 뒤 핵심은 회의가 끝나는 시간 second 를 기준으로 정렬을 하는 것이었다. 그리고 for문을 돌면서 검사하는데 이전 회의의 끝나는 시간 < 다음 회의 시간 이면은 회의가 시작 될 수 있는 것이므로 cnt 값을 증가시켜 회의의 갯수를 셌다. c++ 코드 : // // 1931_room.cpp // SOMA👩🏻💻 // // Created by JoSoJeong.. 2021. 2. 17. [백준] 19598 최소 회의실 개수 문제 : www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 분석 : 이 문제는 주어진 인풋에 대해 필요로 되는 최소 회의실 개수를 구하는 문제다. greedy를 이용해 풀었고 회의실이 3개, 회의실 이용 시간은 0 40 15 30 5 10 으로 주어질 때 1. 회의 시작 시간을 기준으로 정렬을 한다. 0 40 5 10 15 30 함수 안에서 처음에 0, 40을 vv vector에 담은 뒤 v 함수 다 돌 때까지 vv 크기만큼 if문을 돌게된다. else 문.. 2021. 2. 17. [백준] 10818 최소, 최대 문제 : www.acmicpc.net/search#q=10818&c=Problems 검색 www.acmicpc.net 분석 : 이 문제는 못푼 문제에 있길래 클릭 해보니 비교적 간단한 문제라서 풀었다. 1년전 문제라니 세월이 빠르구나 * 반례로 1 10 케이스와 2 10 10 케이스가 있으니 잘 생각해보길 바란다. 처음에는 for문 하나에 input 값 넣고 바로 비교 하려 했는데 위 두 케이스 때문에 분리해서 담아줬다. C++ 코드 : // // 10818_min_max.cpp // SOMA👩🏻💻 // // Created by JoSoJeong on 2021/02/12. // #include #include #include using namespace std; int main(){ int n, max.. 2021. 2. 16. [백준] 2110 공유기 설치 문제 : www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 분석 : 이 문제는 내 기준선에서 조금 신박했던 (?) 이분(이진) 탐색 문제였다. 문제를 이해하는데에도 헷갈렸다. 처음에 정렬을 한 뒤 start 와 end 변수를 간격의 최소, 최대 거리로 설정해 둔뒤 이 위치를 mid 값 변경을 통해 index 위치를 변경 시킨 뒤 start 가 end 인덱스보다 커지게 되면 종료한다. 비교 기준은 mid 값으로.. 2021. 2. 16. [백준] 2252 줄세우기 문제 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 분석 : 이 문제는 종만북 DFS BFS 부분의 대표적인 예제 중 위상 정렬에 관한 문제였다. 위상 정렬이란 의존성이 있는 작업이 주어질 때 이를 어떤 순서로 수행해야 하는지 계산한다. 이때 의존 관계를 DAG(사이클 없는 그래프) 로 표현한다. 사이클이 없다는 뜻은 즉 한 방향에서 한 방향으로 흘러가는 꼴의 그래프를 말한다. 그렇기 때문에 기존 DFS BFS 는 트리 .. 2021. 2. 14. [백준] 10828 stack 문제 : www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 분석 : 을 사용하여 비교적 쉽게 풀 수 있었던 문제였다. 다만 처음으로 segmentation fault 컴파일 에러가 떴는데 top 부분에 empty 조건을 검사하지 않아서 난 문제였다. 정의된 문제를 앞으론 더 잘 읽어야겠다. 그리고 처음으로 cin 이 공백 기준으로 분리해 읽는다는 점을 알게 되었다. 이를 위해 getline 함수를 사용해야 했고 cin 과 getline을 겸용.. 2021. 2. 6. [백준] 1915 가장 큰 정사각형 DP 문제 : www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 분석 : 대표적인 DP 문제로 1씩 더하는게 곧 정사각형의 한 변이 된다는 게 신기했다. DP가 전에 한번 공부했을 때 잘 이해가 안됐는데 이번에 조금 알거 같다는 생각이 들었다. 우선 arr이라는 원래 2차원 배열을 만들고 memo라는 배열에 값을 계산해 누적한다. arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 모두가 1일때만이 arr[i][j]과 함께 정사각형을 만들 수 있으므로 그런 경우만 검사 한 뒤 1을 더해 한변을 memo 배열에 누적해.. 2021. 2. 5. [백준] 1987 알파벳 DFS 문제 : www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 분석 : 위 문제는 전형적인 DFS 문제이다. 처음에는 오른쪽과 아래쪽으로 나아가는 것만 고려했고 수행한 알파벳은 set 함수에 저장해 놓아야지 생각하여 접근했었다. 하지만 안좋은 알고리즘이었다 하하 만약 진행 중 동일한 알파벳을 만난다면 진행한 것을 진행하지 않은 것처럼 하여 다른 방향으로 탐색하는 것이 포인트였다. 재귀함수 사용하는게 추상적이라 잘 이해가지 않아 다른 문제들도 많이 풀어봐야겠.. 2021. 2. 5. [백준] 2470 두용액 이분탐색 문제 : www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 분석 : algorithm의 sort 함수는 기본 sort 함수와 달리 마지막 인자에 사용자 정의 함수를 추가해 정렬할 수 있다. 위 함수를 이용해 1) 배열을 절대값 기준으로 정렬 2) 절대값 비교를 통해 원래 값 변수에 저장 후 누적 3) 마지막으로 산성과 알칼리 값 구분해 swap 하여 출력 하는 방식을 사용하였다. c++ 코드 : // // 2470_soluti.. 2021. 2. 5. [백준] 2467 용액 이분탐색 문제 : www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 분석 : 이 방식은 시간 초과가 났다. 산성과 알칼리 용액을 구분해 배열에 담았고 각 배열이 끝날때까지 O(n^2)으로 탐색하는 방법을 사용했는데 가장 비효율적으로 문제를 푼거 같다. 그리고 딱히 map 함수를 사용하지 않아도 되었는데 쓸데 없는 악세사리가 많은 느낌 .. 문제에서 더 효율적인 방법을 찾아 해결하였다. C++ 코드 : // // 2467_solution.cpp // SOMA👩🏻💻.. 2021. 2. 5. HTML tag & attribute 정리 HTML은 구조적 문서이다. : HTML 문서의 범위를 설정 : HTML 문서의 정보를 설정 : HTML 문서의 구조를 설정 : 제목 표시줄이나 페이지 탭에 보이는 문서 제목을 정의 : HTML 문서에 포함된 모든 상대 URL들의 기준 URL를 설정 하나의 문서에 하나의 base 태그만 사용 가능 속성 의미 값 기본 값 href 기준 URL URL X target A 요소처럼 target 속성을 사용하는 요소의 기본값 _self, _blank _self : 외부 리소스의 연결 및 현재 문서와의 관계 명시 속성 의미 값 rel (필수!!) 현재 문서와 외부 리소스와의 관계 stylesheet, icon… href 외부 리소스의 URL URL type 외부 리소스의 MIME 타입 text/css, image.. 2020. 11. 23. Git 명령어 정리 centralized version control system 중앙 서버가 모든 version 1, 2, 3 .. 파일을 가지고 있고 각 컴퓨터가 중앙 위치에서 파일을 체크한다. - CVS, Subversion 등 .. - 네트워크가 좋지 않으면 딜레이가 발생해 연결이 느려지고 튕기기도 함 distributed version control system - 서버에서 버전을 통채로 가져온다. (텍스트 파일이라 그렇게 무겁지 않다.) commit, add 등 버전 만들고 난 뒤, - 한번에 push 하여 중앙 서버에 보낸다. - git 이 대표적 생성1 git init : .git 레퍼지토리 생성 생성2 git clone 복사주소 : 존재하는 레퍼지토리 복사 git status : 파일의 상태를 확인 git .. 2020. 11. 22. AWS - 2 강연 듣고 나서 .. 생각보다 정말 많은 서비스들을 구축하고 있었고 이를 활용하는 기업들도 많았다. IT기업만 도움을 주는지 특정 산업 분야에 대해서만 서비스를 구축해 지원하고 있는 것인지 궁금해졌다. 어뷰징이 불법이구나 .. github에 공부 목적으로 올리는 경우가 많은데 이를 저작자랑 그렇지 않은 자를 구분한다는게 어려운 것 같다. 배달 내가 하고 싶었던 아이디였는데 배달 로봇을 2017년도부터 만들어 놓고 있었다니 배민 너는 다 계획이 있구나 ~~ .. 부럽 .. 그리고 환경에 대한 사회적 책임을 다하는지 안하는지 끝까지 지켜 볼 꺼고 나는 절대 1000만에 속하지 않을 것이다 지켜보겠다. 그리고 강의 중에 ec2가 나와서 신기했고 다음 강의 시간에 ec2와 s3, glacier에 대해 잠깐 배운다 그러니 다음 실습도.. 2020. 11. 17. AWS - 1 강연 듣고 나서 .. AWS 사가 마냥 다루기 어렵다고 생각했었다. 책 추천 시스템에서부터 확고한 철학으로 IT 시대에 맞는 서비스를 제공하는 기업으로 탈바꿈한것이 정말 대단하다. 고객의 needs를 매달 문서화하여 제출해야 한다는 말씀이 놀라웠다. 로봇을 많이 쓰다보니 소통이라곤 전혀 없는 기계적인 회사인것 같았지만 고객의 입장에서 관점을 바라보고 그를 위한 서비스 구축에 힘쓴다는 점이 역시 크게 된 기업은 다르구나 라는 생각이 들었다. 가장 인상 깊게 들었던 것은 이미지 인식을 통한 딸기 상한 것 골라내는 작업이었다. 센서 + 머신러닝 + 컴퓨터 비전을 활용해 신선 제품만을 배송하고자 하는 것이었는데 이미 실제 쓰고 있는 거라니 .. 궁금함이 생겨 검색해보니 amazin fresh 프로젝트는 실패한 사례라고 한다.. ㅎ .. 2020. 11. 12. 데이터베이스 설계 단계(요구사항 분석, 개념적 설계, 논리적 설계, 물리적 설계) 개요 : 1. 요구사항 분석 데이터베이스 설계는 요구 사항 분석 단계부터 시작한다. 요구 사항 분석 단계에서는 조직의 구성원들이 데이터베이스를 사용하는 용도를 파악한다. 데이터베이스를 사용해 실제 업무를 처리하는 사용자에게 필요한 데이터의 종류와 처리 방법 같은 다양한 요구 사항을 수집하고 이를 분석한 결과를 요구 사항 명세서로 작성하는 것이 요구 사항 분석 단계에서 수행하는 주요 작업이다. 요구 사항 분석 단계에서 파악한 사용자의 요구 사항은 이후의 설계 단계에서 중요하게 사용되고, 구축된 데이터베이스의 품질을 결정짓는 중요한 기준이 된다. 2. 개념적 설계 개념적 설계 단계는 요구 사항 분석 단계의 결과물인 명세서를 가지고 시작한다. 개념적 설계 단계에서는 요구 사항 분석 단계에서 파악한 사용자의 요.. 2020. 10. 25. relation 과 table의 차이 릴레이션과 테이블의 차이는 추상적 개념과 이를 나타내는 구체적 표현의 차이인데 릴레이션은 추상적 개념(abstract concept)이고 테이블은 이 릴레이션을 기술하는 하나의 구체적 표현(concrete representation)인 것이다. 2020. 10. 25. 이전 1 ··· 5 6 7 8 다음
