본문 바로가기

분류 전체보기

 (88)
백준 2528 <사다리> 이 문제는 현재 위치에서 위로 올라갈 수 있는지를 판단해서 올라가는 구현 문제이다. 현재 위치에서 다음 계단으로 올라갈 수 있는 경우는 이렇게 3가지가 있다. 문제 풀이 현재위치에서 다음 위치로 올라갈 수 있으면 계속 올라간다. 계단을 이동시켜준다. (이동 끝점에 도착하면 방향을 바꿔준다.) 이동하기 이렇게 계속 진행해주다가 최고점에 도달하면 종료시켜준다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util..
SWEA 1824 <혁진이의 프로그램 검증> swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DFS로 풀었지만 DFS를 사용하려면 많은 생각과 방문처리가 필요한 문제였다. 우선 기본적으로 알아야 할 것은 각각의 위치마다 0~15 값을 가진 총 4개 (위, 아래, 좌, 우) 방향을 가질 수 있다. 그러므로 일반적인 boolean 2차원 배열이 아닌 visit[x][y][값][방향] 이렇게 표시된 4차원 배열이 필요하다. 이 문제를 DFS를 풀게되면 스택오버플로우가 발생하는 경우가 가장 많을 것이다. 재귀의..
백준 1445 <일요일 아침의 데이트> 골드 2의 문제 하지만 골드 2보다는 쉬운 난이도라고 생각한다. 이 문제에서 헷갈렸던 점은 언제 인접한 칸을 체크해주냐는 것이었다. 이렇게 밑줄 친 부분을 보면 이동 할 칸에 쓰레기가 있다면 옆을 살피지 않고 없다면 4방을 탐색해서 체크를 해주는 것이었다. 이 부분만 고려해 우선순위 큐를 사용해주면 쉽게 해결되는 문제이다. 문제 풀이 쓰레기를 가장 적게 밟은 것 중에 적게 옆을 지나간 횟수의 위치를 꺼내 준다. 4방향 탐색 후 이동할 칸에 쓰레기가 존재한다면 쓰레기 카운터를 증가시키고 그렇지 않다면 4방향을 탐색해 쓰레기가 있는지 확인해서 있다면 옆에 쓰레기 있는 카운터를 증가시킨 후 큐에 넣는다. 이렇게 꽃이 있을 때까지 진행하는 것이다. 우선순위 큐로 비교해주기 위한 class를 하나 생성해주었다. ..
백준 1238 <파티> 문제를 보면 어디 지점에서 어디까지의 최소거리 -->즉 다익스트라 알고리즘 문제이다. 각자의 위치에서 파티장소까지 가는 최소거리에 파티장에서 자신까지 오는 최단거리를 더하면 된다. 각자 위 위치에서 파티 장소까지 가는 거리는 즉 N-1*M 파티 장소에서 모든 장소까지 1*M 이므로 N*M으로 천만으로 충분하다. 문제 풀이 각자의 위치에서 파티 장소까지 최단거리를 각각 구해서 저장한다. 피티장소에서 모든 장소를 최단거리로 검색하며 각자의 위치 값에 더한다. 최소 출력! 문제를 많이 풀어보는것이 알고리즘의 실력이 느는 단계라고 할 수 있다. 그림처럼 주황색 학생으로 부터 파티까지 가는 최단거리 다익스트라를 구한다. 이처럼 모든 학생의 위치에서 파티까지의 최단거리를 다익스트라로 구한다. 그 후 파티 장소에서 ..
백준 2002 <추월> 생각하는 것에 따라 어려움과 그렇지 않음으로 나눠지는 문제 같다. 들어가는 차량이라면 이름이 처음 등장할 것이고 나오는 차량이라면 두 번째로 등장할 것이다. 이점을 유의해서 자기 차례에 자신의 차가 아니고 다음차량이 나오는 개수를 세주면 되는 문제이다. 자기 들어가는 차량이 몇번짼지 체크해주기 위해서 hashmap을 사용했고 key는 차 이름 value는 몇 번 짼 지를 넣어주었다. 풀이 순서 처음 등장한다면 hashmap에 차이름과 순서를 넣어준다. 시작 순서는 0번 부터 시작하고 hashmap에 있는 차가 또 나오면 순서를 확인하고 이후 번호면 count를 해준다. 이때 visit 배열에 방문처리를 함으로써 이미 나온 것을 표시해준다. 자신이 차례가 맞으면 나오지않은 순서중 다음 순서로 옮겨준다. 자..
백준 19591 <독특한 계산기 > 좀 까다로운 시뮬레이션 문제이다. 이 문제의 접근법은 앞의 연산자와 뒤의 연산자 즉 투 포인터를 이용하는 문제이다. 나는 이문제를 위해 연산자와 수를 따로 담기 위해서 두개의 Arraylist를 만들어 줬다. 그렇게 해서 하나는 수를 담을 하나는 연산자를 기록해두었다. 맨 앞에 - 부호를 처리하기위해서 수식의 맨 앞이 -이면 수를 담는 배열에 0을 넣어주고 부호에 -를 넣어줘 시작을 하도록 진행했다. 문제 풀이 숫자와 부호를 구별해서 각각의 ArrayList에 넣는다 (불필요한 0을 제거하면서 넣어준다) 시작점과 끝점의 부호를 비교해서 시작점은 증가하도록 끝점은 감소하도록 해서 같을 때까지 진행한다. 시작점과 끝점이 같을 경우 현재있는 시작점의 수와 끝점의 수를 부호에 맞춰 계산한다. 문제 해결방법의 1..
백준 3691 <컴퓨터 조립> 골드 5라는 난이도를 믿지 못할 문제의 난이도였던 문제이다. 이 문제는 모든 부품의 종류를 선택하는데 선택햇던 부품 중 가장 낮은 성능을 올려주는 것을 최우선으로 한다. 교체를 할때에는 가격이 낮은 순으로 성능이 좋은 것을 교체해준다. 풀이 방법 각 부품을 hashmap에 제품의 이름을 key로 arraylist에 저장할 위치번호를 value로 저장한다. arraylist의 속성을 우선순위 큐로 해서 각각의 부품을 가격순으로 정렬한다. 모든 부품을 선택하기 위해 각각의 arraylist에 꺼내어 새로운 우선순위 큐에 저장한다. 이때는 성능이 낮은 부품을 꺼내야 하기 때문에 성능 순으로 정렬되게 한다. 성능이 낮은 부품을 꺼내 해당 부품에서 가격이 낮고 자신보다 성능이 높은 것이 나올 때까지 진행한다. 성..
백준 1976 <여행가자> 플로이드 와샬로 풀거나 각각의 시작점을 두고 모든 방향을 DFS 또는 BFS를 하면 해결되는 간단한 문제이다. 다만 n^3승이기 때문에 각 도시들마다 돌때 이 방법을 수행해주면 200^3*1000 이므로 시간 초과가 난다. 이 문제에서 주의할 점은 현재의 도시 다음 계획에 속한 도시가 자기 자신일 수도 있다는 것이다! 문제 풀이 각각의 마을을 시작점으로 두고 dfs를 통해 방문할수 있는 곳을 새로운 이차원 배열에 표시를 한다. m개의 마을을 돌면서 방문할 수 없다면 boolean 값을 false로 두고 결과를 출력한다. 이렇게 모든 지점에서 방문할수 있는 마을을 체크하게 되면 n^3 만큼의 시간이 걸린다. 이렇게 해서 resultmap에 표시를 한다. m개의 마을을 순서대로 갈수 있는지 체크하는 것이다...
백준 20056 <마법사 상어와 파이어볼> 최근에 나온 삼성 역량 테스트 시뮬레이션 문제이다. 문제 풀이 순서 모든 파이어볼을 담을 queue를 이용해서 이동시킨다. 한자리에 모여 있는 수가 2개일 경우 결합과 분해가 일어나고 1개일 경우 바로 queue에 다시 넣어준다. K번을 수행하고 난 뒤 queue에 있는 무게를 더하면 된다. 파이어볼의 상태를 나타내기 위해 fire이라는 클래스를 선언했다. 또한 이동 후의 상태를 저장한 move 클래스를 선언했다. 파이어 볼을 이동하면서 주의해야 할 점은 이 과정을 해줘야 한다는 것이다. 파이어볼을 이동할 때 몇 개가 겹치는 지를 알아야 하기 때문에 ArrayList map [][]을 사용 또한 그것의 상태를 저장하기 위한 ArrayList al를 사용 다음 그림과 같이 처리를 한다. 그리고 모든 맵의 ..
백준 17135 <캐슬 디펜스> 조합으로 3명의 궁수를 배치하고 나서 게임을 진행하는 시뮬레이션 문제! 문제를 잘읽어보는게 포인트인 문제이다. 문제 풀이 M개중에 3개의 궁수위치를 조합으로 선택한다. 각각의 궁수 위치에서 D 이하이면서 가장 가깝고 왼쪽에 있는 적을 선택한다. 적은 한칸씩 당겨준다. 여기서 주의할 점은 같은 적을 때릴 경우가 있다는 것이다. 조합으로 궁수의 위치를 선택한다 D거리 이하중 가장 가깝고 왼쪽에 있는 것 선택!!! 그 이후 적을 죽이고 맵을 당겨오는 과정 여기서 생각해야 할 점 하나 더! 조합으로 선택한 후 적을 죽이고 맵을 당겨오는 과정이 있기 때문에 map을 복사해서 사용! 전체 코드 더보기 import java.awt.Point; import java.io.BufferedReader; import jav..

티스토리툴바