알고리즘과 문제풀이

사실 벨로그에 올리지 않았다 뿐이지, 되게 많은 문제들을 풀었다.앞으로는 뭐 푸는 족족 올리긴 할거니까, 그래도 그동안 풀었던 문제들은 깃허브에 잘 관리되어 있어서, 링크를 올릴까 한다.https://github.com/ingeon2/Baekjoon

알고리즘 문제 풀기(백트래킹), 14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 풀이 핵심은, 재귀함수는 두가지를 알아야 한다. 재귀함수는 언제 끝내야하는가?, 그리고 끝나면서 해줘야 하는 로직은? 끝내러 가는 와중에 어떤 로직(문제에서 원하는)을 작성해야 하는가? 14888번. 최대 숫자 개수는 11개...

문제는 다음과 같다. https://www.acmicpc.net/problem/12101 정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성. 1을 나타내는 식의 사전순 정렬 1 2를 나타내는 식의 사전순 정렬 1+1 2 3을 나타내는 식의 사전순 정렬 1+1+1 1+2 2+1 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/12919 풀이는 다음과 같다. 이해하기 쉽게 주석 달아놓았다. 문자열 뒤 A 추가해서 혹은 문자열 뒤 B 추가해서 뒤집는 과정을 거쳐 S 가 T 가 될 수 있다면 1, 아니면 0을 출력하는 문제이다. **생각해 보면, S에서 T로 가기 위해선, 모든 경우마다 무조건 한글자...

문제 https://www.acmicpc.net/problem/14502 사용한 알고리즘 백트래킹 재귀 (벽 세개 쳐주기) BFS (map 돌면서 0의 개수 세주기)

문제는 https://www.acmicpc.net/problem/8979 풀이는 다음과 같다. 사용 알고리즘은 단순구현이다. 하지만 신경써줘야 할 부분은, 어떤 클래스가 있으면, 해당 클래스를 배열화 하고 나서, 어떻게 내림차순이나 오름차순으로 정렬할 수 있을까? 바로,implements Comparable 을 통해 상속받고, 상속받았으므로 compa...

문제는 https://www.acmicpc.net/problem/20920 다음과 같고, 구현 + 정렬 문제인것같다. 나는 정렬 문제를 풀며 약간 외우다시피 했는데, 우리가 아는 알파벳 사전순 숫자 오름차순을 구현하려면 이러한 내용들은 보통 compareTo에서 this 가 먼저 나온다 즉, 아래와 같이 구현하면 된다는 이야기. 아래는 약간 다른데, ...

문제 링크는 다음과 같다. https://www.acmicpc.net/problem/13164 풀이는 아래와 같다. 이해하면 쉬울 내용 모든 키차이를 구한다. (문제의 조건에서 정렬되어서 제공.) 해당 키차이를 정렬한다. (키차이가 크면, 해당 사이를 찢어줄 예정) K개의 무리를 만들기 위해서는, K-1번 찢어줘야 하므로, 2번에서 정렬해준 키차이에서,...

문제 링크는 다음과 같다 https://www.acmicpc.net/problem/11497 풀이는 다음과 같다 이 문제에서 이해해야 할 내용. 정렬된 친구들 12345678 이 있다고 하자. index 0부터 순서대로 다른 배열의 왼쪽, 오른쪽 이렇게 끝까지 넣게 되면, (12) (1342) (135642) (13578642) 이렇게 만들어진 배열이,...

문제는 다음과 같다. https://www.acmicpc.net/problem/16918 풀이는 다음과 같다. 내가 헷갈렸던 부분은, 내가 활용해야 할 정보는 폭탄의 위치 행렬, 그리고 폭탄이 몇초 지났는지 알아야 한다. 즉, 숫자 세개의 정보를 담고 있어야 하는데, 나는 **String 으로 map을 받아서, 더 어렵게 풀었다. 그렇게 받고, 해쉬맵으...

문제는 다음과 같다 https://www.acmicpc.net/problem/1138 풀이는 다음과 같다. 헷갈렸던 부분은, wihle문은 소괄호 () 안이 true일때 동작한다. 풀이 로직은, 코드를 보면 내 키는 for 문의 i 이고, **코드에서, 숫자 count 는 내 앞에 나보다 키큰 친구가 몇명 있는지를 나타내주는 숫자이다 index 는 지...

문제는 다음과 같다. https://www.acmicpc.net/problem/23843 풀이는 다음과 같다. 주석의 예시는 5 2 1 4 4 8 1 이 입력되었을때이다. 내가 계속 바로 아래에 있는 블럭 부분만 구현하고, 내가 가진 전자기기보다 콘센트가 더 많을때는 고려해주지 않았다. 문제를 다시 가서 보니까, N >= M이다 라는 조건은 어디에도 없...

문제는 다음과 같다. https://www.acmicpc.net/problem/1706 풀이는 다음과 같다. 특별한 내용은 없고, 링크를 타고 들어가서 문제를 자세히 읽었다면 주석을 통해 이해할 수 있을 난이도이다.

문제는 다음과 같다 https://www.acmicpc.net/problem/2688 코드는 다음과 같다 흔한 DP 문제이다. 푸는 로직은 주석을 읽으면 이해될 수 있도록 작성했다. 그것도 보기 난잡스러울 수 있으니, 아래의 블럭을 보자. 첫 시도에 통과하지 못했는데, int와 long의 자료형을 잘못 사용해서 틀렸다. 테스트케이스만 통과하고, 다...

문제는 다음과 같다. https://www.acmicpc.net/problem/1926 코드는 다음과 같다. 원래 BFS를 알고있다면, 이해는 쉽다. 내가 해준건, map을 문제에서 준 조건대로 mapr 값이 1이라면 BFS로 순회하면서 how_many로 몇개를 순회했는지 개수를 세주고, 순회하는 친구들을 visitedr = true로 체크하면서 한번 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/15681 풀이 풀이는 다음과 같다. 트리구조를 잘 알고있다면, 어렵지 않게 풀 수 있는 문제이다. 근데 나는 트리구조의 특성을 잘 모르고있어서 쉽게 풀 수 있지 않은 문제였다. 트리구조를 여러개 만들건데, subTree[i] = i값을 루트노드로 하는 트리구조의 크기 라고...

문제는 다음과 같다. https://www.acmicpc.net/problem/20207 풀이는 다음과 같다. 풀이에 자세하게 내가 문제 풀었던 방식을 주석으로 설명해놓았으니, 주석을 참고하며 코드를 보면 충분히 이해할 수 있을거라고 생각한다. 내가 생각하는 필요한 역량은 구현 정도인것같다.

문제는 다음과 같다. https://www.acmicpc.net/problem/21278 풀이는 다음과 같다. 처음엔, 오우~ 최솟값 구하는거구만? 하고 다익스트라를 사용했는데 시간초과가 뜨더라. 그래서 찾아보니, 다익스트라 말고 플로이드 워셜 알고리즘 사용한다더라. 근데, 플로이드 워셜 알고리즘은 사용해본적이 없어 공부하고 배우고 풀었다. 생각보다 어...

문제는 다음과 같다. https://www.acmicpc.net/problem/11265 풀이는 다음과 같다. 더 설명할 내용은, 플로이드 와샬 알고리즘이다. 쉽게말해, 플로이드 워셜 로직 = a->c로 가는 값보다 b를 거쳐 a->b + b->c 값이 더 작다면 작은 값을 택하는 알고리즘. 바로 위의 로직은 하나의 노드를 거쳐 가지만(a->b->c...

문제는 다음과 같다. https://www.acmicpc.net/problem/16166 풀이는 다음과 같다. 최소 환승 알고리즘이다. 다익스트라에 조금 더 많은것들을 요한다. (https://www.youtube.com/watch?v=XIwiZZr2l5I) 최소 거리가 아니라, 최소 환승 횟수라고 생각하고 다익스트라를 적용해야 한다. 주석을 읽으며...

문제는 다음과 같다. https://www.acmicpc.net/problem/5214 풀이는 다음과 같다. 이전의 이 문제와 비슷하다. 역과 호선(하이퍼루프) 가 있고, 최소거리를 구해야 한다. https://velog.io/@dlsrjsdl6505/%EB%B0%B1%EC%A4%80-16166-%EC%84%9C%EC%9A%B8%EC%9D%98-%EC...

문제는 다음과 같다. https://www.acmicpc.net/problem/2021 풀이는 다음과 같다. (맞은 풀이) **처음 풀이는 아래와 같이 풀었고, 해당 코드가 틀린 부분은 없지만, 메모리 이슈로 인해 메모리 초과가 되었다. 그럼 메모리를 줄일 수 있는 부분이 어디있을까.. 싶다가 visited 방문배열을 2차원에서 1차원으로, 즉 visi...

문제는 다음과 같다. https://www.acmicpc.net/problem/14500 풀이는 다음과 같다. DFS와 백트래킹을 잘 이해하고 있다면, 어렵지 않다. 백트래킹을 잘 모르겠다면, https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 이 문제들을 풀어보도록 하...

문제는 다음과 같다. https://www.acmicpc.net/problem/2206 풀이는 다음과 같다. 일반 BFS와 달랐다. 우리가 흔히 아는 map이 주어진다. ex) 000 011 000 이런식으로. 0은 통과가능, 1은 벽이다 1행1열부터 주어진 값 R행 C열까지의 최단거리를 구하는데, 벽을 한번 부술 수 있다. 오답 처음엔, 어.. 벽...

문제는 다음과 같다. https://www.acmicpc.net/problem/14719 풀이는 다음과 같다. 풀이 안의 주석에서, 1번부터 5번까지는 위의 그림을 의미하는것이다. 풀이 스택을 이용해서 풀었다. 뭔가 예전부터 **내가 원하는 값을 만나면, 원하는 값 이외의 값을 만날때까지 기존의 값들을 와다다다 제외하면서 원하는 로직대로 처리해주는 내...

문제는 다음과 같다. https://www.acmicpc.net/problem/1202 **문제를 잘 읽고 풀이를 보도록 하자.. 그리고, 주석을 집중해서 읽어보도록 하자** 풀이는 다음과 같다. 많이 어렵다. 진짜 어렵다.. 코드를 봐도 작동되는건 이해가 가는데, 왜 저렇게 작동시킬까? 가 이해가 안될 수도 있다. 아직 이해가 안갔으면, 아래를 한번...

문제는 다음과 같다. **String 이 주어진다. 해당 String을 구성하는 알파벳 전부를 사용해서, 또다른 String을 만들어라. 만들어낸 String이 문자 두개 이상 중복되면 제외해라. 만들어낸 String들을, 사전순 정렬하고 return해라.** 입력 예시 String abbc 출력 예시 {abcb, abcb, babc, bacb, bc...

문제는 다음과 같다. **1은 길을, 0은 수리가 필요한 길이다. 하지만 인력과 돈은 한정되어있기에, n개의 길만 수리할 수 있다. 이때, 1과 0으로 주어진 길과 n을 입력하면, 해당 길을 가장 길게 연결할 수 있는 출력을 구하시오.** 입력 예시 111101011001001110101, 4 출력 예시 12 (맨 처음의 1111010111001) 입...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java 풀이는 다음과 같다. 이거 그냥 그때그떄 알맞은 로직을 사용하는 그리디 알고리즘 문제이다. 처음 풀이는 되게 난잡하게 index1, index2 이런식으로 배달과 수거를 한번 왕복할때 0이 ...

문제는 다음과 같다 https://www.acmicpc.net/problem/14503 풀이는 다음과 같다 어.. 풀이들을 보면 DFS라고 하지만, 나는 약간 구현에 더 가까운것 같다. 문제를 읽으며 순서만 제대로 파악한다면, 충분히 맞출 수 있는 문제이다. 청소가 안되어있다면 청소를 해준다. 주위 네개의 칸에 청소 가능한 칸이 있는지 체크한다 (...

문제는 다음과 같다. https://www.acmicpc.net/problem/2230 풀이는 다음과 같다. 투포인터 투포인터 알고리즘을 알고 있다면, 그렇게 어렵지 않다. s값이 고정되어있을때, e가 arr[e] - arr[s] >= M 을 만들기 위해 달아난다. 달아나서 arr[e] - arr[s] >= M 값을 만족하게 된다면, while문을 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/16236 구현 문제이다. 풀이는 다음과 같다. 상어 클래스 : 상어의 위치와 크기, 먹이를 얼마나 먹었는지를 나타내고, 위치의 먹이를 먹을 수 있는지, 위치로 이동할 수 있는지, 먹어버리는 매서드(크기, 먹은 수 조절 한꺼번에)를 가지고 있다. 노드 클래스 : 위치와, 해...

문제는 다음과 같다. https://www.acmicpc.net/problem/18870 풀이는 다음과 같다. 이분탐색을 모르신다면?https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 이분탐색 로직을 안다는 가정 하에 다른 부분을 설명하자면, 배열이 1000 999 1000 999 1000 999...

문제는 다음과 같다. https://www.acmicpc.net/problem/12865 풀이는 다음과 같다. 이전에 비스무리한 배낭에 넣는 문제를 풀었었는데, https://velog.io/@dlsrjsdl6505/%EB%B0%B1%EC%A4%80-1202-%EB%B3%B4%EC%84%9D%EB%8F%84%EB%91%91-%EC%9E%90%EB%B0%...

문제는 다음과 같다. https://www.acmicpc.net/problem/2579 풀이는 다음과 같다. 흔한 DP 문제이다. DP를 풀기 위해선 세가지를 찾아야 한다. DP 배열 정의 dpi = i번째 계단을 바로 직전에 j+1개의 계단을 뛰어왔을때 점수의 최댓값이다. 예를 들어, dp10 = 10번째 계단을 이전에 2개의 계단을 뛰어넘어왔을때 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/15654 풀이는 다음과 같다. 흔한 백트래킹 문제이다.

문제는 다음과 같다. https://www.acmicpc.net/problem/1806 풀이는 다음과 같다. 흔한 투포인터 문제인데, 가운데의 else if 문 정도만 이해한다면 문제는 쉽다. 가운데의 else if문은, end 포인터가 끝에 도달하고 나서 sum >= S라면, sum < S가 될때까지 start포인터를 줄여나가기 위해 만들어준 로직이...

문제는 다음과 같다. https://www.acmicpc.net/problem/22862 풀이는 다음과 같다. 적당한 투포인터 문제이다. 풀이를 설명하자면, 부분수열에 odd, 홀수의 개수가 K개보다 작다면 수열을 늘릴 수 있으므로 e index의 값에 따라 홀수 개수 늘려주고 e값 증가, 정답 갱신을 해준다. 그다음, else if문은, 홀수가 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/1377 풀이는 다음과 같다. 우선, 버블정렬 알고리즘은 다음과 같다. 당연히 코드로 보면 이해가 안간다. 예시를 들어 설명을 하겠다. 10 1 2 5 3 을 다음 코드에 집어넣을 예정이다. 10 1 2 5 3 for문 i = 0를 돌면 (10 1 2 5 3 -> 1 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/3020 풀이는 다음과 같다. 누적합의 개념을 알고 있다면, 주석을 잘 읽으면 이해가 갈 내용이다. 처음에 위 로직을 통해, 높이 h인 석순(s[])과 종유석(j[])의 수를 구한다. (ex - s[2] = 5 -> 높이 2의 석순이 5개.) 다음은 위 로직을 통해 누적...

문제는 다음과 같다. https://www.acmicpc.net/problem/1987 풀이는 다음과 같다. 백트래킹 + DFS 문제이다. map은 char의 배열이다. 그렇기에 visitedmap[r - 'A'] 는, 어떤 알파벳을 방문했는지를 알려주는 배열이다. 예를 들어, A를 방문했다고 하면, (mapr = 'A' 라고 하면,) vistied...

문제는 다음과 같다. https://www.acmicpc.net/problem/2169 풀이는 다음과 같다. 로봇이 map을 돌아다니며 얻을 수 있는 최대 누적 값을 구하는 문제이다. 처음엔 DFS가 생각나서 아래와 같이 풀었고, 보기좋게 틀렸다. 시간초과였다. 물론 이 풀이로도 답은 나오지만, 완탐인만큼 시간초과가 나온다. 시간 제한은 1초이기 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/7576 풀이는 다음과 같다. 흔한 BFS문제이다. 다른 문제들의 BFS와 다른점이 있다면, 시작점이 여러개가 될 수 있다는 점이다. 그래서 해당 부분은 아래와 같이 구현했다.

문제는 다음과 같다. https://www.acmicpc.net/problem/1759 풀이는 다음과 같다. 백트래킹 문제이다. 주석으로 설명을 달아놓았다. 요즘 코테를 보면, 백트래킹 + 그래프 문제가 자주 나와서, 해당 영역을 연습해야지 싶다. 처음엔, 위의 로직을 아래와 같이 작성하여 26퍼센트에서 틀렸습니다가 나왔다. 해당 로직으로는, ...

문제는 다음과 같다. https://www.acmicpc.net/problem/1339 풀이는 다음과 같다. 이 문제에서 핵심 로직은 다음과 같다. ABC -> 100A + 10B + C BBDES -> 10000B + 1000B +100D + 10E + S EEDD -> 1000E + 100E + 10D + D 즉, 주어진 String들의 위치에 따...

문제는 다음과 같다. https://www.acmicpc.net/problem/1941 풀이는 다음과 같다. 풀이에 대해서 설명을 하면, 5x5의 행렬은 0~24의 index, 총 25개로 표현가능하다. index/5, index%5로 0, 0 .........4, 4 까지 모든 5x5 행렬을 나타낼 수 있다. 풀이 순서는 아래와 같다. 0~24중...

문제는 다음과 같다 https://www.acmicpc.net/problem/9205 풀이는 다음과 같다. 어렵지 않은 BFS문제이다. 주어진 노드들을 nodes에 기록한다. nodes를 순회하며, 서로다른 두개 노드의 거리가 1000 이하라면 그래프 A에 추가해준다. 여기까지가 초깃값이고, BFS로직으로 그래프를 순회하며 축제 노드 (n+1번째 ...

문제는 다음과 같다. https://www.acmicpc.net/problem/1043 풀이는 다음과 같다. 풀이 로직은 다음과 같다. 진실을 알고 있는 친구가 포함된 파티에선 무조건 진실만을 말해야 한다. 또한, 한번 진실을 들은 친구들에게는 계속해서 진실만을 이야기해야 한다. 즉, **맨 처음 진실을 알고 있는 친구가 가는 파티, 그 파티에 참...

들어가기 앞서 현대자동차그룹 SW 검정 시험 느낌이다. 해당 시험을 통과하면, 정해진 레벨에 따라 코딩테스트 전형이 면제되기도 한다. 현재 정답률은 아래 사진과 같다! (순서대로 방문하기 문제의 썸네일이 귀엽다.) 문제는 아래 소프티어 사이트에서 확인할 수 있다. https://softeer.ai/practice/index.do 1번 자동차 테스트 ...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1 풀이는 다음과 같다. 풀이에 대한 설명으로, 사람P 이 있는 위치를 골라서 해당 위치로 맨해튼 거리 2 이내의 점들을 탐색하고, 만약 맨해튼 거리 2 이내의 점들에서 또다른 사람P이 있다면, 거리두기 실패 (...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/70129 풀이는 다음과 같다. 결코 어려운 문제가 아니다. 주어진 수에서 0을 제거하고, (ex : 1001 -> 11) 0을 제거한 수의 길이를 구한 후, 그 길이를 또다시 2진수로 변환한다. (ex : 11 길이 2, 2를...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/67257 풀이는 다음과 같다. calc1은 다음과 같은 함수이다. calc2은 다음과 같은 함수이다. 숫자 두개, 연산자를 받아 해당 연산 결과를 보여준다. backTracking은 연산자의 우선순위를 바꿔가며 calc1을...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/42839 풀이는 다음과 같다. 풀이는 다음과 같이 했다. backTracking 함수를 통해 주어진 숫자들을 방문하며 모든 경우의 수를 HashSet set에 넣어주었다. 해당 set를 순회하며 나오는 해당 숫자를 isPr...

문제는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/64064 풀이는 다음과 같다. isOk 함수는, 두개의 String을 기준으로 체크해줄 아이디와, 불량 사용자 아이디가 매치되는지 확인한 후 boolean을 리턴해준다. backTracking 함수는, 전체 아이디중에서 무작...

문제는 다음과 같다. https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SWPRBLSBMS_257643&psProblemId=1309 풀이는 다음과 같다. 3번의 시험 점수가 주어진다. 해당 점수를 통해 등수를 매기면 된다. 여기서 떠오르는 생각 -> 점수 순으로 줄세우고, 등수 매기기? 맞...

문제는 다음과 같다. https://www.acmicpc.net/problem/3055 풀이는 다음과 같다 알아야 할 내용은 다음과 같다. 고슴도치가 물을 피해 이동해 비버구멍으로 탈출하는 로직을 만들어야 한다. 각각 고슴도치와 물을 BFS로 이동시키며, 고슴도치는 물과 장애물을 피해서 물은 장애물을 피해서 둘이 한꺼번에 한턴에 움직인다. (if(c...

문제는 다음과 같다. https://www.acmicpc.net/problem/1068 풀이는 다음과 같다. dfs 로직을 알고 있다면, 충분히 풀 수 있는 문제이다. 우리는, 어떠한 트리 구조에서 어떤 노드를 제거했을때의 리프 노드의 수를 구하면 된다. 풀이에서 핵심 요소는 다음과 같다. 리프노드는, 자식노드가 없는 노드를 의미하므로, 리프노드...

문제는 다음과 같다. https://www.acmicpc.net/problem/15486 간략하게 말하면, 퇴사날과 스케줄이 정해졌을 때 최댓값의 이익을 뽑아내는 것이다. 예시 테스트케이스는 위 사진의 표가 있을때, 1, 4, 5,일에 있는 상담을 하고 45의 이익을 내는 것이다. 위 문제를 어떻게 풀어야 할까? 주어진날(n)의 범위가 150만 이하...

문제는 다음과 같다. https://www.acmicpc.net/problem/2240 풀이는 다음과 같다. 코드마다 자세하게 주석을 달아놓아서, 잘 읽으면 이해할 수 있다. D 라는 배열을 채울 때, w가 0일때와 0이 아닐 때 채우는 로직이 각각 다르다. Dt = t미터에서 w횟수만큼 이동했을 때 얻을 수 있는 자두의 최댓값 이라고 지정했기 때...

문제는 다음과 같다. https://www.acmicpc.net/problem/1915 풀이는 다음과 같다. R행 C열의 직사각형의 안에서, 1로 이루어진 가장 큰 정사각형을 찾는 문제이다. 그런데, 행과 열의 최댓값은 1000이고, 하나하나 모든 정사각형을 찾아낼 수는 없다. DP, 다이나믹 프로그래밍 문제이다. Di 를 i, j를 왼쪽 아래 꼭...

문제는 다음과 같다. https://www.acmicpc.net/problem/10026 흔한 BFS 문제이다. 물론 문제를 읽고 이해하는 내용도 중요하지만 바쁜 현대인들을 위해 예시 입출력을 설명하자면, 적록색약이 아닐때는 R G B가 구분가능하므로 아래와 같이 4구간으로 나뉜다. 적록색약일때는