알고리즘

프로그래머스 입국심사

https://programmers.co.kr/learn/courses/30/lessons/17676 처음 문자열 파싱하는데 적응이 안되어 있어서 시간이 좀 걸렸다. 문자열을 파싱한 후, 시작시간과 마침시간을 함께 저장하였다. 문제 핵심 로직 ms단위로 시간을 바꾼

https://programmers.co.kr/learn/courses/30/lessons/17678 특정 알고리즘을 사용하는 문항은 아니고 구현력을 보는 문제였다. 시간을 분으로 바꾸어 연산을 편리하게 하였다. 문제 핵심 가장 늦게 버스를 탈 수 있는 경우는 막차

https://programmers.co.kr/learn/courses/30/lessons/49189 전형적인 bfs 문제이다. 그래프 2차원 배열을 만들고 방문배열, 거리배열을 만들었다.

https://programmers.co.kr/learn/courses/30/lessons/42895 가능한 조합의 모든 경우의 수에 대해서 생각해봐야 하는데, 동적계획법을 통해 가능한 조합을 incremental approach로 접근할 수 있었다. 사용한 N의

https://programmers.co.kr/learn/courses/30/lessons/42627해결방안을 모르겠어서 정답을 찾아봤었다.요청부터 일이 끝난 시간까지의 합들을 구하는 문제이기 때문에, 어떤 일이 끝난뒤, 바로 일처리가 가능한 것들중 빨리 끝나

https://programmers.co.kr/learn/courses/30/lessons/43162백준에 있는 dfs/bfs문제들중 영역 개수를 구하는 문제들이 있는데 그와 유사한 방식으로 해결하였다.그래프를 dfs방식으로 탐색하면서 방문자 배열을 변경하였고

https://programmers.co.kr/learn/courses/30/lessons/43105전형적인 dp문제이다.처음 문제에서 제시한 그림을 봤을때는 이 문제가 떠올랐다.https://programmers.co.kr/learn/courses/

https://programmers.co.kr/learn/courses/30/lessons/49191처음에 문제 이해에 어려움이 있었다.문제의 핵심은 승패를 그래프상으로 나타내였을때 다른 노드를 타고 연결이 가능하여 모든 노드를 순회할 수 있는지 알아보는 것이

https://programmers.co.kr/learn/courses/30/lessons/42898dp문제를 처음 풀때는 어떻게 이걸 동적계획법으로 생각하고 풀 생각을 했을까? 라는 의문이 제일 먼저 들었다. 근데 dp문제를 계속해서 풀고 조금 적응이되니 d

최대힙과 최소힙을 만들고 두 힙을 동기화시켰다.이렇게 하는 이유는 최댓값이나 최솟값을 pop할때 힙을 통해 pop을 하게되면 빠르게 처리할 수 있기 때문이다.두개의 힙을 만들었지만, 파이썬 heapq 공식문서를 참고해보니 아래와 같은 기능이 있었다.출처 : https&

https://programmers.co.kr/learn/courses/30/lessons/64064처음에 정규표현식을 써야하나 고민을 하다가 시간을 날렸다.조합을 구해야 한다는 생각은 했지만 조합을 잘 사용하지 못했다.permutations를 이용해 조합을

https://programmers.co.kr/learn/courses/30/lessons/43163탐색에 관한 문제이다.탐색을 하기 때문에, bfs/dfs로 풀 수 있는데 bfs로 해결해봤다.그런데 한가지 조건을 넣어서, 하나의 문자열만 다른 문자만 appe

https://programmers.co.kr/learn/courses/30/lessons/67258개인적으로 좀 어려웠다. 구현능력이 많이 부족한 것 같다. 나중에 다시 한번 풀어봐야겠다.처음에 내가 문제에 접근할 때 슬라이딩 윈도우로 오른쪽으로 밀면서 최소

bfs를 이용해 최단경로를 구하는데, 비용이 작은 방법이 있다면 수정하는 문제https://programmers.co.kr/learn/courses/30/lessons/67259같은 방향이라면 cost+100을 넣고,다른 방향이라면 cost+600을 넣는다.b

https://programmers.co.kr/learn/courses/30/lessons/42579딕셔너리를 이용해 키-값의 관계를 이용할수 있는가를 물어보는 문제.문제에서 원하는 답을 문제의 흐름대로 썼다.장르별 재생횟수를 딕셔너리를 만들고 재생횟수 순서로

https://programmers.co.kr/learn/courses/30/lessons/42892트리 순회에 관한 문제였다.문제의 핵심은 트리를 구현하고 재귀를 통해 순회할 수 있는지 알아보는 문제였다.트리를 구현하는데 있어서 접근방법이 떠오르지 않았다.

https://programmers.co.kr/learn/courses/30/lessons/64062처음에는 sliding window방식인가?하고 범위를 늘려나갈 것을 생각했지만, stones배열을 보니 시간초과가 나올 확률이 매우 커보였다.stones배열을

https://programmers.co.kr/learn/courses/30/lessons/42861처음 보고서 학교 알고리즘과목 시간에 배웠던 크루스칼 알고리즘이 떠올랐다.크루스칼 알고리즘은 union-find알고리즘을 통해서 구현할 수 있다.크루스칼 알고리

https://programmers.co.kr/learn/courses/30/lessons/76503그래프 dfs 재귀를 깊게 이해하고 있는가를 물어보는 문제였다.문제에서 나온 그래프가 트리구조라는 정보를 이용해,트리구조에서 어떤 노드이던지 루트노드가 될 수

https://programmers.co.kr/learn/courses/30/lessons/42884문제를 보고 이전에 프로그래머스에서 풀었던 문제가 하나 생각났었다.https://velog.io/@wook2pp/%ED%94%84%EB%A1%9C%EA

https://programmers.co.kr/learn/courses/30/lessons/72414 카카오 2021년인데 시간 문자열 파싱은 어느정도 적응했는데, 로직짜는데 어려웠다. 너무 어렵게 생각한 것 같다. 일단 패착의 요인은 최대 가능시간이 100시간인데,

https://programmers.co.kr/learn/courses/30/lessons/12979단순 구현문제였다.N이 2억 이하의 자연수이기 때문에 N값에 대해서 배열을 생성하는것은 불가능하다.기지국들사이 통신이 안되는 곳에 최대2\*w+1만큼 길이의 기

https://programmers.co.kr/learn/courses/30/lessons/12904문자열을 뒤집어서 같으면 팰린드롬 문자열이다.파이썬에선 reversed를 이용해 문자열을 뒤집을 수 있다.최대 문자열의 길이부터 1까지 슬라이딩 윈도우를 해보며

https://programmers.co.kr/learn/courses/30/lessons/77886스택을 사용할 수 있는가를 물어보는 문제이다.110이 스택에 쌓이게되면 꺼내서 개수를 센다.그리고 스택의 어느 위치에 넣어야할지를 고민하면 된다.0이나오는 바로

https://programmers.co.kr/learn/courses/30/lessons/12971이전의 계산결과를 이용하는 dp를 사용하는 문제이다.N이 10만이라는 점에서 완전탐색이나 dfs등의 방법을 사용한다면 시간초과의 가능성이 매우 커보였다.그렇기

https://programmers.co.kr/learn/courses/30/lessons/12914level3치곤 쉬운 문제이다.재귀를 통하여 구하려했는데 역시 시간초과가 나와서 dp를 추가하였다.

https://programmers.co.kr/learn/courses/30/lessons/12927문제에서 주어진 배열에서 가장 큰 원소를 찾고 1씩 감소시키는 것이 문제의 요구사항이었다.1씩 감소시킬때 마다 가장 큰 원소가 바뀔 수 있기 때문에 계속해서 찾

https://programmers.co.kr/learn/courses/30/lessons/68646개인적으로 문제의 규칙을 찾기가 어려웠다.문제 해결방안은 먼저 최후에 까지 남을 수 있는 조건은 어떤것인가를 생각해보는 것 이었다.예를들어 3 5 4라면 5는

https://programmers.co.kr/learn/courses/30/lessons/12936조합에서의 순서를 찾는 문제였다.문제를 구조화시켜보면 마치 캐시메모리에서 직접사상을 연결하는 방식과 매우 유사해 보였다.시간 초과가 난 코드당연히 시간초과가 나

https://programmers.co.kr/learn/courses/30/lessons/43164dfs문제이다.이 문제의 특징은 모든 지점을 한번씩 다 거쳐야 한다는 것이다.그렇기 때문에 일반적인 dfs방식에서 모든 지점을 거치지 않았다면 해당 경로는 고려

https://www.acmicpc.net/problem/16637dfs로 해결하는 전략을 택했다.문제를 일반화시켜보면, a op b op c 와 같은 형태로 생각할 수 있다.이러한 상황에서 괄호는 앞에 걸거나, 뒤에걸거나 둘중 하나이다.이 정보를 토대로 재귀

예상 대진표 https://programmers.co.kr/learn/courses/30/lessons/12985

https://www.acmicpc.net/problem/17135시뮬레이션 + bfs로 해결하였다.

https://www.acmicpc.net/problem/17471삼성A형 기출문제이다.bfs에 관한 문제.최대 10개까지 구역이 있으니 완전탐색으로 두개의 그룹을 나누어 계산하는 것이라 생각했다.절반이상을 넘어가면 그룹이 차이가 없기 때문에 그룹을 나누는 과

https://www.acmicpc.net/problem/17406특정 알고리즘을 사용하는 것이 아닌 단순 구현에 관한 문제였다.배열을 돌릴때 배열을 이동시키는 과정에서 값들의 저장이 필요함을 알았고,각 코너부분을 미리 저장해놓고, 우선 돌린뒤 코너부분이 들어

https://www.acmicpc.net/problem/14501dp에 관한 문제이다.dp는 항상 설계를 어떻게 잘 하느냐가 중요한 것 같다.특정 날짜에 일을 하는게 맞는지를 판단하기 위해 dp를 사용하였다.x일날 y기간동안 일을 한다면,x일날 일의양 + y

https://www.acmicpc.net/problem/14889조합을 구하는 문제.조합을 구하고 단순히 그래프 순회를 통해 합을 구해주는 문제였다.

구현 + 재귀에 관한 내용이 있는 문제어떤 바퀴를 돌릴때 왼쪽, 오른쪽을 확인해야 하는데,바퀴를 돌려놓고 나서 왼쪽 오른쪽을 돌리려면 이미 틀어진 바퀴로 확인을 해야하기 때문에 정확하지 않다.그러므로 재귀를 통해 제일 왼쪽과 오른쪽을 찾고 바퀴를 돌려나가는 방식으로 진

https://www.acmicpc.net/problem/15683구현과 시뮬레이션 문제이다.문제에 특별히 알고리즘 지식이 필요하다기 보단 시뮬레이션 테크닉을 갖추는 것이 중요하다고 생각했다.일단 예를들어 1번에 대해서 4가지 방향이 존재하는데 각각 방향 모두

dfs, 백트래킹을 이용하는 브루트포스 문제였다.사다리지점을 어떻게 탐색하느냐는 문제와 주어진 그래프에서 사다리조작이 이루어 졌는지 확인하는 문제이다.사다리 지점을 재귀로 탐색해야 하는데 지점을 탐색하는 과정에서 처음 0,0부터 탐색하다보니 재귀의 과정에서 필요없는 탐

구현과 시뮬레이션에 관한 문제.방향에 대한 규칙을 찾는게 우선인데, 방향 배열을 저장해놓고 뒤에서부터 탐색해 나가며 (방향+1)%4가 찾고자하는 방향인것을 알 수 있다.

구현문제이다.문제 설명이 길어서 문제 이해하는데 시간이 좀 걸렸다.크게 봄/여름/가을/겨울로 나뉠 수 있는데 문제에서 하라는대로 잘 따라하면 된다.한 구역에 여러개의 식물이 자랄 수 있으니 deque을 이용하여 구성하면 편하게 연산할 수 있다.

https://www.acmicpc.net/problem/17144bfs + 구현에 관한 문제이다.update해주어야 하는 곳을 배열에 저장하고 한번에 update시켰다.회전은 일일이 하나하나 다 구현했지만 시간이 많이 걸리는 느낌이 있었다.

https://www.acmicpc.net/problem/17140일반적인 구현에 관한 문제이다. 문제에서의 관건은 열을 정리할때 어떻게 깔끔하게 하냐가 관건이다.파이썬에서 2차원 배열을 Tranpose시키는 방법을 활용하여 열을 정리하는 경우에 Tranpos

https://www.acmicpc.net/problem/17142bfs문제이다. 시간을 어떻게 저장할지만 잘 고민하면 된다. 바이러스가 있는 칸 말고 빈칸을 만난 경우에 리턴값을 update를 해주면 시간을 구할 수 있다.

https://www.acmicpc.net/problem/17779전형적인 구현하는 문제이다.특별한 로직이 없이 문제에서 요구하는 사항을 빠르게 구현하는 것이 핵심이다.구역을 나눈 배열을 생성하고, 인구배열과 비교하며 구역별 인구수의 합을 구했다.경계선은 문제

문제에서 시키는 사항을 잘 수행하면 되는 시뮬레이션 문제이다.크게 두가지 함수를 만들었는데,최단거리의 손님을 찾아주는 함수손님을 목적지까지 이동하는 함수이렇게 두가지로 나누었다.손님의 위치를 2번부터 m+2번까지 지정해주어 확인하였다.

https://www.acmicpc.net/problem/20055처음에 로봇이 n+1~2n까지 이동이 가능한줄 알고 문제 이해에 애를 먹었다.로봇은 1~n 까지만 이동이 가능하며 내린 이후에는 컨베이어만 돌아가는 방식이다.

https://www.acmicpc.net/problem/20056구현하는 문제였다.처음에 문제의 조건인 행이 연결되어 있는것과, 열이 연결되어 있는것을 캐치하지 못해서 시간이 좀 걸렸다.문제는 크게 파이어볼을 이동시키는것, 두개 이상 있는것을 처리하는것으로

https://www.acmicpc.net/problem/1062오랜만에 포스팅...문제를 보면 처음에는 기본으로 배워야 하는 단어 a,n,t,i,c를 뺀 나머지 알파벳 중에서 k-5개의 조합을 구해서 일일이 다 문자열마다 비교해봤다.파이썬 set를 이용해서

bfs를 응용하는 문제이다.bfs를 통해 최단거리의 목표지점을 찾는데, 기존의 문제들은 target을 목표지점가지 한 칸 씩 이동하여서 목표물을 찾았다.그러나 한칸씩 이동하는 것이 아니라 몇칸씩 이동할지 제안을 주면서 bfs를 사용하면 이 문제를 해결할 수 있다.mov

구현을 하는 시뮬레이션 문제이다.시뮬레이션 문제는 문제의 요구사항을 깔끔하게 정리하고 함수로 만들어야 구현이 깔끔해지고 후에 어디서 틀렸는지 쉽게 알 수 있는 것 같다.문제에서는 말의 번호대로 계속 움직이는 함수를 실행시키고, 말을 움직였다면 해당 칸에 말이 얼마나 쌓

처음 문제 설명은 어려워보이게 생겼는데 읽어보면 배열에서 주변 숫자가 같은 것 끼리 지우면 된다.크게 두가지를 실행하면 되는데,배열 돌리는 함수와 지우는 함수가 필요하다.파이썬에서 배열을 쉽게 돌리는 방법은 deque라이브러리의 rotate함수를 사용해 배열을 돌릴 수

이 문제를 3가지 방식으로 풀었는데, 각각의 방법 모두 좋은 것 같아 3가지 방법으로 풀어보았다.문제에 접근할때 생각은 n개를 쏘는데, 10부터 0점중에 n개를 어떻게 나열할까라고 생각했다. 그렇기 때문에 0부터 10까지 숫자중에 중복하여 n개의 숫자를 뽑고 모든 경우

처음 이 문제를 봤을때, 그냥 단순히 백트래킹만 하면 되는거 아닌가? 하고 백트래킹으로 문제를 풀었고, 탐색에 중복이 있다고 생각했지만 일단 풀고 안되면 다른 풀이를 봐야겠다고 생각했는데 우연히(?) 맞은 문제이다.후에 문제풀이를 봤는데, 단순 백트래킹으로는 시간초과가

이 문제를 읽고서는 처음에는 구현은 너무 쉬운데? 라고 생각했다.하지만 효율성 테스트가 있는 것을 보고 특정 알고리즘을 사용해 연산을 줄여야 되는구나라고 생각했다.결론적으로 누적합을 사용한 dp를 사용하면 되는데, 나는 dp를 사용한 풀이를 떠올리지 못했다. 바킹독님의

dfs와 백트래킹을 사용해 해결하는 문제이다.연결이 불가능한 코어는 코어 리스트에서 아예 제외를 하고 연결이 가능한 코어중에서 하나씩 연결해보고 백트래킹 하면서 찾아가면 된다.처음에 잘못 풀었던 부분은, 무작정 최소길이를 찾으려 해서 오답이 났다.문제 조건에서 가능한

https://programmers.co.kr/learn/courses/30/lessons/72412문제 설명이 길지만 잘 읽어보면 문제 이해에는 크게 어렵지 않다.처음 문제를 풀때 딕셔너리로 해당 조합들을 만들었지만, "-"의 존재때문에 다시 생각하게 만들었

https://programmers.co.kr/learn/courses/30/lessons/72413최단거리를 찾는 문제이다.최단거리가 나오면 항상 다익스트라, 플로이드 워셜 알고리즘을 생각해야 한다고 배웠었다.처음에는 플로이드 워셜 알고리즘을 사용해 문제를

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

문제를 처음 읽고 예전에 풀어봤던 느낌이 났었다. 그래서 문제를 풀고 백준을 찾아봤는데, 이 문제의 해결법과 같지는 않지만 가장 긴 증가하는 수열 시리즈 문제를 풀었을때와 구조가 비슷하다고 생각했다.문제를 접근하는 방법은 다음과 같다. 핵심은 싸게 사서 비싸게 파는 것

https://programmers.co.kr/learn/courses/30/lessons/81303문제를 해결하지 못해 바킹독님의 풀이를 보았다.이 문제의 해결법은 연결리스트였다. 연결리스트는 가장 기초적인 자료구조인데, 이를 이용한 문제를 푸는것은 이번이

https://www.acmicpc.net/problem/15591문제에서 그래프가 주어지는데, q개의 질문사항을 잘 해결하는 문제이다.문제에서 요구하는 것을 간단히 말하면, 어떤 정점에서 다른 정점까지 비용중에 요구한 값보다 큰 간선을 찾는 것이다.그런데 현

https://www.acmicpc.net/problem/10021이 문제는 정점들과 정점들 사이의 비용을 주어준 문제이다.요구사항은 이 간선들중에서 최소비용으로 사이클 없는 그래프를 만드는 것인데, 크루스칼 알고리즘을 사용하여 이 문제를 해결할 수 있다.크루

처음 문제 이해에 애를 먹었지만, 요구사항은 간단했다. 어떤 소들 끼리 길을 안건너고 만날수 있는지 찾으면 되었다.소들의 위치를 저장해 각 소마다 bfs를 하였다. 소는 최대 10000마리 이므로 10000번 bfs를 돌려주면 되기 때문에, 시간은 넉넉할 것이라 생각했

위상정렬을 이용한 문제이다.어떤 정점에 연결된 in-degree를 이용해 각 정점의 차수를 줄여나가는 방식으로 문제를 해결할 수 있다.문제를 해결한 방식은,입력값으로 들어오는 연결을 그래프로 만들어 주고, in-degree값을 증가시켜 차수의 배열을 만들어 주었다.이제

특정 범위의 수가 제곱수로 나누어 지는지 확인하는 문제이다.이 문제의 특징은 left의 범위가 1조라는 것이다.하지만 right는 1조+1백만까지이므로 1백만 사이의 숫자들 중에서 어떤것을 고를지를 고민하면 된다.물론 1조크기의 배열을 만드는것은 말이 안되고, 에라토네

https://www.acmicpc.net/problem/1052같은 크기의 물병을 합쳐서 크기가 2배인 물병을 만든다는 것을 잘 이해하는것이 중요한 문제였다.위의 내용을 비트로 생각해보면 비트마스킹을 통해 문제를 해결할 수 있겠다라는 생각이 든다.어떤 수 n

값을 증가시켜가면서 값이 바뀌는 특정 지점을 찾아야 하는 문제였다.값을 증가시키다 어느 순간 문제 조건에 해당되는 부분이 바뀌는 지점이 생기는데, 이를 이분탐색을 이용해 해결할 수 있었다.그 어떤 지점이 바뀌기 시작하는 지점을 찾아야 하는데,1부터 최대 10억까지 답이

https://www.acmicpc.net/problem/1080이 문제는 행렬을 최소한으로 뒤집어 원하는 행렬의 모양을 만드는 문제이다.3x3만큼의 크기의 윈도우를 움직인다고 생각해보자.(0,0)에 있는 배열의 값은 오로지 0,0 ~ 2,2에 의해서만 바뀐다

https://www.acmicpc.net/problem/1022구현을 잘 할수 있는가를 묻는 문제였다.처음에는 음수인 인덱스가 보기 싫어서 제일 왼쪽으로 밀고 패딩을 주는 방식을 생각했었다.이 접근의 문제점은 일단 소용돌이의 모든 배열을 저장하려 했다는 생각

https://www.acmicpc.net/problem/1027어느 시점에 건물이 가려지는지를 파악하는 문제였다.건물을 연결하다 보면 기울기를 쓰면 되겠다라고 판단되는데, k번째 건물의 왼쪽과 오른쪽을 볼때 왼쪽으로는 기울기가 점점 작아져야 하고, 오른쪽으로

백트래킹을 이용하는 문제이다.백트래킹만 잘 구현한다면 문제를 쉽게 해결할 수 있다.가능한 경우의 수가 엄청 크지않아 조합을 이용해 감소하는 수 배열을 만든 뒤, 정렬을 해도 된다.하지만 경우의 수가 엄청 큰 문제에서는 위의 해결방법이 먹히진 않을 것 같고, 백트래킹을

https://www.acmicpc.net/problem/1043그래프를 이용하여 해결할 수 있는 문제이다.나는 파티 배열을 받아서 그래프를 구성하고, 진실을 아는 사람들을 정점으로 그래프를 순회해 가면서 방문한 정점도 진실을 아는 사람으로 변경하였다.저장해놓

https://www.acmicpc.net/problem/1068트리 + dfs를 이용하는 문제이다.n이 최대 50까지라 시간제한에 크게 걸리지 않는다.최근에 그래프를 배열로 만들어서 푸는 문제가 생각나서 dfs가 아니라 parent배열과 child배열을 만들

https://www.acmicpc.net/problem/2933구현 + bfs문제였다.이 문제의 핵심은 어떤 미네랄을 파괴하였을때, 클러스터가 분리되는 지점이 발생하는데 이 클러스터를 내리는 것을 구현하는 것이 핵심이다.깬 지점을 중심으로 주변 4칸에 있을

최단거리를 찾는 bfs문제이다.근데 bfs에 다른 알고리즘을 접목시켜야 연산시간을 줄일 수 있다.더러운 칸의 위치가 10개뿐이라는 점이 눈여겨볼 지점인데,10개 칸을 완전탐색으로 돈다면 10!로 나열할 수 있고, 이 경우를 bfs로 돌린다면 cpp에선 통과가 가능할 지

https://www.acmicpc.net/problem/1327k칸만큼 뒤집어 bfs를 통하여 원하는 정답의 최단거리를 찾는 문제이다.방문배열을 어떻게 만들것인가가 문제인데, 만약 배열로 생성한다면 8^8만큼 크기의 배열을 생성해야 한다.그렇기 때문에 공간

https://www.acmicpc.net/problem/2098알고리즘에서 유명한 문제인 TSP 문제이다.TSP 문제의 가장 쉬운 해결방법은 완전탐색이고, 완전탐색은 대부분 dp로 해결이 가능하다(특별한 케이스를 제외하고)TSP문제는 어떤 지점에서 다른 지점

https://www.acmicpc.net/problem/7579배낭문제와 비슷한 문제이다.배낭문제에선 현재 선택한 물건을 넣는다와 안넣는다로 선택할 수 있는데,현재 선택한 물건을 넣는 경우에 비교해야 할 부분은 "가방의 무게에서 현재무게를 뺐을때의 가치의 최

https://www.acmicpc.net/problem/10942이 문제를 완전탐색으로 계산한다면 배열의 절반만큼 M개의 질문을 연산하면 대략 10억의 연산이 나오기 때문에 시간초과가 자명하다.그렇다면 중복을 줄일 수 있는 방법을 찾아야 하는데, 가장 먼저

https://www.acmicpc.net/problem/1039처음 이 문제를 보고 몇일전에 풀었던 https://www.acmicpc.net/problem/1083이 문제가 떠올랐다. 이 문제에서는 최대 k번 스왑이 가능했기 때문에 k번 안에 가장

https://www.acmicpc.net/problem/2931구현 문제이다.bfs를 통해 가스의 흐름을 찾아갈 수 있는데, 이때 블록을 어떻게 처리해야 할지가 문제이다. 블록마다 특정방향으로 흐를 수 있는데, 이 경우들을 고려해 블록마다 갈 수 있는 방향을

https://www.acmicpc.net/problem/11404모든 각 정점에서 각 정점가지의 최단거리를 찾는데는 플로이드-워셜 알고리즘을 사용한다.플로이드-워셜 알고리즘은 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하는데, 특정 노드 k를 거쳐서 방

https://www.acmicpc.net/problem/2151문제를 읽고 처음에는 잘 이해가 안됬지만, 결국에 결론은 다음과 같다.거울은 양면이므로, 북에서 들어온 빛은 동쪽 혹은 서쪽으로 꺾인다 동쪽에서 온 빛은 남쪽 혹은 북쪽으로 꺾인다.결국 한쪽 문에

https://www.acmicpc.net/problem/16946만약 시간초과를 생각하지 않고 그냥 풀면 1인 지점마다 0으로 바꾼 뒤, bfs를 모두 돌려주면 된다.이렇게 한다면 만약 최악의 경우에 1000\*1000에 모두 1인지점을 놓고 1000000번

https://www.acmicpc.net/problem/2186dfs를 통해 문자열의 크기와 같다면 return해주는 문제이다.당연히 단순 dfs만 해주면 시간초과가 발생한다dfs만 사용한 코드그렇기 때문에 중복을 제거해 주어야 되는데, 잘 생각해보면만약 내

https://www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지

https://www.acmicpc.net/problem/2213트리에서 dp를 이용하는 문제이다.트리는 어떤 정점을 잡고 나머지를 아래로 늘어트리면 어느 노드던지 루트가 될 수 있다. 나는 1을 루트노드로 잡고 문제를 해결했다.이 문제는 전형적인 dp가 문제

https://www.acmicpc.net/problem/17825구현문제.가능한 경우의 수는 10번의 움직임들을 각각의 말에 배치하는 경우인데,이는 4^10 = 1048576로 모든 경우의 수를 탐색해도 시간초과가 걸리지 않겠다고 생각했다.주사위 판을 어떻게

https://www.acmicpc.net/problem/20061문제를 잘 읽고 구현하는 문제이다.근데 구현이 복잡해 빠르게 구현을 처리하는게 관건이다.사람들마다 각기 구현방법이 다 다른데 내가 구현한 방법을 써보겠다.일단 블록을 놓으면 초록과 파랑이 각기

https://www.acmicpc.net/problem/19237특별한 알고리즘 없이 구현하는 문제이다.여러가지 구현문제들을 이리저리 치여보면서 느낀점은, 초기단계에서 어떻게 구현할 것인가 머리속으로 그려놓아야 한다는 것이다.이런 구현 문제들은 초기단계에 데

https://www.acmicpc.net/problem/20057문제조건을 그대로 구현하는 구현문제..구현해야 할 로직은 크게 두개이다.토네이도를 구현모래 흩뿌리기 구현토네이도를 구현하기 위해서는 정 중앙부터 시작해서 1부터 n까지 증가하는 i값과, i칸 만

https://www.acmicpc.net/problem/1826내가 처음 문제를 접근한 방법은 일단 좌표위에 주유소들을 그려놓고 차를 이동하는 것을 시뮬레이션 하였다.시뮬레이션을 하다보면 주유소를 방문하는데, 이때 2가지로 나눌 수 있다.해당 주유소를 방문을

https://www.acmicpc.net/problem/17136문제를 읽고 가장 먼저 들어온점은 일단 10x10배열이라 배열이 크지 않다는 점.색종이 수를 가장 적게 써야하는데, 예제 5번을 보면 직관적으로는 여기다가 어떤것을 붙이고 저기다가는 어떤것을 붙

https://www.acmicpc.net/problem/1347특별한것 없는 구현문제.방향만 잘 나타내주면 되는데, 위 오른쪽 아래 왼쪽을 각각 0 1 2 3으로 설정했다.후에 키를 iter하면서 L이라면 -1 R이라면 +1을 해주었다.만약 값이 0이라면 -

https://www.acmicpc.net/problem/1520문제 이해는 어렵지 않다.dfs를 통해 시뮬레이션을 해보면서 경우의 수를 찾으면 된다.근데 역시나 dfs만 쓰면 n과m이 500인 상황에서 시간초과가 날수밖에 없다.이러한 상황에서 중복된 작업이

https://www.acmicpc.net/problem/1726이전에 bfs + 상태별 방문배열 유형을 여러개 풀어봐서 이 문제도 익숙했다.최단거리를 구하는데, 방향에 따라 상태를 다르게 저장해야 하는것을 보고 bfs+방향별 방문배열로 해결하기로 했다.문제에

https://www.acmicpc.net/problem/1938문제가 좀 길지만 읽다보면 문제 상황은 어느정도 심플하다.BBB를 EEE로 맞추면 된다.일단 통나무가 있을 수 있는 상태는 | 모양이거나 ㅡ 모양이다.즉 가운데 위치와 어느 방향으로 서있는지만 알

https://www.acmicpc.net/problem/1941가장 먼저 배열이 5x5란점이 눈에 띄었다.5x5 배열에서 브루트포스를 할 수도 있겠다라는 마음가짐으로 문제를 읽었다.결국 25개중에 7개를 골라야 하는데 25C7은 480700로 해당 가지수를

https://www.acmicpc.net/problem/1194문제 이해는 되게 간단하다. 0에서 1로 가는데 그사이 열쇠를 먹어서 문을 열면 된다.문제를 보면 키1개로 1개의 문만 여는것이 아니라 해당되는 문은 다 열 수 있다.이 점과 키가 6개밖에 없다는

https://www.acmicpc.net/problem/2146가장 짧게 이을 수 있는 대륙을 찾는 문제이다.가장 쉽게 접근할 수 있는 로직은대륙별로 번호를 주기각 대륙마다 bfs를 통해 다른 대륙까지 가는데 얼마나 걸리는지 체크제일 가깝게 이을 수 있는 것

https://www.acmicpc.net/problem/2206백준 문제집에서 SW역량테스트 준비 문제집을 풀고 있는데, 처음에는 어려웠지만 점점 익숙한 유형이 나오는 것 같다.백준 1194번 문제를 풀었다면 같은 논리의 문제이다.최단거리를 구하는 bfs 문

https://www.acmicpc.net/problem/2234bfs문제이다.문제에서 구하라는 3가지를 구하면 된다.이 문제는 친히 비트를 쓰라고 알려주고 있다.이전에 해왔던 bfs로 영역표시 알고리즘을 쓰는데, 이동하려는 칸에 막대가 있다면 이동을 안하면

https://www.acmicpc.net/problem/3048앞으로 파이썬 말고 자바로 알고리즘 풀이를 해볼 생각이다.파이썬 쓰다가 자바 쓰려하니 좀 답답한 느낌이 있지만 앞으로 스프링 공부하면서 자바를 계속 쓸것이라 판단해 자바를 쓰기로 했다.

https://www.acmicpc.net/problem/16639처음에는 완전탐색으로 dfs를 돌렸지만 경우의 수가 많아져 결국 실패했다.다른 사람의 풀이를 참고했는데,괄호를 여러개 쓸 수 있다는 점은 연산자의 우선순위에 상관없이 계산을 할 수 있다는 점이다

https://www.acmicpc.net/problem/1800해결하지 못해 다른사람들의 풀이를 참조했다.이 문제는 다익스트라 + 이분탐색 문제이다.다익스트라와 이분탐색에 대해 이해해야 위 문제를 풀 수 있었다.어떤 조건을 만족하는 최대, 최소값 문제에서는

https://www.acmicpc.net/problem/16918시뮬레이션 문제이다.폭탄이 같이 터진다는 점에서 배열을 0,0부터 r,c까지 순차적으로 탐색했을때, 폭탄이 터진 경우 옆에 있는 폭탄도 터트리면 안된다.그렇기 때문에 폭탄이 터지지 않는 위치에서

https://www.acmicpc.net/problem/17182각 지점마다의 최단거리를 구하고 백트래킹을 해주면 되는 문제이다.최단거리를 구할땐 플로이드 워셜 알고리즘을 이용했다.백트래킹시 상태관리를 해주어야 하는데,노드가 몇개 없는 점에서 이전에 풀었던

https://www.acmicpc.net/problem/44850,0 -> n-1,n-1 로 이동하는 최단거리 문제최단거리 문제에서는 다익스트라를 쓸 수 있을까를 고민해봐야 한다.이 문제를 dfs로 완전탐색 하기에는 넘 오래걸린다.2차원 배열로 되어있지만,

https://www.acmicpc.net/problem/1253투포인터 슬라이딩 윈도우 문제이다.완전탐색으로 문제를 해결하면,N의 범위가 2000이고 값 2개에 대해 각각 2000번 루프를 돌리고 N번을 반복해야 하니O(n^3)의 시간복잡도로 시간초과가 난다

https://www.acmicpc.net/problem/1806문제 제목 그대로 부분합을 구할 수 있는지를 물어보는 문제이다.투포인터를 통해 O(N)의 시간복잡도로 통과할 수 있다.시작점에 두개의 포인터를 설정하고 구간합이 작으면 오른쪽 포인터를 밀고,구간합

https://www.acmicpc.net/problem/12919브루트 포스적으로 해결하는 문제.연산에는 2종류가 있는데 각각의 경우의 수 마다 2개의 연산을 실행하면 연산량이 너무 많아져 할 수 없다.호출을 줄이기 위해 뒤집은 문자열이나 원래 문자열의 su

https://www.acmicpc.net/problem/14658n,m의 범위가 너무 크기 때문에 배열은 만들 수 없고,n,m크기만큼 트램펄린을 한칸씩 밀면 너무 많은 계산량이 생긴다.처음 아이디어는 각 별을 기준으로 1,2,3,4분면을 탐색했는데, 이렇게

https://www.acmicpc.net/problem/1522문제의 핵심은 결국 a를 하나로 뭉쳐놓게 만드는 것이 포인트이다.그렇다면 어떤 부분을 정해서 b를 교환했을때 최소로 a를 일렬로 나열할 수 있을지 생각해보아야 한다.문자열의 길이가 1000밖에 되

https://www.acmicpc.net/problem/20437슬라이딩 윈도우 문제이다.k개를 포함하는 최소한의 연속된 문자열을 찾으려면가장 왼쪽과 오른쪽이 같은 문자여야 한다.그렇기 때문에3번은 k개를 포함하는 왼쪽과 오른쪽이 같은 최소를 찾으면 되고,4