본문 바로가기

알고리즘/일반

백준 3085번: 사탕 게임 (JAVA) 문제 해석 인접한 사탕이 다른 색이면 서로 위치를 교환한다. 인접한 사탕이 같은 색이면 두 사탕을 먹을 수 있다. 연속으로 최대 먹을 수 있는 사탕의 최대 개수를 출력한다. 알고리즘 사탕을 채워놓은 행렬을 만들고 인접한 색이 다르거나 같거나 모두 교환을 진행하고 인접한 두 사탕을 가로로 골랐으면 가로로, 세로로 골랐으면 세로로 탐색하여 교환 후 최대 개수를 매번 비교하며 갱신한다. 한번 교환 후 이어서 다른 것을 교환하는 것이 아닌 교환 후 다시 원상 복귀를 해야 하는 문제였다. 코드 더보기
백준 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 (JAVA) 문제 해석 1원, 2원, 5원, 7원 동전을 보유하고 있다. 지불해야 하는 금액이 입력값으로 주어지고 해당 금액을 보유한 동전들을 이용해서 지불해야 한다. 단 동전 개수를 최소화하여 지불한다. 알고리즘 보유하고 있는 동전이 1, 2, 5, 7 이므로 dp[n]은 dp[n-1], dp[n-2], dp[n-5], dp[n-7] 중 최소값에 1, 2, 5, 7 중 하나의 동전을 사용하여 지불하면 된다. 코드 더보기
백준 14235번: 크리스마스 선물 (JAVA) 문제 해석 산타가 방문한 횟수 n이 주어진다. n개의 줄에는 a가 들어온다. a가 0이면 가지고 있는 선물 중 가장 가치가 큰 선물을 줘야한다. a가 0이 아니면 선물을 a개만큼 충전하고 각 선물의 가치가 주어진다. 알고리즘 보유한 선물의 개수가 유동적이므로 동적으로 리스트를 생성해야 하고 a 값에 따라 리스트에서 가장 큰 데이터를 출력하고 해당값을 삭제하거나 리스트에 데이터를 추가해야 한다. 코드 더보기
백준 5545번: 최고의 피자 (JAVA) 문제 해석 토핑 N개 중에서 여러 종류를 선택하는데 같은 종류는 한개만 선택할 수 있고 아무 토핑도 선택하지 않아도 된다. 피자를 1원 당 최대 열량을 내도록 하는 토핑 조합을 찾아야 한다. 토핑 가격은 모든 종류가 동일하다. 알고리즘 토핑의 가격이 모두 동일하므로 열량이 가장 큰 것부터 내림차순으로 하나씩 추가해가면서 1원 당 최대 열량이 되도록 하는 값을 찾는다. 이 문제를 풀 때 간과했는데 토핑을 하나도 선택하지 않는 것이 더 나은 경우도 체크해야 한다. 코드 더보기
백준 17952번: 과제는 끝나지 않아 (JAVA) 문제 해석 한 학기가 몇분인지 N이 입력값으로 주어지고 N분째에 주어진 과제의 정보가 주어진다. 과제는 주어질수도 있고 안주어질 수도 있다. 과제는 다른 과제를 하던 중이라도 분마다 가장 최근에 나온 순서대로 한다. 과제가 끝났다면 그 다음으로 최근인 과제를 이어서 마저 한다. 알고리즘 과제를 가장 최근에 나온 순서대로 하므로 스택을 이용해야 한다. 과제가 주어지는 경우와 과제가 주어지지 않는 경우로 나눈다. 과제가 주어지는 경우에 만약 과제 해결 시간이 1분이라면 바로 해결 처리하고 아니라면 해결 시간을 1분 줄인 뒤 스택에 넣어준다. 과제가 안주어지고 스택이 비어있지 않다면 가장 마지막에 들어온 과제를 한다. (과제 해결 시간을 1분 줄인다) 이 경우 가장 마지막에 들어온 과제의 남은 해결 시간이 0.. 더보기
백준 2852번: NBA 농구 (JAVA) 문제 해석 농구 게임은 총 48분 간 진행된다. 골이 들어간 횟수가 주어지고 그 횟수만큼 골을 넣은 팀과 넣은 시간을 입력값으로 준다. 1번 팀이 이기고 있던 시간, 2번 팀이 이기고 있던 시간을 구해라. 알고리즘 처음 골이 들어가고 두번째 골이 들어가는 순간부터 어떤 팀이 이기고 있던 시간을 구할 수 있다. 따라서 처음 기준 시간을 0분이 아닌 처음 골이 들어간 시점부터로 한다. 각 팀이 이기고 있던 시간을 총 합해주는 변수를 둔다. 이후 누가 이기고 있는지를 체크하며 저번 골이 들어간 시점과 이번 골이 들어간 시점의 차이를 위 변수에 알맞게 더한다. 시간을 계산할 때 번거로움을 피하기 위해 단위를 초로 변환하여 일괄 계산 후 마지막 출력할 때만 분과 초로 바꿔준다. 코드 더보기
백준 16165번: 걸그룹 마스터 준석이 (JAVA) <Map 활용> 문제 해석 총 걸그룹의 수와 문제 수가 주어진다. 걸그룹 팀 이름과 해당 팀의 인원수, 멤버가 주어진다. 문제 종류가 0이면 팀 이름이 주어져 해당 팀에 속한 멤버들을 사전순으로 출력해야 하고 1이면 멤버 이름이 주어져 해당 멤버가 속한 팀 이름이 출력되어야 한다. 알고리즘 걸그룹 팀 이름과 해당 팀에 속하는 멤버들을 매칭시키기 위해 HashMap을 사용한다. 팀 이름을 key, 멤버들을 value로 하는데 HashMap은 중복키를 허용하지 않으므로 value를 멤버들이 들어있는 List로 한다. -> HashMap 형태 코드 더보기
백준 13414번: 수강신청 (JAVA) <List와 Set> 문제 해석 과목 수강 가능 인원 K와 수강신청 버튼 누른 횟수 L, 수강신청 버튼을 누른 학생의 학번이 입력값으로 주어지고 한 번 누른 학생도 또 누를 수 있다. 대신 그 경우 수강신청 우선순위가 마지막에 누른 시점으로 밀려난다. 수강신청 성공한 학생들을 출력한다. 알고리즘 버튼을 누른 학생들을 조건을 검사하고 순서대로 List에 담는다. 조건은 List에 버튼을 누른 학생의 학번이 이미 존재하면 해당 학번을 삭제한다. 하지만 List를 사용할 시 ArrayList와 LinkedList 모두 시간 초과가 나온다. 검색해본 결과 Set을 사용해야 함을 알 수 있었다. 조건을 실행할 때 contains() 함수를 사용하는데 List는 O(N), Set은 O(1)의 시간 복잡도가 나오기 때문이다. 코드 더보기

티스토리툴바