algorithm
1.[백준] 내일로 여행 13168
문제풀이 해싱과 플로이드 와샬을 적절히 쓰면 쉽게 풀 수 있는 문제이다. 우선 노드가 string으로 들어오기 때문에 string을 int로 바꿔줄 필요가 있다. 이때 해싱을 사용한다. map을 이용해 지역의 이름을 숫자로 바꿔주면 배열에서 index 접근이 가능해
2.[프로그래머스]월간코드챌린지시즌2 후기
4월에 있던 시즌 1은 몰라서 참가를 못했지만 동기의 추천으로 시즌 2를 참가하게 되었다.4문제 이상 풀어야 상품 추첨 자격이 되지만 상품이 목적이 아니라 재미있을 것 같아 신청하게 되었다.2번까지 분위기는 좋았다 빠른 속도로 풀었지만 3번부터 막혔다.애초에 다른 케
3.[백준] 도로검문 2307
최단거리 문제로 모든 간선에 대해 막는다 생각하고 다익스트라를 돌린다면M(N+MlogN)이 나올 것이다. M 개의 간선 \* (N 개의 정점 초기화 + 다익스트라)사실 생각해 보면 최단거리에 포함되지 않는 간선은 막을 필요가 없다.어차피 그쪽으로 가지 않기 때문이다.
4.[백준] 문자열 화폐 17828
A를 최대한 배치한 후 문자열을 'Z'로 다채워도 X가 될수없기전에 'Z'로 다 채운다.'Z'로 다채워도 X가 26의 배수가 아닐 수 있기때문에 중간에 나머지에 해당하는 알파벳도 추가해준다.N이 X보다 크거나 N\*26보다 X가 큰 경우는 불가능한 경우다.solutio
5.[백준] 겹치는 선분 1689
선분의 좌표를 오름차순으로 정렬한다. 그 후 선분의 끝점을 기준으로 탐색한다.우선순위 큐를 이용해 현재 우선순위 큐에 들어있는 가장작은 끝점이 현재선분의 출발점 보다 작거나 같다면 해당 끝점을 빼준다. 왜냐하면 해당정점은 현재 추가하는 정점과 겹치지 않기 때문이다.이렇
6.[백준] 면접보는 승범이네 17835
다익스트라 문제로 K 개의 도시를 제외한 N-K 개의 도시를 출발 정점으로 모두 다익스트라를 돌려주면 당연히 시간 초과가 발생한다. 발상의 전환이 필요한 문제이다. 결국 특정 정점에서 K 정점으로 가는 최단거리는 K 정점에서의 최단거리라고 볼 수 있다.(단방향이기 때문
7.[백준] 골목 대장 호석 20183
다익스트라+이분탐색 문제이다.이분 탐색으로 골목의 요금의 최솟값을 구할 수 있다. mid를 골목의 최소 요금으로 잡고 이분 탐색을 돌리며 해당 금액보다 큰 간선은 다익스트라를 돌릴 때 continue 해주는 식으로 코드를 짜고 다익스트라가 끝났을 때 도착지점까지의 비용
8.[백준] 벽 부수고 이동하기 2 14442
bfs가중치가 1로 모두 똑같기 때문에 bfs로 최단거리를 구할 수 있는 문제이다.하지만 문제에서 벽을 k개까지 부수며 이동가능하다고 하였다. 그렇기 때문에 벽을 부숴야하는 상황에서는 벽을 부수는게 이득이다. 현재 x,y좌표에서 벽을 z개 부쉈을 때의 최단거리를 dxz
9.[백준] 팀빌딩 22945
문제풀이 > 투포인터 문제이다. 배열의 처음과 끝을 각각 포인터로 잡고 O(n)만에 해결해주면 된다. 중간에 어떤게 있던 양끝과 총 개수가 중요하기 때문에 가능하다. 코드 > solution 문제링크 > boj/22945
10.[백준] 시식 코너는 나의 것 23029
문제풀이 코드 > solution 링크 > boj/23029
11.[백준] 움직이는 미로 탈출 16954
bfs문제이다. 움직이는 방향은 제자리에 가만히 있는 것까지 총 9방향 탐색을 해주어야한다.각자의 벽을 하나씩 내릴수 없어서 캐릭터를 올려주며 해당 위치가 갈수있는지 비교해주면 된다.이동해야할 위치에 벽이 있는지와 이동하고나서 그 위치에 벽이 내려오는지 그리고 해당위치
12.[백준] 돌다리 건너기 2602
다이나믹 문제로 점화식은 dxz = 돌다리에서 x번째 y(위,아래)쪽이고 두루마리는z번째일때 경우의수이다. 위 3가지 정보를 가지고 재귀를 돌려주면 무난하게 해결할 수 있다.첫번째 두루마리에서는 어디서든 시작할 수 있으니 위 아래 전부 호출해준다.그 다음부터는 위쪽 아
13.[백준] 경사로 14890
처음에 테스트 케이스를 보지않고 경사로를 놓은 곳에 또 경사로를 놓는 경우라는 구문을 읽고 가로 세로 겹치면 안된다는 소리로 이해하고 코드를 작성했다. 2번테스트 케이스에서 막혀 직접 몇개가 나오는지 카운팅 해보고 가로 세로 각각 해당 구문이 적용이라는 것을 알았다.코
14.[백준] 로봇 청소기 14503
특이한 문제다. 결과값이 이상하게 나와 문제를 잘못이해하고 있나 테스트케이스2번을 그림판에 붙여놓고 손으로 어떻게 나오나 봤는데 스물몇개밖에 안나와서 뭐지 하고 코드를 봤는데 이상한 부분이 있어 수정하니 정답이 나왔다. 직접계산해보면 안나오지만 코드로 돌리니 나오는 기
15.[백준] 2048(Easy) 12100
4방향 탐색을 5번 총 4^5번 한다.(solve 메서드)매 탐색마다 맵 상태를 밀어준다.(move 메서드)매 탐색마다 맵을 새로 할당하여 맵이 달라져도 다른 탐색에 영향을 주지 않도록 한다.미는 쪽 방향에 따라 어떤 칸을 먼저 밀지 달리한다.(오른쪽으로 밀 때는 제일
16.[백준] 구간 나누기2 13397
n개의 숫자를 m개의 연속된 구간으로 쪼개어 각 구간의 최댓값과 최솟값의 차이(이하 가중치)를 최소로 만드는 문제이다. 파라매트릭 서치를 이용해서 문제해결이 가능하다.mid를 가중치로 정의하고 n개의 숫자를 순회하면 된다.list를 순회하며 현재 구간의 가중치가 mid
17.[백준] 톱니바퀴 14891
4개의 톱니바퀴중 회전하는 톱니바퀴를 기준으로 양옆으로 탐색한다.중간에 회전하지 않는 톱니바퀴가 나온다면 break해준다.톱니바퀴의 회전여부를 chk를 통해 관리해주고 순회가 끝나면 한번에 톱니바퀴를 돌려준다.(move메서드)해당과정을 k번 반복한다.solutionbo
18.[백준] 드래곤 커브 15685
초기에 이동한 정보를 어떻게 뒤에 까지 들고가야 할까를 계속 고민하다가 패턴을 써보고서야 규칙이 있다는 것을 알게되었다.위 코드는 실제 코드에서 이동을 위한 x,y증감 값을 저장해놓은 것 이다.0세대 : 0 1세대 : 0 / 1 2세대 : 0 1 /
19.[백준] 게리맨더링2 17779
문제풀이 삼성 문제가 그렇듯 문제에 나와있는대로 구현하면된다. 최대 나올수 있는 숫자는 100이다. 숫자의 개수가 최대 100개이고 넣을 수 있는 MAX값도 100보다 작거나 같은 자연수이기 때문에 최대 100이다. 아래는 r연산에 대한 구현 방법이다. 원본배열(a
20.[백준] 이차원 배열과 연산 17140
삼성 문제가 그렇듯 문제에 나와있는대로 구현하면된다. 최대 나올수 있는 숫자는 100이다. 숫자의 개수가 최대 100개이고 넣을 수 있는 MAX값도 100보다 작거나 같은 자연수이기 때문에 최대 100이다.아래는 r연산에 대한 구현 방법이다.원본배열(a배열)의 각 행에
21.[백준] 낚시왕 17143
해답은 문제에 나와있는 대로 구현하면 된다.나는 Map으로 상어를 관리했다. 상어를 입력받은 순서대로 인덱스를 부여해 Map의 키값으로 이용하고 Shark클래스를 만들어 좌표,속도,방향,크기를 멤버변수로 두었다. 상어를 이동시킬 때 직접 이동시키지 않고 각 인스턴스들의