방배동 고구마

문제 N개의 샘플이 있고 각각의 샘플에는 정수가 주어진다. 연구를 위해 N개중 2개의 샘플을 채취한다. 이때 샘플이 가진 정수의 합이 0에 가까운 2개의 샘플을 채취하고자 한다. N(2~100000), 정수A(-1000000 ~ +1000000) 이며 샘플의 정수 값으 오름차순으로 입력된다고 한다. 0에 가까운 값이 여러 경우일 경우 가장 빠른 번호의 샘플을 답으로 한다. 위 조건에 맞는 2개의 샘플 번호를 구하라 입력 5 -102 -58 59 78 101 출력 0 4 문제해결 조합 문제이다. N개의 샘플중 2개의 샘플을 고른다. 순서는 상관이 없다. 트리를 구성하는 DFS로 모든 경우의 수를 수행할 수도 있지만 N이 10만개이므로 시간복잡도 N제곱으로 timeout일 경우가 생긴다. 따라서 DFS는 적..

룩업테이블이랑 예상된 결과값을 미리 계산하여 놓은 배열과 같은 집합을 의미한다. 알고리즘 해결에 있어 룩업테이블을 활용해야하는 경우가 있다. 아래의 문제를 살펴보자 문제 주어진 map은 감염경로와 같다. N*N크기의 map에 숫자가 입력되어 주어지며 숫자는 미로의 길을 의미하는데 아래와 같은 정보를 가진다. 지도의 크기 N과, 병균의 위치가 주어진다. 병균은 주어진 지도의 경로를 통해서만 전염된다고 한다. 주어진 map에서 감염되지 않은 경로의 수를 구하라. 입력 4 0 0 2799 7439 0652 2172 출력 5 해결전략1-DFS 1. 주어진 좌표에서 DFS로 확산한다. 2. 확산시에는 방문하지 않은 경로, 경로가 연결된 지점만 확산한다. 3. 각 도로 모양에 따른 상하좌우 방문정보를 미리 Tabl..

핸드드립 커피도 매장마다, 바리스타마다 다양한 레시피가 있다. 커피는 워낙 레시피에 따라 다양한 맛이나기 때문에 깊이 들어갈 수록 매우 복잡하다. 그러나 나는 집에서 간단하고 가장 보편적인 것을 추구한다. 추구한다고 하니 뭔가 있어보이지만 사실 이것 저것 공부하면서 혼자 알아내고 결론낸 나의 생각이다. 간단 보편 레시피 일반적으로 커피는 1인분에 20g을 기준으로 한다. 원두와 물의 양은 1:15로 한다. 즉, 20g의 원두에는 300g을 물을 사용하여 추출한다. 1. 린싱 린싱은 커피필터에 뜨거운 물을 부어주면서 필터의 냄새도 빼주면서 드리퍼를 예열하는 역할이다. 꼭해주자. 2. 뜸 원두를 드리퍼에 20g 넣어주고 원두양의 3배의 양인 60g의 물을 부어 50초간 뜸을 들여주자. 뜸을 들이는 목적은 커..

변치않는 사랑 얼핏보면 장미로 알겠지만 리시안셔스라는 꽃이다. 줄여서 리시안이라고 많이 부른다. 꽃말은 '변치않는 사랑'. 참 좋은 꽃말이다. 꽃이 굉장히 우아하며 풍성한 느낌이다. 생화 상태로 집에서도 굉장히 오래간다. 색깔도 흰색, 보라색, 분홍색 등 굉장히 다양하다. 꽃을 선물하는 것은 정말 기분 좋은 일이다. 좋아하는 모습을 보면 참 행복하다. 지친 하루를 보내고 집으로 돌아와서 몸을 뉘울때 이런 예쁜 꽃을 보면 이내 마음이 정화된다. 오늘도 수고한 너에게 위안이 되었으면 좋겠다.

행복한 사랑 꽃을 참 좋아하는 아이인데 왜 이렇게 늦게 줬을까. 많이 후회된다. 좋은 날에 더 잘해줄걸, 앞으로 더 잘해줘야겠다. 장미는 누구에게나 친숙한 꽃이다. 분홍색 장미와 옥시페탈룸의 색감이 참으로 아름답다. 옥시페탈룸의 꽃말은 '날카로움'이다. 분홍색 장미는 '행복한 사랑', '사랑의 맹세'이다. 이렇게 좋은 꽃말들을 마음에 담아 그 사람에게 전해주다보면 내 마음도 전달 될 것이다.

대표적인 봄꽃 프리지아, 봄꽃이며 노란색을 띈다. 꽃말은 '천진난만, 새로운 시작'을 뜻한다. 우리의 시작을 응원한다는 뜻으로 사봤다. 꽃시장에서 처음 꽃을 사봤는데 상당히 괜찮은거 같다. 전문가의 손길을 거쳐서 만든 예쁜 꽃다발도 좋지만 내가 만들어주고 싶었다. 아이같이 좋아하던 모습을 잊을 수 없다. 처음 만져본 꽃이었지만 모양이 예쁘게 잡힌거 같다. 자주 예쁜 꽃을 사줘야겠다.

스택문제는 참으로 까다롭다. 경험으로 봤을때는 코드로 만들고나서 반드시 Test case를 손으로 똑같이 해봐야 하는 거 같다. 그래야 문제점을 발견할 수 있다. 또한 스택처리 반복안에서 분기를 치거나 첫노드를 먼저 Push하거나 하는 것은 좋지 못하다. 스택처리 반복이 복잡해질 수록 추적하기 어렵기 때문이다. 간단한 스택처리 Test case로 한줄한줄 한손한손 따라가면서 디버깅해보자. 문제 높이가 다른 N개의 전봇대가 주어진다. 서로다른 전봇대끼리 전깃줄을 잇는다. 1. 이웃한 두개의 전봇대는 전깃줄을 잇는 것이 무조건 가능하다. 2. 이웃하지 않은 두개의 전봇대 사이에 양측의 두 전봇대보다 높이가 높거나 같다면 전깃줄을 이을 수 없다. 위의 그림의 경우 5가지의 경우가 있다. 1번과 3번 전봇대는 ..

논리문제는 아이디어를 내기까지가 상당히 까다롭다. 결국 많은 경험이 필요하다. 다음 문제를 보자 문제 N*N의 영역이 주어진다.(N : 2~10000) 해당 영역에 먼지가 떨어져 있다. 청소를 단 한번 할 수 있다. 청소 구역의 둘레 길이 L(4~100이며 짝수이다)이 주어진다. 먼지의 개수는 M(1~100)으로 주어지며 먼지의 X,Y좌표값이 주어진다. 주어진 L의 조건에서 청소 시 가장 많이 제거할 수 있는 먼지의 갯수를 구하라 입력 6 10 6 2 2 4 6 5 2 6 4 2 4 3 3 출력 4 접근방법 주어진 케이스는 아래와 같다. 청소영역 둘레가 10이라 청소영역 가로세로 2*3 조합도 가능하고 1*4 조합도 가능하다. 아이디어를 생각해본다. 1) 간단하게 N을 기준으로 모든 영역을 수행한다. N..

[문제] N*N(N : 4~ 10) 크기의 도화지에 색종이를 붙인다. 색종이는 직사각형 모양이다. 이때 겹쳐 붙일 수 있다. 색종이는 숫자 1부터 9까지 나타나며 빈 도화지는 0으로 나타낸다. 가장 많이 겹쳐진 지점의 색종이 수를 구하라. [입력] 4 1591 1496 1444 0550 [출력] 4 [접근방법] 주어진 입력을 그림으로 표현하면 아래와 같다. 앞선 덧칠 문제와 굉장비 비슷한 접근 방법이다. 1. 색깔 별로 minX, minY, maxX, maxY의 값을 구한다. for문으로 탐색하여 좌표별 최고 최소 값을 구하면 될것이다. 2. 구한 좌표를 저장해둔다. 구조체 배열을 사용하면 편리하겠다. 3. 저장된 좌표값을 차례로 visit 배열에 count올린다. 4. visit배열에 가장 큰 값을 찾..

문제 꼬리잡기 게임을 한다. 일직선 상에서 진행하며 모두 동시에 출발하지만 출발 위치와 속도는 다르다. T분동안 게임이 진행되며 일직선 상이기 때문에 추월할 수 없고 속도가 빠른 뒷사람의 앞사람의 꼬리를 잡으면 하나의 그룹으로 인식된다. 주어진 조건에서 몇개의 그룹이 형성되는지 구하라 입력 참가자 수 N : 1~100,000 게임시간 T : 1~1,000,000,000 각 참가자출발 위치 P : 0 ~ 1,000,000,000 각 참가자 속도 S : 0 ~ 1,000,000,000 ※ 출발위치는 오름차순으로 입력됨 5 3 0 1 1 2 2 3 3 2 6 1 출력 3 접근방식 아주 간단하게 생각해보자. 1. 각 참가자의 계산된 T분 후 위치를 구한다.2. 뒷 사람이 앞사람보다 위치가 클 경우, 앞사람의 위..

Greedy 알고리즘은 모든 경우의 수에 대해 수행하지 않는다. 즉, 모든 문제에 Greedy를 적용할 수는 없다. 최선의 선택을 해가다 보면 최종적인 해답이 나온다는 개념이다. 예를 들어 10원, 50원, 100원 짜리가 있고 160원을 만든다고 할때, 최소의 갯수로 만든다고 하자. 최소의 갯수로 만들기 위한 최선의 선택은 큰 동전 부터 사용해가는 것이다. 즉, 100원 1개 / 50원 1개 / 10원 1개, 총 3개가 답이 되겠다. 그러나 120원짜리 동전이 있다고 가정해보자. 이때 역시 큰 동전부터 선택하게 되면 120원 1개 / 10원 4개로 총 5개를 선택하게 된다. 즉 오답이다. Greedy알고리즘은 모든 경우에 적용할 수 없다. 120원짜리 동전의 선택이 적용되지 않는 이유는 100원짜리 동..

문제 주어지는 노드사이에는 최대 1개의 도로가 있으며 양방향 도로이다. 도로에는 가중치가 있으며 노드간 이동시에는 최단 경로로 이동한다. N, 노드 수 : 5~100 M, 도로 수 : 5~5000 D, 노드 사이의 거리 이때 각 노드를 출발점으로 할때 도착 노드까지의 거리가 가장 먼 거리를 X라고 하자. 노드 중의 X가 가장 작은 X의 값을 구하라 입력 N과 M이 입력되며 노드A와 노드 B 사이의 거리 D가 아래와 같이 입력된다. 5 7 1 2 5 3 2 14 2 4 5 1 3 10 4 3 15 5 4 15 3 5 8 출력 15 입력을 그래프로 표현하면 위와 같다. 접근방식 서로 다른 가중치가 있는 맵이므로 BFS로 접근이 유효하다. BFS는 크게 2가지 종류가 있는데, 가중치가 서로 다른 경우와 가중치..