본문 바로가기

전체 목록!291

두 원 사이의 관계 중학교 수학에서 배웠던 두 원 사이의 관계... 솔직히 다 까먹었다. 그래서 오늘 백준 문제를 푸는데 1002번 터렛 문제를 풀려는데 기억이 안나서 다시 상기시키는 과정으로 블로그 글을 써보려고 한다. 먼저 얘는 총 6가지가 있다. 크게 나눠서 살펴보자.* r 은 작은 원의 반지름이고, r'은 큰 원의 반지름이다. d는 두 원의 중심 사이 거리이다.하나도 안 만날 경우하나도 안 만날 경우에는 3가지가 있다. (그림을 못 그린다...) 가장 흔하게 생각할 수 있는 모양이다. r + r' < d 얘는 되게 신기한 경우인데, 원의 중심이 같은 경우이다. 이런 경우를 동심원이라고 하며, r != r'이다. 그러면서 d = 0이 된다. 그림을 되게 못 그리긴 했는데 r' - r을 하고 나면 d 말고도 왼쪽에 쪼가.. 2017. 11. 16.
[Algorithm] LCS(Longest Common Subsequence, 최장 공통 부분 수열) LCS알고리즘오늘은 LCS 알고리즘에 대해서 알아보도록 하겠다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)이다. substring과 subsequence의 차이점은 예를 들어서 'carrot'이라는 단어를 자를때, Substring : 연속해서 이어져 있는 것이다. (예시) carr 또는 rot 등등. Subsequence : 순서는 바뀌지 않지만, 띄어져서도 이어지는 녀석을 칭한다. (예시) cro 또는 arrt 등등. LCS는 두 수열이 주어졌을 때, 공통으로 들어있는 부분 수열 중 가장 긴 것을 찾는 것이다. orange와 neopong 이 주어졌을 때 공통으로 있는 부분 수열은 'ong'가 될 것이다.. 접근수열 A인 abcdef와 수열 B인 bce가 있다. .. 2017. 11. 15.
[BOJ] 1260번: DFS와 BFS 문제 풀러 가기 링크! 1260번: DFS와 BFSDFS와 BFS를 실제로 구현해 볼 수 있는 아주 좋은 문제이다.DFS는 깊이 우선 탐색이여서 최대한 한 정점에서 최대한 깊게 갔다가 다시 돌아오는 작업을 반복해서 모든 정점을 탐색하는 것이고BFS는 너비 우선 탐색이여서 층 별로 있는 모든 정점을 다 돌면서 내려간다고 보면 된다.아직 내가 직접 쓴 글이 없어서 개인적으로 정말 좋다고 생각하는 블로그의 글의 링크를 걸어 놓을테니 이 쪽에 가서 자세히 공부하면 된다.DFS 설명, BFS 설명 개인적으로 DFS는 재귀함수를 이용하는 것을 좋아해서 원래는 스택을 쓰지만 나는 재귀함수로 구현했고 BFS는 스택을 이용해서 구현했다. BFS는 분리하지 않고 main함수에 적어서 가독성이 떨어질텐데... 그 점은 양해.. 2017. 11. 4.
AWS(Amazon Web Service)에 대한 나의 생각 사건의 시작10/26/2017, 방과후에 학교에서 AWS에 대해서 1시간 30분동안 교육을 받고 간단한 실습을 해볼 기회가 있었다.아마존 AWS 동아시아 태평양 담당 이사님께서 설명을 해주셨다.아마존은 크게 AWS, 유저의 판매를 도와주는 서비스(?) - 이름이 기억 안 난다, 그리고 우리가 흔히 아는 아마존닷컴해서총 3가지정도로 구성되어 있다고 하셨다.그 중 AWS에 대해서 설명을 해주셨다. 윈도우를 예를 들어서 윈도우즈 서버 하나를 구축하려면 적어도 3개월이 걸린다고 한다.(회사는 절차가 복잡하다 보니 이런 문제가 생긴다) 그런데 AWS는 단 3~5분 정도면 된다고 한다.*실제로 내가 실습을 해보면서 윈도우즈 서버 2012 Base를 만들어 봤는데 정말 간단했다. 중간에 대답을 해서 AWS educa.. 2017. 10. 27.
[BOJ] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 오랜만입니다... 오늘은 팰린드롬에 대한 문제를 풀어 보려고 합니다.팰린드롬이란, 위키백과 : 숫자, 단어, 구 같은 시퀀스들이 앞과 뒤가 같아서 반으로 접으면 일치하게 되는 녀석들을 칭합니다. 이 문제는 DP로 푼다고 하는데, 저는 사실 DP를 잘 못하기도 하고 굳이 DP로 풀 필요가 없는 것 같았습니다.12345678910111213141516171819202122232425262728293031#include int palin(int start, int finish, int *arr) { int mid = (start + finish) / 2; for(int i = start, j = finish; i = mid; i++, j--).. 2017. 10. 21.
[파이썬] 바운스! 게임 공이 왔다갔다 거리면서 패들로 받아 치는 게임입니다. 많이들 해보셨을 거예요. 필요하시거나 코드 분석해보실 분들은 쓰세요. 저도 사실 책에서 하는 게임 만들기를 기반으로 만들어서 저작권 같은 건 없습니다. 2017. 10. 9.
tkinter를 이용한 모던 디자인(장난질!) [파이썬] Tkinter를 이용한 장난 [코드] 123456789101112131415161718192021222324from tkinter import *import randomtk = Tk()canvas = Canvas(tk, width = 400, height = 400)canvas.pack() def random_rectangle(width, height, fill_color): x1 = random.randrange(width) y1 = random.randrange(height) x2 = x1 + random.randrange(width) y2 = y1 + random.randrange(height) canvas.create_rectangle(x1, y1, x2, y2, fill = fill_.. 2017. 10. 9.
[알고리즘] 링크드 리스트에 대해 알고가야 할 것.. 의견 나눠주세요 이 글은 '뇌를 자극하는 알고리즘 - 박상현 저', 이것만은 알고 갑시다에서 나온 내용입니다. (문제가 된다면 바로 내리겠습니다.) 1. 링크드 리스트와 배열의 성능을 다음 세 가지 연산에 관해 비교하여 설명하세요. 삽입 삭제탐색- 링크드 리스트가 삽입/삭제 연산에서 보자면 배열보다 더 빠르다는 것에서는 장점이지만 역으로 특정 위치에 있는 노드를 찾는 것은 배열에 비해 느리다고 할 수 있다... 2. 환형 링크드 리스트의 장점은 헤더 노드를 이용하여 테일 노드의 위치를 바로 파악할 수 있다는 것입니다. 그럼 링크드 리스트나 더블 링크드 리스트에서 환형 링크드 리스트에서처럼 바로 테일 노드의 위치를 알아내게 할 수는 없을까요? 그 방법을 생각해보고 설명하세요. - (아직 생각이 안 떠오르니... 좋은 생각.. 2017. 9. 30.
내 블로그에서 음악을 들을 수 있다니!!! 심심해서 블로그를 꾸미고자 SCM 플레이어를 달아봤다. 이 플레이어는 학교에서 애들이 실습 서버를 터뜨리는 과정에서 알 게 되었는데 상당히 꿀인 플레이어다. 나도 꼭 만들어 봐야지~현재 내 블로그에 있는 음악들은 Coldplay, Ed sheeran, 아이유의 노래이다. 이거 일일이 다 하려니깐 너무 고생이라서 아직은 많이 추가 못 했는데 RSS를 만들어주는 크롤링 프로그램을 만들어서 확장 시킬 예정이다!역시 프로그래밍은 짱이라니깐~~~ 물론 그 작업은 시험 끝나고 할 것이다. 히힛 2017. 9. 24.
재미있는 만화책 :: 미생(윤태호 작가) 스티커는 학교 도서관 바코드라서 가리기 용으로 사용했다. 요즘 하도 컴퓨터 책만 읽어서 현실적으로 재미있는 책을 찾다가 만화책을 다시 찾았다. 역시... 만화책은 재미있다. 학교 선생님이 "재미있어? 직장인들이 봐야 재미있지 않음??" 이러셨는데오히려 정말 사회 생활이 내가 공부하면서 힘들다고 하는 거에는 비할 바가 아니라는 걸 깨달았다.왠지 모를 공감도 되고 재미있다. 나중에 드라마로도 봐야겠다. 2017. 9. 24.
[BOJ]14726번: 신용카드 판별 14726: 신용카드 판별 숫자로 해도 되고 문자열로 해도 되는데 나는 문자열로 구성했다. 구현~ 12345678910111213141516171819202122232425262728293031323334353637383940#include int N;char num[10001][1001]; bool f(char a[]){ int sum = 0; for (int i = 15; i >= 0; i--) { if ((i + 1) % 2 != 0) { if ((a[i] - '0') * 2 >= 10) { a[i] = ((((a[i] - '0') * 2) / 10) + ((a[i] - '0') * 2) % 10) + '0'; } else a[i] = (a[i] - '0') * 2 + '0'; } } for (in.. 2017. 9. 24.
[BOJ]2605번: 줄 세우기 2605: 줄 세우기 풀이이 문제는 여러가지 방법으로 풀 수 있다는 생각을 했다.스택으로도 풀 수 있고, swap으로도 풀 수 있다는 생각을 했지만 나는 swap으로 했다. 별로 추천하고 싶은 방법은 아니지만 도저히 이 방법 밖에는 생각이 나지 않았기 때문에 이 방식으로 문제를 해결했다. 1) 우선 나는 1부터 n까지의 숫자를 배열에 다 채웠다.2) 반복문을 i = 0 ~ i < n 만큼 도는데, 변수 idx의 값은 i에 따라 바뀐다.(순서대로 돌기 때문에)3) 뽑은 번호를 x라고 할 때 x == 0이면 아무런 행동도 취하지 않으므로 continue를 해주고 나머지 경우에는 x번 만큼 반복문을 돌면서 swap을 해주면 된다. 4) 마지막 출력!!! 아직도 잘 모르겠다고요? 네 충분히 이해합니다. 저도 다.. 2017. 9. 3.
[BOJ]2309번: 일곱 난쟁이 2309: 일곱 난쟁이 풀이무식하게 brute force를 해보자. 제한된 상황에서는 이런 좋은!! 알고리즘이 어디 있겠는가. 처음에 어떻게 풀어야 할 지 모르겠어서 헤맸다. 나는 어떻게 풀었냐면 일단 9명의 키를 다 더한다.그리고 키 순서 대로 정렬을 시켰다. 반복문을 돌면서 sum - (i번째 값 + j번째 값) == 100이 되면 i와 j의 인덱스를 저장해서 출력을 할 때 그 인덱스는 거르고 출력 할 수 있게 했다. 코드123456789101112131415161718192021222324252627282930#include #include using namespace std; int arr[9], i, j, sum =0, save_index1, save_index2; int main(){ for .. 2017. 9. 3.
[BOJ]2783번: 삼각 김밥 2783: 삼각 김밥풀이단순 구현 문제다. 나는 1g 당 가격으로 주어지는 값 마다 비교해서 최소값을 구한 것을 *1000 해주었다. 코드 1234567891011121314151617181920212223#include double MIN(double a, double b, double c){ return a > b / c ? b / c : a;}int main(){ int get; double numx[101], y[101], omg = 0, ori, pri; scanf("%d %d", &pri, &ori); omg = pri / ori; scanf("%d", &get); for (int i = 0; i 2017. 9. 3.
[BOJ] 2477번: 참외밭 링크 : https://www.acmicpc.net/problem/2477 2010년 초등부 3번 문제다. (4,5번은 나중에 풀어봐야겠다) 이 문제는 입력 값이 어떻게 주어지든 간에 이.어.져.서 주어진다는 것을 이용하면 된다.직사각형 넓이 최대값 구하는 것은 쉽고 (가로, 세로 MAX 값 구해서 곱해주면 된다. 이것 또한 가로, 세로는 연결되어 있으니깐 잘 이용하면 된다!),작은 직사각형을 구해서 빼줘야 한다. 근데 여기서 알아야 할 것이 참외밭은 무조건 육각형이라는 것이다.그렇기 때문에 가로, 세로의 최대값이 나온 지점에서 가로의 index를 i라고 하면 i를 +3, +4 해준 값을 곱하면 작은 직사각형이라는 것이다!"잘 모르겠으면 그림을 보면서 비교를 해보자."그렇게 해서 최대 직사각형 넓이를 구.. 2017. 8. 26.

티스토리툴바