본문 바로가기

Algorithm

 (117)
[백준] JAVA - 1620.나는야 포켓몬 마스터 이다솜 생각 1번부터 N번까지의 포켓몬의 이름을 입력으로 받고 M개의 포켓몬의 정보를 통해 해당 포켓몬의 이름이나 번호를 출력하는게 문제입니다. N과 M이 100000이하의 자연수이고 포켓몬의 이름이 최대 20이기 때문에 일반적인 반복문을 통해 포켓몬의 정보를 찾으려면 N*M*20 대략 2천억번의 연산이 필요합니다. 따라서 O(1)의 시간복잡도를 가진 해쉬맵을 사용하여 문제를 풀었습니다. 우선 포켓몬의 이름을 Key, 번호를 Value를 가진 해쉬맵을 만들고 반대로 번호를 Key, 포켓몬의 이름을 Value로 가진 해쉬맵을 만들었습니다. 다음으로 포켓몬의 번호가 입력으로 들어왔을때 문자열이 숫자인지를 판별한다음 포켓몬의 번호를 Key로 가진 해쉬맵에서 포켓몬의 이름을 출력하도록 했습니다. 반대의 경우에도 동일한..
[백준] JAVA - 18429.근손실 생각 운동키트의 중량이 같다고 하더라도 이를 모두 다르게 보기 때문에 모든 경우의 수를 탐색해야하는 순열로 생각하여 풀었습니다. 가능한 경우를 생성하고 이때 N일동안 근육량이 500이상이 되는지 체크한뒤 가능한 경우의 수를 카운트하였습니다. 이번 문제에서는 순열을 비트마스킹을 통해 생성했습니다. permutation함수에서 cnt는 현재까지 뽑은 순열 원소의 개수를 의미하고 flag 는 선택한 원소의 비트정보를 나타냅니다. 이때 flag를 통해 선택한 원소인지를 판단할 수 있습니다. N개를 나열한다고 했을때 i번째가 선택됐는지 아닌지를 비트연산인 (flag & 1
[백준] JAVA - 1063.킹 생각 명령어를 차례대로 받아 마지막 위치를 구하는 문제입니다. 이때 체스판에서 가장 아래가 1이고 가장위가 8임을 유의해서 dy,dx 방향 설정을 해줘야합니다. 처음 주어진 킹과 돌의 위치를 parsing해서 좌표값으로 설정해줬습니다. 명령어를 실행하면 킹을 먼저움직여줍니다. 킹의 다음 좌표가 범위 밖이면 continue시켜 다음 명령어를 실행시켜줍니다. 만약 킹이 돌과겹치게된다면 돌을 킹과 같은 방향으로 움직여줍니다. 이때 바로 좌표를 업데이트 시켜주지않고 다시 범위를 체크한다음 돌이 범위에 벗어나지 않을때만 해당 명령어를 모두 적용해줘야합니다. (킹,돌 모두 좌표 업데이트) 이때 돌이 범위에서 벗어난다면 명령어를 모두 수행하지 않아야하기때문에 check함수가 true일때만 좌표를 업데이트 시켜준것입니..
[백준] JAVA - 1018.체스판다시칠하기 생각 처음에 BFS 로 풀려고 했습니다. BFS가 진행될때 같은 depth들은 색깔이 모두 동일해야한다라는 생각을 가지고 구현했지만 계속 답이 안나와서 결국 BFS를 포기하고 B,W색깔이 반복되는 인덱스들의 규칙을 찾아서 문제를 다시 풀었습니다. 사방탐색을 하지 않는 문제인데 굳이 BFS로 접근했습니다. 문제를 보고 계속 어떤문제인지 혼자 판단하고 이 틀에 맞춰서 문제를 푸는 습관을 버리도록 노력해야겠습니다. 시작이 B일때와 W일때 무엇이 최소값인지 모르기 때문에 두가지 경우를 모두 체크했습니다. 시작이 W일때 행과 열의 인덱스 합이 짝수일때 B가 칠해져있으면 다시 칠해야 하는 경우입니다. 반대로 행과 열의 합이 홀수일때 W가 칠해져있으면 다시 칠해야 하는 경우입니다. 마찬가지로 시작이 B일때도 동일하게..
[백준] JAVA - 2559.수열 생각 K일이 주어졌을때 연속적으로 K일만큼의 온도의 합이 가장 큰지를 찾는 문제입니다. K일이 고정적으로 입력에서 받기때문에 이를 파라미터로 받아 반복문을 한번만 돌면서 찾으면됩니다. K 구간 만큼의 합을 구하는 함수를 따로 만들어 구했습니다. 이때 K 구간의 시작인덱스는 N-K와 같을때까지만 시작할수있습니다. Java code package com.java.algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 연속적인 며칠동안의 온도의 합이 가장 큰지? 이때 합 찾기 * 1
[백준] JAVA - 10158.개미 생각 개미가 2억번이나 도는지 모르고 처음에 dy,dx 방향값을 설정해놓고 매초 개미의 좌표를 구해주는 코드를 작성했습니다.. 시간초과가 나고 개미가 2억번을 도는걸 어떻게 처리해줄지 고민하다가 결국 구글링을 통해 이해했습니다 이해에 도움이 된 블로그 주소입니다! hanstemcell.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EA%B0%9C%EB%AF%B8?category=672485 위의 블로그를 보고 x좌표와 y좌표를 나눠서 생각한다음, 개미가 총 이동한 좌표에서 너비를 나눠주면 개미가 몇번 왕복운동했는지가 나옵니다. 여기서 나눈값이 홀수이면 이미 끝을 찍고 되돌아오는중이기 때문에 x=0인 쪽으로 다가오는 방향입니다. 반대로 짝수이면 x=w인 쪽으로 가고있는중입니다. 즉, ..
[백준] JAVA - 15686.치킨 배달 생각 주어진 치킨 집 N개에서 M개의 치킨 집을 뽑는 조합을 구한 뒤, 각 조합마다 주어진 최소 치킨 거리를 찾는 문제입니다. 처음에 문제를 읽고 도시에 있는 치킨집 중에서 최대M개를 고르라는 뜻을 1개,2개, ... ,M개까지 골랐을 각각의 모든 경우에 대한 부분집합 문제로 잘못 이해했다가 엄청 고생했습니다ㅠㅠ 재귀를 이용해서 combination을 구했지만 시간초과가 계속 나와 결국 해결하지 못하고 다시 nextPermutation을 이용해서 풀었습니다. brute force + 시뮬레이션 문제는 정말 많이 풀어봐야겠습니다 입력을 받을때, 치킨집과 집을 ArrayList 타입으로 받고 각각의 좌표를 클래스를 만들어 저장합니다. 치킨집의 총 개수는 치킨집 ArrayList의 크기이고, 최대 M개를 뽑는..
[백준] JAVA - 3109.빵집 가스관을 연결할때 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할수있고, 각 칸의 중심끼리 연결합니다. 문제에서 요구하는것이 가장 가스관의 최소 최대 거리가 아니기 때문에 가스관이 갈수있는 경우를 되돌아가서 다시 탐색하지 않는것이 핵심입니다. 그렇기 때문에 백트래킹 방법으로 풀어야합니다. 또한 가스관의 최대 개수를 구해야하므로 가스관이 오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선 순서대로 탐색을 해야 파이프라인의 최대개수를 구할수있습니다. 3방 탐색을 통해 다음 단계를 탐색하러 들어갑니다. 이때 방문 표시에 대한 흔적을 남겨야 탐색 여부를 판단할수있기 때문에 반드시 해줘야합니다. 탐색을 할 수 없는 위치라면 0을 리턴하고 더 이상 이동 할 수없다는 흔적을 남겨줍니다. 마지막까지 탐색..

티스토리툴바