백준 알고리즘

https://www.acmicpc.net/problem/15558간단한 문제인데 82퍼의 벽에 막혀 엄청나게 틀렸다.

https://www.acmicpc.net/problem/2589입력한 좌표에서 L로 연결된 최대 거리를 반환하는 함수를 작성하였고이를 모든 L 좌표에서 반복해서 최대값을 구한다.알아두면 좋을 것 같다.

https://www.acmicpc.net/problem/13549N과 K가 같을 때 조건을 생각하지 못해 오답이 발생하였다.이 조건만 생각한다면 쉽게 풀 수 있는 것 같다.

https://www.acmicpc.net/problem/26360,0은 항상 공기이므로 0,0에서 시작함처음으로 공기와 닿은 치즈는 큐에 추가하지 않음반복문을 돌릴때 1시간 전 치즈의 크기를 구하기 위해 항상 치즈의 크기도 같이 구해줌

https://www.acmicpc.net/problem/16173dfs 개념잡기용 문제dfs를 수행하고 가장 오른쪽 아래칸에 방문여부로 print를 하면 된다.

https://www.acmicpc.net/problem/1068주요 반례로는 이런 식으로 제거했을때 2번 노드가 루트노트가 되는 경우가 있었다.그래서 인접그래프가 지우는 노드 그 자체인 경우의 조건을 추가해주었다.

https://www.acmicpc.net/problem/1520DFS로 풀었는데 시간 초과가 뜬다.문제를 다시보니 DP 개념이 필요한 문제라서 DP를 공부하고 다시 풀어야 겠다.

https://www.acmicpc.net/problem/14888순열을 이용하였다.중복이 있으므로 반드시 중복 제거를 해준다.

https://www.acmicpc.net/problem/9663pypy3으로 통과하였다.N퀸은 대표적인 백트래킹 문제라고 한다.문제를 풀지는 못했지만 체스판은 이차원 배열이지만 인덱스를 하나의 축으로 보는 방식으로 일차원 배열로 퀸의 위치를 기록하였다.로직은

https://www.acmicpc.net/problem/90951,2,3까진 직접 경우의 수를 구한다.4부터는 나눠서 생각했다.3을 만드는 방법에 1을 더해주면 4가 된다.마찬가지로 2를 만드는 방법에 2를 더해주면 4가 되고 1을 만드는 방법에 1을 더해주

https://www.acmicpc.net/problem/1244주어진 조건 그대로 착실하게 코드를 작성하면 구현 자체는 어렵진 않았다.

https://www.acmicpc.net/problem/2491같은 자리 수열을 만들어서 조건을 만족하면 1을 더해주는 기본적인 DP 문제이다.

https://www.acmicpc.net/problem/1541가장 작은 수를 만들기 위해서는 - 부호 사이에 괄호를 만들면 된다.ex) 50-40+30-20+10 => 50-(40+30)-(20+10)

https://www.acmicpc.net/problem/1080위 그림처럼 3X3행렬의 가장 왼쪽 위 숫자만 비교해주면서 행렬을 변경해준다.변경이 끝나고 A==B가 같으면 cnt를 출력, 다르면 -1을 출력하고 예외조건으로 N,M이 3 미만일때도 생각해준다.

https://www.acmicpc.net/problem/1931끝나는 시간 - 시작하는 시간 순으로 정렬하여 그리디 알고리즘을 적용한다.

https://www.acmicpc.net/problem/1715문제를 해결하기 위한 로직은 정렬 후 가장 작은 두개의 수를 뽑아 더하는 것을 반복하는 것이다.그런데 정렬을 계속하면 시간초과가 발생하여 우선순위 큐(힙큐)를 사용하였다.

https://www.acmicpc.net/problem/1339알파벳을 추출하여 딕셔너리를 만들고 value로는 0을 넣어주었다. 그리고 단어를 순회하면서 자리수를 구하고 곱해주어 딕셔너리의 value에 더해주었다.예를 들면 C는 'GCF' 에서 10, 'A

https://www.acmicpc.net/problem/11000강의가 끝나는 시간을 기록하고 새로운 강의의 시작시간이 기존 강의의 끝나는 시간보다 작을 경우에는새로운 교실을 추가한다.가장 빨리 끝나는 강의를 찾기 위해 힙큐가 사용된다.

https://www.acmicpc.net/problem/2212문제 설명이 조금 어려운데아래의 input을 넣어주면1,3 이렇게 나눌 수 있고 집중국이 각각 2,3의 범위를 가지므로 최소값은 5이다.센서를 정렬하고 각각의 거리를 구했다.그리고 거리가 큰 순서

https://www.acmicpc.net/problem/12904S에서 T를 만들기보다는 T에서 S로 역산한다.

https://www.acmicpc.net/problem/2437추가 A,B,C,D 4개가 있다고 가정했을때추가 1개인 경우 A만 측정 가능하다.측정 가능한 무게 = A그런데 여기에 B가 추가되면 이 전의 측정 가능한 무게 리스트 원소에 B를 다 더해준 값과

https://www.acmicpc.net/problem/13904

https://www.acmicpc.net/problem/1149예시로 아래와 같이 주어졌다.이 그래프를 DP처럼 사용한다.만약 두번째 집에서 초록색을 사용한다고하면 첫번째 집에서 빨간색이나 파란색을 사용했을 것이다.빨+초 = > 26+60 = 86파+초 =

https://www.acmicpc.net/problem/1932삼각형 테두리에 있는 원소는 따로 계산해주었고내부에 있는 원소는 대각선 위 아래에서 큰 값을 더해주는 식으로 풀었다.

https://www.acmicpc.net/problem/1966문제 조건 그대로 구현했다.

https://www.acmicpc.net/problem/10157빈 리스트에 테두리를 순환하면서 좌표를 넣어주었다.그런데 인덱스오류가 발생했다.이런 식으로 남는 부분이 리스트에 들어가지 않았다.그래서 반복이 끝나고 해당 부분을 추가해주는 식으로 처리하였다.

https://www.acmicpc.net/problem/2564A가 상점의 위치, B가 경비원의 위치라고 할때특정 점(0,0)을 기준으로 한 방향으로의 거리를 측정한다. (파란색과 보라색)그리고 두 거리의 차를 구하면 이동거리가 나오는데, 이 이동거리가 짧은

https://www.acmicpc.net/problem/1072입력의 숫자가 매우 크므로 반드시 sys로 입력을 받아야 한다.이미 승률이 99%인 경우는 100%가 될 수 없다는 예외조건을 잘 생각해야한다.

https://www.acmicpc.net/problem/20551처음엔 while 반복문으로 문제를 풀고 예제입력 1을 통과했는데 예제입력 2에서 막혔다.예제입력2는 동일원소가 나올때 가장 작은 인덱스값을 출력하는건데이것을 보자마자 bisect 라이브러리가

https://www.acmicpc.net/problem/1431문자와 문자의 길이, 문자 내부의 자리수의 합을 리스트에 넣고 정렬해준다.isdigit() 라는 메소드에 대해 알게되었다.string 클래스의 메소드로 문자가 모두 숫자이면 True를 반환, 하나

https://www.acmicpc.net/problem/17140lambda 정렬을 통해 풀 수 있는 문제이다.문제를 풀기위해서는 행과 열을 바꿔주는 과정이 필요한데 이 과정에서 zip 이라는 내장함수를 알게되었다.

https://www.acmicpc.net/problem/2170입력값을 양쪽 다 비교해야 답을 구할 수 있지만, 입력값을 담은 리스트를 정렬하면 시작점은 비교할 필요가 없다.따라서 끝점의 크기만 비교해가면서 답을 구하면 된다.

https://www.acmicpc.net/problem/5430시간 초과를 방지하기 위해 R이 나왔다고 행렬을 뒤집기보다는 방향을 바꿔주는게 좋다.그리고 출력이 리스트가 아니다.쉼표 뒤의 공백이 없으므로 출력값을 똑같이 만들어줘야한다.

https://www.acmicpc.net/problem/17609회문의 특성상 양끝에서 똑같은 갯수의 문자를 지워도 회문이다.하나씩 비교하다가 양쪽이 서로 문자가 다를때 한쪽씩 지워가면서 회문 체크를 해준다.

https://www.acmicpc.net/problem/5052전화번호를 정렬한뒤 앞에서부터 뒤에 오는 번호와 비교했다.

https://www.acmicpc.net/problem/1958LCS 문제에서 비교하는 단어가 3개로 늘어서 3차원 배열로 DP를 적용하면 쉽게 풀수있는 문제였다.

https://www.acmicpc.net/problem/7490연산해야되는 숫자가 작아서 중복순열을 이용해 풀었다.eval() 함수는 괄호에 오는 문자열을 숫자처럼 계산해주는 함수이다.

https://www.acmicpc.net/problem/16120문자열 치환 문제는 replace 를 쓰면 쉽게 풀수있지만, 입력이 길어지면 시간초과가 발생한다.그러므로 스택을 활용하여 푸는 것이 안전하다.

긴 문자열에서 짧은 문자열로 연산방법 두가지를 모두 시행하면서 최종적으로 문자열의 길이가 같아졌을때, 리스트에 S가 있는지 판단하여 문제를 풀었다.

https://www.acmicpc.net/problem/1351백준에서는 해시에 분류되어있는 문제이다.재귀문제인데 숫자 범위가 커서 그냥 재귀로 풀면 메모리 초과가 발생한다.재귀에서 구한 값을 딕셔너리에 저장해서 이미 구한 값은 꺼내오는 식으로 통과할 수 있

https://www.acmicpc.net/problem/2295투포인터의 변형 문제이다.세개의 포인터를 선택해야하고, 중복이 가능하므로 조건을 살짝 변경해서 풀었다.

https://www.acmicpc.net/problem/15686combinations 라이브러리를 쓰면 간단한 문제인데 백트래킹을 익히기 위해 백트래킹을 이용해서 풀었다.

https://www.acmicpc.net/problem/13023문제가 살짝 이해하기 힘들지만 요약하자면 한점에서 출발하여 5번째 요소까지 방문할 수 있냐를 묻는 문제이다.즉, 이런 그래프는 문제 조건을 만족시킬 수 없다.DFS 문제지만 백트래킹 개념이 필요

https://www.acmicpc.net/problem/17471게리맨더링은 아래의 그림처럼 선거구를 유리하게 선정하는 전략을 말한다고 한다.문제 풀이는 이렇게 접근했다.선거구를 두개로 나누기combinations을 활용하여 N의 갯수의 절반만큼 반복을 시행

https://www.acmicpc.net/problem/1937 1차 풀이 시간초과가 발생했다. DP를 적용시키지 못했다. 2차 풀이 DP로 DFS의 반복을 줄이는 것이 핵심이다.

https://www.acmicpc.net/problem/2638비슷한 문제를 코딩테스트에서 풀었던 기억이 있어 같은 로직을 적용했다.같은 공기지만 치즈 외부와 내부의 공기라는 차이점이 있기 때문에 치즈 외부의 공기는 graph 에서 2로 변환시켜주는 DFS

https://www.acmicpc.net/problem/9466방문 루트를 작성하고 다음 방문노드가 해당 루트에 있으면 정지한다.주의할점은 모든 루트를 저장하는 것이 아니고 반복되는 구간만 저장하는 것이다.루트를 슬라이싱해서 반복되는 구간을 구할 수 있다.

https://www.acmicpc.net/problem/1520처음에는 그냥 DFS로 풀었는데 시간 초과가 발생했다.그래서 DP를 적용시켜야된다는 것을 직감했다.DP그래프의 좌표는 해당 좌표에서 종점까지 가는 방법의 갯수이다.여기서 (0,3) 32값을 가진

https://www.acmicpc.net/problem/2573난이도는 그렇게 어렵지 않다. 그런데 파이썬에서 DFS로 풀면 메모리 초과 혹은 시간 초과를 보기 정말 쉽다. (백준 정답비율이 낮은 이유)pypy3으로 제출하고 재귀제한은 10\*\*4 로 해야

https://www.acmicpc.net/problem/16946전체 배열을 순회하면서 1 -> 0으로 바꾸고 DFS를 하는 방식으로 풀었는데visited 를 반복마다 생성해서그런지 시간초과로 통과xgraph 에서 0의 구역을 나누어서 2부터 넣어줌. (ar

https://www.acmicpc.net/problem/16922기본적인 백트래킹 문제 유형인데, 시간 초과가 발생하므로 반복 구간을 잘 설정해야 한다.

https://www.acmicpc.net/problem/171365칸 색종이부터 1칸 색종이까지 대보면서 갯수를 구하는 식으로 풀었다.예제는 다 통과했는데 제출하면 실패했다.반례는 아래와 같았다.이러한 배열은 3x3 1칸, 2x2 3칸, 1x1 3칸으로 표현

https://www.acmicpc.net/problem/18428graph에 대해 조건 통과 여부를 판단하는 check라는 함수를 작성했고백트래킹으로 O 장애물 3개를 설치해가면서 문제 조건을 통과하는지 체크해준다.

https://www.acmicpc.net/problem/1062정답은 나오는데 시간초과가 발생했다.비트마스킹 개념을 도입해서 시간복잡도를 줄였다.

https://level.goorm.io/exam/49076/1%EC%B0%A8%EC%9B%90-%EB%BF%8C%EC%9A%94%EB%BF%8C%EC%9A%94/quiz/1이것저것 조건을 달다보니 코드가 길어졌는데 정답 코드처럼 간소화할 수 있는 문제였다.

https://www.acmicpc.net/problem/2493스택에서 자주 출제되는 유형의 문제인데 좋은 테크닉을 배웠다.참고 블로그

https://www.acmicpc.net/problem/2015얼마전에 구름 알고리즘 강의에서 defaultdict 에 대해 배워서 딕셔너리 문제를 풀었다.범위가 일반적인 누적합 알고리즘으로 풀면 시간초과나 메모리초과가 발생할 수 있어서 딕셔너리를 활용하여

https://www.acmicpc.net/problem/1484쉬운 투포인터 문제였다.

https://www.acmicpc.net/problem/1461수열을 정렬한뒤 0을 기준으로 나눠준다.그리고 M으로 나눴을때 나머지가 0인 값들만 저장해주고저장한 거리 리스트를 두배한 값에서 가장 큰 값(왕복하지 않을 거리)를 뺀다.

https://www.acmicpc.net/problem/1922크루스칼 알고리즘 + 유니온 파인드위의 링크에서 크루스칼 알고리즘을 활용하여 최소신장트리 문제를 푸는 방법에 대해 배웠다.

https://www.acmicpc.net/problem/99341 6 4 3 5 2 7 이런 순서로 입력되었을때,가장 아래층부터 채워나간다.트리에서 가장 아래층은 입력 순서의 홀수번째 수이다.즉, 가장 아래층은 1 4 5 7이다.한 층을 채우고나면 홀수번째

https://www.acmicpc.net/problem/4803유니온 파인드를 이용하는 문제였다.자꾸 오류가 발생하여 원인을 찾아보니 find 함수에 있었다.

https://www.acmicpc.net/problem/1240백트래킹으로 쉽게 풀 수 있었다.딕셔너리의 개념을 정확히 이해하고있지 않아서 막혔다.딕셔너리의 키는 mutable하고 값은 immutable하다.처음에 키를 list로 하려고 했다가 막혀서 딕셔너

https://www.acmicpc.net/problem/3584graph에 부모 노드를 기록했다.그리고 재귀함수로 타고올라가면서 그 루트를 저장했다.공통 조상을 구해야할 노드 C와 D가 주어지면C의 루트는 \[16,10,4,8]D의 루트는 \[7,6,4,8]

https://www.acmicpc.net/problem/1167그 전에 풀었던 문제와 유사했다.트리의 지름을 구하는 방식은 아래의 2가지 순서로 이루어 진다.임의의 노드에서 가장 먼 거리의 노드를 구한다.1에서 구한 노드와 가장 멀리 떨어진 노드와의 거리를

https://www.acmicpc.net/problem/11437LCA 알고리즘을 사용하는 기초 문제였다.LCA 알고리즘제출은 Pypy3으로 했다.

https://www.acmicpc.net/problem/14267defaultdict 를 사용해서 문제를 풀었다.문제에는 강조되지 않았지만 한사람이 여러번 칭찬을 받을 수 있는 경우도 생각해야한다.시간복잡도 때문에 pypy3으로 제출했다.

https://www.acmicpc.net/problem/1135트리+DP 유형의 문제이다.DP 그래프를 0으로 초기화하고 아래부터 접근했다.노드 22 노드는 3,4 두개의 리프노드를 가진다.DP3, DP4 는 리프노드이므로 0이다.그렇다면 2에서 자식노드들의

https://www.acmicpc.net/problem/16437트리+DP 유형의 문제이다.비슷한 유형의 문제를 많이 풀어보다보니 어느정도 감이 잡혀서 쉽게 풀 수 있었다.x 노드에서 dfs를 할때 자식노드를 방문하고 방문 후에는 자식 노드의 dp값을 더해

https://www.acmicpc.net/problem/1504다익스트라를 여러번 해서 풀었다.경로해야할 정점으로 v1 v2가 있으므로1 -> v1 -> v2 -> N1 -> v2 -> v1 -> N이러한 두 경로가 있을 수 있다.따라서 이 두 경로의 최단거

https://www.acmicpc.net/problem/1238다익스트라 유형의 문제인데 특정 점에서 다시 돌아오는 경로의 길이까지 포함한 값의 최소값을 구해야한다.

https://www.acmicpc.net/problem/15684사다리 결과를 체크해서 True or False를 반환하는 sadari라는 함수를 만들었다.가능한 좌표를 백트래킹하면서 sadari 함수의 결과를 체크하는 식으로 풀었으나 시간초과가 발생했다.

https://www.acmicpc.net/problem/1010N,M을 도식화하면 일정한 규칙성이 있다.이 규칙성으로 DP를 구해준다.

https://www.acmicpc.net/problem/2193DP를 계산해보면 피보나치 수열의 DP를 가진다.

https://www.acmicpc.net/problem/4485다익스트라 알고리즘 개념을 이차원 배열에 적용시켜 시작점에서 끝점까지 최소 가중치를 구하는 구하는 문제였다.

https://www.acmicpc.net/problem/14938다익스트라 알고리즘의 기본 개념 문제였다.

https://www.acmicpc.net/problem/2665백준 1261번 문제와 같은 유형의 문제이다.벽을 뚫는 2차원 배열 다익스트라 문제인데 이러한 문제는 다음과 같이 접근한다.만약 벽에 막히지 않았다면 최소 가중치가 0일 것이고, 최소 가중치가 1

https://www.acmicpc.net/problem/1719다른 문제처럼 최단거리를 묻는 것이 아닌 최단 거리까지의 경로를 묻는 문제이다.힙큐의 원소를 (거리, 노드,지금까지 경로) 로 넣고 다익스트라 알고리즘을 실행시켜 최단경로를 구할 수 있다.