본문 바로가기

Algorithm

 (117)
[SWEA] JAVA - 5215 햄버거 다이어트 주어진 햄버거 정보에서 어떤 햄버거들을 선택했을때 최대 칼로리 이하이면서 최대 만족도인지를 찾는 문제이다. 선택할수있는 햄버거들의 조합을 구한뒤 최대 만족도를 가지는 햄버거의 조합을 찾아야한다. 재귀함수를 사용해서 풀었는데 이 함수에서 파라미터로 전달해야할것은 몇번째 햄버거를 선택할것인지를 결정하는 인덱스, 현재까지 선택한 햄버거의 만족도 합, 현재까지 선택한 햄버거의 칼로리합이다. 1. idx 번째 햄버거를 선택 할 수 있다면(idx번 햄버거 칼로리와 이전까지 저장된 햄버거 칼로리를 더했을때 최대 칼로리를 넘지 않는다면) idx를 선택하거나 선택하지 않거나 두가지 경우로 분기한다. 2. idx 번 햄버거를 선택 할 수 없다면 다음 idx 햄버거를 고르러 간다. 3. 모든 햄버거를 다 탐색했을때이거나 현..
[SWEA] JAVA - 1861 정사각형방 package com.ssafy.off; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class SWEA_1861_정사각형방 { /** * 깊이우선탐색 * 이동할수있는 방의 개수가 동일한것이 여러개면 가장 작은 방 번호 출력 */ static int dy[] = {-1,1,0,0}; static int dx[] = {0,0,-1,1}; static int[][] map; static int ans; static int startRoom; //시작점부터 최대한 많은 거리를 도착했을때 내가 이동한 거리를 리턴 pub..
[SWEA] JAVA - 3499 퍼펙트 셔플 (설명 오늘내로 업로드 예정입니다!!!) N개의 카드가있으면 이를 정확하게 반으로 나누고 나눈것들을 교대로 카드를 뽑아 새로운 덱을 만드는 문제이다. 이때 반으로 나눈 카드들을 각각 맨 앞에 있는 카드를 먼저 뽑아야 한다. 맨 앞에 있는 카드를 먼저 뽑아야 하는 순서를 지켜야 하기 때문에 Queue 를 활용하여 풀었다. 이때 N이 홀수일경우 먼저 놓는쪽에 한장이 더 들어가게 처리해줘야 하기 때문에 N이 짝수인 경우와 홀수인 경우를 나눠서 처리해줬다. 1. 카드를 반으로 나눈것들중 왼쪽의 카드와 오른쪽의 카드를 저장하기 위한 left, right 큐를 만들었다. 2. left 큐에서 한장뽑은다음 right 큐에서 한장을 한쪽의 큐가 모두 비어있을때까지 반복해주었다. 3. 이렇게 뽑힌 카드들의 순서를 저장하..
[SWEA] JAVA - 1210 Ladder1 (설명 오늘내로 업로드 예정입니다!!) 재귀함수로 문제를 풀고싶어 y=0이고 좌표값이 1인 x 좌표들 중에서 출발하여 y가 마지막 행 까지 도달할때 해당 x 좌표값을 반환하는 재귀 함수를 구현하려고 시도하였습니다. 하지만 이렇게 시작을 문제에서 주어진대로 접근하는 경우 보다 문제를 거꾸로 뒤집어서 도착점~출발점 을 찾아가는 방식으로 풀어야 한다는것을 배운 문제였습니다. 우선 도착점에서 시작하여 좌,우 방향으로 방향 전환이 가능할경우 방향 전환을 해주었습니다. 만약 좌우 방향 모두 이동할수없을 경우 전진 이동을 해야합니다. (저는 좌우 방향의 이동 우선순위가 더 높은줄 모르고, 이동 분기점에서 제일 첫번째 if문에 직진이 가능할 경우를 설정해서 코드를 수정했습니다 ㅠㅠ) 재귀함수로 구현한 go 함수에서 y..
[SWEA] JAVA - 1873 상호의 배틀필드 (설명 오늘내로 업로드 예정입니다!!) 처음 문제를 읽고 잘못 이해해서 엄청 헤맸다ㅠㅠ 첫번째로 헤맨 부분은 방향 명령어가 들어온다면 이동하거나 이동할수없을때(벽돌벽이던 강철벽이든 물이든) 모두 방향전환을 먼저 처리해줘야하는걸 놓쳤다. 두번째로는 전차와 포탄의 좌표는 별개의 값이므로 각각 처리해줘야한다. 만약 포탄을 발사했는데 계속해서 평지이면 포탄을 계속 이동시킨다. 문제를 처음 읽었을땐 풀만한데?ㅎㅎ 이러고 풀었다가 정말 정말 반성했다. 이렇게 잘못짜버린 코드를 쉽게 버릴수도없고 테스트 케이스도 99개?중에 80개가 맞게 나와서 더욱 힘들었다. (결국 같은반 알고리즘 스터디 조원으로부터 방향처리가 잘못됐다는 지적을 받아 풀수있었다^-ㅠ 고마워 우재!! ) 지난주부터 알고리즘 보충수업을 들으면서 교수님..
[SWEA] JAVA - 1223 계산기2 중위표기법을 후위표기법으로 바꾼다음 계산 결과를 출력하는 문제입니다. 분명 이번주에 배웠는데 중위표기법을 후위표기법으로 바꾸는 부분이 잘 떠오르지 않아 구글링해가며 로직을 다시 이해했습니다. 이 문제에서는 '+', '*' 연산자만 나오기 때문에 연산자 우선순위를 간단하게 비교할수 있습니다. 먼저 중위표기법을 후위표기법으로 바꿀때, 피연산자를 만나면 후위표기법 리스트에 저장합니다. 만약 연산자가 들어온다면 이 연산자가 입력값(연산자)과 우선순위를 비교하여 우선순위가 높은 연산자를 pop해준뒤 다음 새로운 연산자를 스택에 넣어줍니다. 그 다음으로 연산자 스택에 쌓여있는 값들을 모두 후위표기법 리스트에 붙여줍니다. 마지막으로 후위표기법으로 표시된 리스트에서 연산작업을 해줍니다. 아래와 같이 동작합니다. 피연산..
[SWEA] JAVA - 1225 암호생성기 8개의 숫자를 앞에서부터 차례대로 1~5까지 감소시키고 맨앞의 원소를 감소시키면 감소된값을 다시 tail 로 붙이는 작업을 반복한다. 이러한 과정을 반복하기때문에 Queue를 사용해서 풀었다. 1~5까지 감소시키는 과정이 한 싸이클이다. 이렇게 계속 싸이클을 진행시키다가 0보다 같거나 작아지는 원소가 발생할때 이 원소를 0으로 유지한다음 종료시킨다. package com.ssafy.off; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SWEA_1225 { static int[] password; private static void solve(int[] password) { Queue q..
[SWEA] JAVA - 1218 괄호 짝짓기 열린괄호만을 저장하고 닫힌 괄호와 가장 최근에 저장한 열린 괄호와 매칭 시켜주기 위해 스택 자료구조를 사용해서 풀었습니다. 만약 닫는 괄호가 왔는데 스택이 비어있다면 잘못된 괄호이고, 스택의 pop 원소와 새로 들어오는 괄호의 짝이 맞지 않아도 잘못된 괄호입니다. 이때 각 괄호마다 짝을 지어주기 위해 HashMap 의 Key-Value 특징을 사용하여 Key 값에 열린 괄호들을 넣고 Value에는 닫힌 괄호들을 넣어 서로 짝을 지어줬습니다. (다른분들의 코드를 보니 case방식으로 짝을 많이 맞춰줬는데 좋은 방법인것같습니다.) package com.ssafy.off; import java.util.HashMap; import java.util.Scanner; import java.util.Stack; p..

티스토리툴바