본문 바로가기

전체 글136

가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열 백준 11053번 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 주어진 수열에서 길이 1부터 N까지 끝의 수가 n일 때, 가장 긴 증가하는 부분 수열을 구한다고 해보자. 즉, d[N] = N길이의 수열에서 마지막 값이 n일 때 가장 긴 증가하는 부분 수열 이된다. ※ 부분수열을 구하는 것이기 .. 2023. 1. 16.
숨바꼭질3 숨바꼭질 3 백준 13549번 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 이 문제는 다음 노드로 이동(걷거나 순간이동)할 때의 가중치가 1 또는 0으로 균일하지 않다. BFS로 풀 수 있는 문제들은 가중치가 균일해서 Queue에 가중치 합이 작은 순으로 순차적으로 들어오게 되어있다. 그러나 이 문제는 가중치가 균일하지 않기 때문에 일반적인 BFS 방식으로 문제를.. 2023. 1. 9.
Tripagram 회고 Tripagram 회고 11월에 여행 정보 공유를 주제로 한 서비스를 개발하기 위해 팀 단위 프로젝트를 진행하였다. 프로젝트는 11월 8일부터 12월 7일까지 약 한 달 동안 진행되었다. 여기서는 해당 프로젝트를 진행하면서 느낀 점이나 경험한 것들을 기록하려고 한다. 1. 내가 뽑은 내 팀원 이번 프로젝트는 랜덤으로 팀이 정해질 수도 있었지만 내가 직접 팀원을 고를 수 있었다. 나는 랜덤으로 팀이 정해지는 것보다 내가 주도적으로 팀원을 선택하고 싶어서 직접 팀원을 선택하기로 했다. 직접 팀원을 고르려고 하니 내가 직접 팀원을 고를 때만 보이는 것이나 느낄 수 있었던 것들이 있었다. 팀원을 직접 선택하려고 하니 많은 사람들이 후보군으로 내 머릿속에 올라왔다. 각자 다 장점이 있었고 이 중에서 한 명을 뽑는.. 2023. 1. 2.
퍼-즐 퍼-즐 백준 1525번 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 우선 나는 2차 배열인 퍼즐을 1차 배열로 변환하고 문제를 풀었다. 문제를 풀 때, 주어진 퍼즐의 원소를 이동시켜야 하는데 2차 배열보다는 1차 배열이 다루기 더 쉬울 거 같았기 때문이다. 2차 배열의 각 위치를 1차 배열로 표현할 수 있기 때문에 1차 배열로 변환해서 문제를 푸는데 전혀 문제가 되지 않는다. [1차 배열로 변환] 문제는 간단하다 목표 상태에 도달하기 위한 행위의 최솟값을 구하는 것이기 때문.. 2023. 1. 2.

티스토리툴바