일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 삼성 SDS 대학생 알고리즘 특강
- 동적 계획법
- 백준
- BOJ
- 완전탐색
- dynamic programming
- 시뮬레이션
- 잠실
- 다이나믹 프로그래밍
- 알고리즘
- 스택
- PS
- 에라토스테네스의 체
- DP
- 구현
- hackerrank
- 삼성 기출
- 백트래킹
- C++
- 맛집
- dfs
- 해커랭크
- 소수
- Algorithm
- 그리디
- 브루트포스
- sw expert academy
- BFS
- koitp
- SWEA
- Today
- Total
목록분류 전체보기 (108)
펭로그
문제 링크 : https://boj.kr/1978 이 문제는 에라토스테네스의 체를 이용하여 소수 리스트를 미리 구한다음 계산하면 쉽게 답을 찾을 수 있다.입력 최대값이 1000밖에 안되기 때문에 그냥 1000까지 미리 소수를 구하는 편이 빠른 것 같다. 12345678910111213141516171819202122232425262728293031323334#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bool isPrime[1001]; memset(isPrime, true, sizeof(isPrime)); // 에라토스테네스의 체 이용하여 1000까지의 소수..
방이동 먹자골목에 있는 진성 한우 곱창을 다녀왔다. 가게 앞에서부터 웨이팅의 냄새가 난다. 우리 앞에 6팀 정도 있었다. 한 30분 정도 웨이팅 한듯 8ㅅ8중간에 더운날 기다리느라 고생한다고 시원한 물 한잔씩 사장님께서 주셨다. 가게 밖에서부터 볼 수 있는 메뉴판 가게 내부 메뉴판 모습 기본 상차림! 곱창 모듬 2인분을 시켰다. 거의 다 익혀서 나온다. 여기는 직원이 직접 다 해준다. 개꾸르 지글지글 추가로 대창 1인분을 시켰다. 모듬 구이 중에선 대창이 젤 맛있는듯 깍두기 철판 양밥도 추가! ㄹㅇ 핵존맛 잠실에 여러 곱창집에 있는데 그 중에서 제일 맛있는 맛집인 것 같다.다른 곱창집도 웨이팅 해야되고 여기도 저기도 다 웨이팅 해야하는데 웨이팅 안하는 집은 그냥 그닥 그런 것 같은 느낌..이 더운 여름날..
문제 링크 : https://boj.kr/2581 소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이..
문제링크 : https://boj.kr/2468 흰색으로 연결된 부분들의 갯수를 세는 문제다.갯수를 세는 것은 DFS로 풀면 되는데.. 문제는 1~100까지의 비 내리는 높이들을 하나 하나 다 계산해봐서 영역이 가장 많은 것을 구하는 것이다.어떻게 해야 효율적으로 구할 수 있을까 생각해봤는데.. 일단 풀었다.1~100까지의 횟수는 그리 많은 횟수가 아니라 시간 복잡도 상으로도 O(1)에 해당하기 때문에..그래서 1~100 까지의 모든 높이마다 각각 dfs를 그냥 돌렸는데 시간초과도 나지 않고 풀렸다. 이미 풀렸기 때문에 여기서 시간을 더 줄이는 효율적인 방법은 생각해보지 않았다.혹시나 해서 입력 받을때 최소 높이, 최대 높이를 추가로 체크해서 풀었는데 어짜피 시간은 똑같이 나왔다. 별로 의미가 없는듯 차..
문제 링크 : https://boj.kr/1012 BOJ 11724 연결요소의 개수랑 매우 유사한 문제로 생각된다.인접한 배추들이 존재한다면 하나로 이어진 배추들에는 지렁이가 한마리씩만 필요하다.결국 연결요소 문제랑 동일하게 연결요소의 갯수를 세면 되는 문제다.visited를 따로 만들지 않고 dfs로 탐색이 가능한 위치면 true로 두었고 방문 불가능한 위치이거나 방문했다면 false로 두었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950// BOJ 1012 유기농 배추#include using namespace std; vector cbg;const int dx[4] = {1, -1..
문제 링크 : https://boj.kr/10451 그림과 같이 순열 사이클을 찾는 방법은 간단하다.그냥 dfs로 돌리면 된다. dfs를 몇번 시작했는지만 체크하면 된다.다음에 방문할 노드를 저장하는 것은 인접 리스트를 만드는 방법과 동일하고 방문했다면 0으로 설정하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243// BOJ 10451 순열 사이클#include using namespace std; vector permu; void dfs(int idx){ int next = permu[idx]; if(next != 0) { permu[idx] = 0; // 방문 표시 dfs(next); }} int main..
문제 링크 : https://boj.kr/11724 문제의 컨셉은 간단하다. 주어진 그래프에서 하나로 이어져 있는 연결 요소의 개수를 찾는 문제로 위 그림에서 하나로 이어져있는 연결 요소 수는 2개가 된다. 입력의 경우는 미리 인접 리스트를 만들어 간선을 입력 받는다. 그 이후 1부터 N까지 DFS를 돌려서 DFS가 끝나는 시점에 카운트를 하나 증가시켜 주면서 다음 시작 요소로 DFS를 돌리는 식으로 반복하면 답을 구할 수 있다. 스택으로 구현한 방법이 함수를 사용하여 재귀로 돌리는 것보다 시간이 덜 걸릴 줄 알았는데 함수로 재귀 돌리는 것이 의미 없는 수치이긴 하지만 더 빨랐다. (위 - 스택, 아래 - 재귀) 스택으로 구현한 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
문제 링크 : https://boj.kr/2178 지난번에 풀었던 BOJ 7576 토마토 문제보다 훨씬 쉬운 BFS 문제인듯 하다.토마토 문제에서 잡았던 대부분의 기본 개념을 그대로 가지고 풀었다.토마토 보다 이 문제를 더 먼저 풀었으면 좋았을걸.. 먼저 이 문제는 입력 자료형이 공백으로 구분지어져있지 않기 때문에 1. std::istringstream 를 split 하여 입력받기2. char형 그대로 입력 받는 방법3. 스트링 클래스의 getline(std::cin, input); 사용4. scanf("%1d", &input); 처럼 형식지정자로 1자리만 받도록 하기등등 다양한 방법을 활용하여 입력 받아야 한다. 이 외에도 getch나 gets 등등 아주 많다.scanf를 사용하는게 제일 편하긴 하지만..
방이동 먹자골목에 위치한 착한우 정육식당을 방문했다!입구에서부터 메뉴 현수막이 걸려있는 것을 보면 가격이 아주 ㅎㄷㄷ하게 저렴한 것을 확인할 수 있다. 입구에서 고기를 직접 고르고 자리로 가면 된다. 질 좋은 고기들이 한가득!상차림비로 인당 2천원씩 내고 먹으면 된다. 개꿀 매장의 모습 여긴 숯을 쓴다! 잘 모르겠는데 참숯처럼 보인다. 기본 상차림이 나오고 39,000원 짜리 한우 모듬 500g을 시켰다.아주 질 좋은 고기인듯 하다. 육회도 시킴! 존맛 맛있게 익어간다! 업진살을 추가로 더 시켰다!저게 25,000원 어치 아주 맛있게 잘 먹었음 ^ㅅ^
삼성 SDS에서 대학생을 대상으로 알고리즘 교육을 무료로 시켜준다는 공고가 떴다!온라인으로 분반테스트 응시를 하고 선발된 인원에 한해서 알고리즘 교육이 진행되는 프로그램이다.알고리즘 교육을 받을 기회가 없어서 제대로 공부해보지도 못한 채로 알고리즘을 제대로 시작한지 2달 정도 밖에 안된 나에겐 아주 좋은 기회라 생각이 들어 바로 신청했다.하지만 신청자가 몰린 탓에 마감 기간이 27일까지였지만 실제 마감은 17일 경에 마감된 것 같다. 18일 쯤에 사전테스트 응시 안내 메일이 오고 22일 자정까지 응시할 수 있도록 안내 메일이 왔다.사전테스트 문제는 삼성SDS에서 운영하는 https://koitp.org 사이트에 공개되어 있다. 미라콤아이앤씨와 삼성 SDS의 사내 교육에 이용하는 사이트로 개설되어 있는 것..