전체 글
[백준] 다각형의 면적
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 주어진 N개의 점들이 순서대로 이어져 다각형을 구성하게 될 때, 해당 다각형의 넓이를 계산하는 것이 문제입니다. 기본적으로 "삼각형 여러개로 쪼개서 구하는 것이 좋지 않을까" 라는 생각이 가장 처음 듭니다. N각형은 분할된 N-2개의 삼각형의 넓이의 합으로 구할 수 있기 때문입니다. 그러면 이 삼각형의 넓이를 어떤 방식을 이용하여 구하는 것이 가장 효율적일까요? 물론 많은 방법이 있지만, ..
[백준] 최소 스패닝 트리
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 문제 제목에서 의미하는 것과 같이, 최소 신장 트리의 cost를 return 해야 하는 문제입니다. 최소 신장 트리는 Kruskal 알고리즘이나 Prim알고리즘을 사용한다고 합니다. Prim 알고리즘의 경우 아직 한번도 구현해 본적이 없어서 예전에 파이썬으로 구현해본 Kruskal알고리즘으로 구현하였습니다. 실제 구현..
[서울] 명동 케이코쇼텐
명동의 케이코 쇼텐. 인스타에서 스마일 카레로 보고 방문했다. 카레는 내기준으론 양도 딱 적당했고 맛있었다. 딱 밸런스가 맞는 느낌이였다. 조금 맵기는 하다. 가격도 생각보다 비싸지 않고 합리적이다. 가게 내부 인테리어도 볼만했다.
[대전] 선화동 카라멜
예전부터 웨이팅이 길어서 못먹어본 카라멜에 왔다. 오픈 전 몇시부터 웨이팅 받으니 잘 찾아보고 시간 맞춰서 가야한다. 뇨끼도 유명하다고 하는데 두명에서 뭔가 메뉴 조합하기가 어려워서 뇨끼는 담에 먹어보는 것으로.. 라구파스타 안에 고기도 많고, 완전 맛있어서 대만족. 그리고 스테이크 시키면 리조또도 같이 나와서 둘이 같이먹으면 완전 맛있다.
[백준] 벡터 매칭
https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 점들이 N(짝수) 개 찍혀 있고, 이 점들을 둘씩 이으면 벡터가 생기게 됩니다. 이런 벡터들의 합의 최솟값을 구하는 문제입니다. 어렵게 생각하지 말고, 벡터의 합은 각각의 성분들을 더하면 되는 것을 생각해봅시다. 만약 이렇게 두개의 벡터가 있다면, 벡터의 합은 이 되고 이 길이가 우리가 구하는 벡터의 합의 길이입니다. 한마디로, N개의 점들중 시작점 N/..
[백준] 알파벳
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 보드의 각 칸에 알파벳 대문자가 적혀있는 상황입니다. 이 때, 알파벳이 겹치지 않게 가장 좌측 위에서 이동을 할 때, 총 몇개의 알파벳을 최대로 밟고 지나갈 수 있는지를 구하는 문제입니다. bfs나 dfs를 사용해야 할 것으로 짐작할 수 있습니다. 여기에서 만약 bfs를 사용하게 되면, 저장해야 하는 상태로 판의 상태도 있을 것이기 때문에 관리가 어렵습니다..
[백준] 녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제부터 간단하게 요약하면, N*N의 모양의 동굴을 통과하는데, 각 칸에서 돈을 빼앗기게 됩니다. 가장 왼쪽 상단에서 출발해서 가장 오른쪽 하단에 도달할 때 까지 최소한으로 돈을 빼앗길 때, 얼마를 빼앗기는지 구해야 하는 문제입니다. bfs를 이용하여 문제를 해결할 수 있습니다. 동굴 모양과 같은 비용 저장 array를 둡니다. 그리고 매번 상하좌우를 체크해보고, 해당 칸으로 진..
[백준] 알고스팟
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 우선 문제부터 요약하면, 미로에 사람들이 갇혀있는데, 미로의 어떤 부분은 빈 방이 아니라 벽이라고 합니다. 벽을 부시는 횟수를 최소화 해서 가장 왼쪽 상단에서 가장 오른쪽 하단으로 이동하려 할 때, 최소로 벽을 부시는 횟수를 구해야 하는 문제입니다. 많이 나오는 미로 찾기 문제 유형입니다. bfs를 이용하였고, bfs의 상태가 발전하는경우 (즉 queue에 넣는 경우)는 해당..