Algorithm

BFS와 메모이제이션을 사용하여서 풀었다. 전형적이었다.

https://www.acmicpc.net/problem/17626 미리 제곱을 구해서 저장해주면 최대수인 50,000의 sqaure root까지만 계산해주면 되므로 시간복잡도가 훨씬 줄어든다.

알고리즘 공부를 하면서 지식이나 여러사이트들의 문제 풀이를 올릴 예정입니다.아직 많이 부족하니 경험이나 지식,조언 등을 공유해주시면 감사하겠습니다.

컴퍼러블을 사용하여 회의가 끝나는 시간 기준으로 정렬을 해주었다. 가장 빨리 끝나는 회의가 먼저 시작해야 다음에 가장 먼저 시작하는 회의를 시작하여 최대 회의의 갯수를 찾을 수 있다. 처음에 끝나는 시간 기준으로만 정렬을 해주어서 오답이 나와서 확인해보니 7 5 와 7

알고 스팟의 Pi문제 입니다.

알고스팟의 LIS문제이다.스코프의 개념에 대해서 다시 찾아보았다 .예제를 다 읽고 풀었지만 스스로 하려고 노력해보았다 . 이전에 작성하였던 걸 가져오고있는데 스코프가 뭐더라..일단 내용은 메모이제이션.... 흠..

3.Review

예전의 나는 공부하기 싫엇나 보다..

백준 11403 경로찾기 문제입니다.

우선순위 큐를 사용하요 풀이를 하였다. 경우의 수를 적절히 나누어서 풀면 된다.

최소힙 코드를 가져와서 입력시 -1 출력시 다시 -1을 곱해주어서 간단히 해결하였다.

덱 개념을 이용하는 문제입니다.

3.Review

처음에는 StringBuilder로 문자패턴을 확인해주었는데 50점이 나왔다. 시간을 줄이기 위해서는 O(N^2)인 시간복잡도를 줄여줄 필요가 있었다. 따라서 IOI만 확인하는 방법을 사용하였다. IOI패턴이 등장하였을때 O는 검사하지 않고 다음에도 IOI가 반복되는지

U C P C 가 순서대로 존재하는지만 보면 해결되는 문제이다.

처음엔 전부 탐색했다가 시간초과가 나와서 해당 방법으로 풀이하였다. 우선 rx는 만족해야 하기에 rx를 기준으로 count를 늘려주었다. 탐색해야하는수가 엄청 줄어들었다.

1층짜리 토마토 문제 코드를 가져와서 조건에 맞게 수정해주었다.

처음에는 무식하게 숫자를 하나하나 배열로 해서 풀었었다... 그렇게 할 필요가 없엇는데...bfs를 이용하면 풀린다. 아마 StringBuilder와 객체Node를 사용하면 시간이 줄어들 것 같다.

최솟값힙을 가져와서 조건에 맞게 수정해주었다...

오늘부터 스터디를 시작했습니다. 스터디원들이 너무 좋습니다. 문제 리뷰를 하자면 저는 DFS로 풀었으나, 크루스칼로도 풀수 있을겁니다. 자세한건 주석으로 풀이해놓았습니다.

순열로 풀었습니당.

https://www.acmicpc.net/problem/10158음.. 처음에는 제자리로 오는 위치에서 시작하게 시간을 조절 해 주었는데, 0.15초로 풀기엔 너무 짧앗고 O(1)로 풀수있는 방법이 존재하였다.좌우, 상하로만 반복운동한다는것에 중점을 두고 풀

처음에 항목이 그리디라서 그리디하게 풀려했다가 많이 돌아간것 같다 . BFS로 풀면 간단히 풀린다.

문제 분류는 DFS/BFS로 되있던데... 왜징....

저렇게 풀면 될거같아서 풀었는데 알고리즘 이름은 모르겠다...

크루스칼을 문제에 맞게 적용하면 된다.

https://programmers.co.kr/learn/courses/30/lessons/42748문제 대로 하면 된다...

에라토스테네스의 체를 사용하여 소수를 미리 구해준다.그 후 순열을 사용하여 나오는 조합들에대해 소수인지 판별하고 중복을 방지하기 위해 HashSet을 사용하였다.

패턴을 저장해서 비교하면서 정답을 찾아갔다.

https://www.acmicpc.net/problem/17144출저 : 백준 17144번 문제 문제가 긴데 당황하지 않고 요구사항대로 작성하면 된다. 효율성은 잘 모르겠다... 하다보니 좀더 객체지향적으로 쪼갤수 있을 거같다...

아래서부터 접근하면 쉽게 풀린다. 최댓값이 되게 큰값을 합쳐주면서 올라간다.

순열에서 조건에 맞게 살짝 바꿔주었다.

전 문제에서 살짝 수정했다.....

StringBuilder를 이용하여 적절히 바꿔주었다.

전번의 N과M에서 살짝 수정만 하면 된다...

역시 전에 코드에 살짝 문제의 요구사항에 맞게 수정을 해주었다....

분명 한번에 성공했다 생각했는데 조건이 하나 빠져있었다. 오름차순으로 모두 정렬되는것이 중요한것 같다. 이 문제 역시 전 문제를 고쳐서 만들었다.

위에서부터 하던지 아래서부터 하던지 상관은 없다 진행하면서 칠할수있는 가장 작은 cost를 더해주면서 진행해나간다면최솟값을 찾을수 잇다.

아래서 두번째줄부터 그 아랫줄의 큰수를 합쳐가면서 위로 올라가면 된다.

https://www.acmicpc.net/problem/2636공기를 -1로 채워서 -1과 닿는 치즈를 녹여서 없애주는 작업을 반복하였다.

https://www.acmicpc.net/problem/1600BFS를 사용하면 얼추 된다. 중요한 점은 말처럼 뛴 횟수에 따라 방문 배열을 따로 해주어야지 모든 경우를 탐색 할수 있다.

말이 되고픈 원숭이와 비슷하다 BFS를 사용하고, 벽을 부쉇을때 안부쉇을때 방문배열을 달리 해주면 된다.

프림 알고리즘 적용

1.문제 2.코드 3.Review

DP와 이분탐색을 적용하였다.

거꾸로 찾아나가면 된다.

걸어갈수있는 거리인 1000을 넘는 거리는 못간다고 가정하고 플로이드 와샬 법칙을 적용하면 풀리는 문제이다.

https://www.acmicpc.net/problem/14502BFS와 순열이 적용되는 문제이다. 시뮬레이션문제가 그렇듯 시키는대로만 하면 풀리는듯...

플로이드 와샬 기본 문제

https://www.acmicpc.net/problem/17472여러가지 기법들이 적용된다... 처음에는 프림이 아니라 플로이드를 적용했었는데 모든것을 지나가는 길을 체크할 방법이 없었다. 그래서 프림으로 재구현하였다.

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030모두 탐색하는데 현재의 코스트가 최저cost를 이미 넘었으면 더 이상 탐색하지 않는다.

배낭 알고리즘의 기초 문제이다. 불필요한 배열을 줄이기위해서 역방향으로 진행을 하였다. 각각의 배열에는 (현재 배낭에 들어있는 가치)와 (현재 물건의 가치와 현재물건을 넣고 남은 자리에 넣을수있는 가치를 더한것)중 큰 값을 넣어준다.

BFS로 풀면 간단히 풀리는 문제이다. int형 범위를 넘을 수 있으니 long타입을 사용하도록 하자.

숨바꼭질1을 변형한 문제이다. 위치가 2가 될때는 시간이 소모되지 않는 차이점이 있다. 따라서 시간초과가 걸리지 않는 2를 먼저 탐색해주어야 한다. 즉. 탐색 순서에 따라 정답여부가 갈린다. 이 문제에서 주의해야 할점이다.

이 문제는 숨바꼭질을 변형한 문제이지만 접근방식이 약간 다르다 .똑같이 BFS로 풀었다. 하지만 queue에 추가해주는 조건이 조금 까다롭다. 나는 동일한 횟수로 접근하는 방법을 구하기 위해서 방문을 했어도 동일한 시간에 접근을 했다면 queue에 추가해주는 방식을 사

골드4인데 골드5인 숨바꼭질보다 더 쉬웠다.... (개인적으로)그냥 숨바꼭질의 풀이에서 지나온 경로를 저장해주는 객체를 추가하였다.

일반적인 BFS문제와 비슷하다 .. 그러나 벽을 몇개 부쉇는지의 여부에 따라 방문배열을 달리 해주어야 하고 체크도 따로 해주어야 한다.

이 문제 역시 벽 부수고 이동하기 2와 비슷하다. 다만 고려사항이 더 추가되었다 .제자리에서 대기할수 있다는 것과 낮에만 벽을 부술수 있다는 것. 이때 불필요한 움직임을 없애주어야지만 시간초과가 나지 않는다 따라서 벽을 부술수 없는 낮에만 제자리에서 대기를 하고 벽을

일반적인 BFS로 풀려고 시도하였으나 시간초과가 나왔다. 그래서 BFS로 빈 공간의 구역을 나눠주고, 그 구역에 해당하는 곳을 다시 갈수있는 수로 다시 채워 주었다. 그리고 벽을 부순 뒤 상하좌우에서 겹치지 않는 곳만 더해주었다. 출력시 (값+1)%10을 해서 출력을

문자열과 컴페어러블에 대한 경험치가 많이 부족한거 같다... 연습해야겠다..

도착지점까지 갔을때 잃는 루피의 최소거리를 구해줘야 하므로 다익스트라 알고리즘을 사용하였다. 우선순위큐를 사용하여 시간을 줄여주었고 우선순위큐에서 컴퍼레이블을 사용하여 루피의 누적 수를 기준으로 poll을 하게 변경해주었다.

1.문제 2.코드 3.Review

https://www.acmicpc.net/problem/1194이 문제는 똑같은 BFS문제인데 방문여부를 어떻게 확인해주느냐에 따라 정답이 나온다. 열쇠를 습득한 종류에따라 방문배열을 달리 해주어야 하는데 이때 비트마스킹을 이용하면 편리하게 풀 수 있다.

https://www.acmicpc.net/problem/2458처음에 문제를 어떻게 풀지 방법을 생각하는게 어려웠다. 플로이드와샬을 적용하면 내가 갈수 있는곳, 나한테 올수있는곳을 체크할수 있다. 그 합이 N-1이 되면 그 수는 순서를 찾을 수 있다.

https://swexpertacademy.com/main/code/problem/problemDetail.do그냥 하라는거 하면 되는 구현문제

1.문제 2.코드 3.Review

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&probl

비트마스킹을 이용하여 경우의수를 판단한다.

https://www.acmicpc.net/problem/16235코드 한줄 잘못써서 꽤나 애를 먹었다........구현문제는 차분하게 차분하게 풀어야한다..

시간초과가 나서 어떻게 하면 값에 접근을 덜할까 하다가 슬라이딩 윈도우 개념을 적용하였다. 앞에껀 추가되고 뒤에껀 추가된다는 느낌으로 배열을 조절하였다.

이미 쓴 숫자인지만 확인하면 쉽게 풀린다.

https://www.acmicpc.net/problem/17471뭔가 풀기 귀찮았던 문제... 우선 순열로 팀 조합을 만들어 줘야 한다 이때 시간을 줄이기 위해서 가능한 적은 경우를 해야하는데구역이 5개일때 1 / 2,3,4,5 이 둘은 똑같은 경우이기때문에

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE&probl

https://www.acmicpc.net/problem/17141DFS사용 배치할 바이러스들을 스택에 넣어준다. BFS로 바이러스가 몇초만에 퍼지는지 확인한다.바이러스가 다 퍼졌는지 확인한다. \-끝-

https://www.acmicpc.net/problem/17142연구소 2와 똑같은 문제인데 다른 점은 어디서 검사를 해주느냐에 따라 답이 달라졌다.

https://www.acmicpc.net/problem/14500노가다 구현문제인것 같다.... 각각 블럭의 위치를 정해주었는데 쓰다보니 일부 대칭이 되는것이 있어서 그것을 이용하였다. 그림을 그려보고 좌표를 대입해보면 된다.

스택을 이용하여 풀었다. 원래는 StringBuilder에 문자열을 집어넣고 검사를 했었는데,시간초과가 나왔다. 스택을 이용하게 되면 O(N)으로 줄어들게 된다.

플로이드-와샬을 적용하면 풀리는 문제이다. 문제의 조건에서 다음 여행지가 출발지와 같으면 갈수 있다는 것으로 풀어야한다.

https://www.acmicpc.net/problem/1068child를 가지고있는 Node를 만들어서 활용하였다. 입력값은 부모로 생각하여 받아주었다. 설명은 주석으로 써놧으니 코드와 같이 읽으면 될겁니다.

뒤에서부터 접근하면 매우 쉽게 풀린다.

/ 백준 14226번 문제 이모티콘 BFS문제이다. 가장 빨리 해당 갯수를 완성시킬수 있는 시간을 찾는문제 방문 체크시 숫자와 클립보드의 숫자를 동시에 체크해주는것이 포인트인것 같다./

BFS문제 끝 .

만나는 지점마다 만들수있는 섬을 0으로 해주면서 카운트 해주었다.

플로이드 와샬로 시간이 오래걸리긴 했지만 풀었다.

Review

1.문제 2.코드 3.Review

그냥 문장 전체가 회문인지 체크해주면 쉽다....

처음에 고민을 했는데 A문자 하나를 앞으로만 옮긴다는것을 생각하여 B문장의 뒤에서부터 옮겨야 할것을 찾아주었다. 설명이 어렵다... 를 예시로 들면 B문장의 AB까지 똑같고 C를 찾고 그 이전 문장인 A를 찾아야 하는데 없으므로 ABC를 제외한 나머지 2개만 옮겨주면

현재 연결되어있는 노드중에서 가장 빨리 해킹할수 있는것부터 해킹하면 풀린다. 이 문제는 주의해야하는게 감염시키는 순간에도 시간은 지나가기에 현재 컴퓨터가 해킹되면 그 지나간 시간도 계산해주어야지 된다...