백준(python)

문제링크 : https://www.acmicpc.net/problem/1260

문제링크 : https://www.acmicpc.net/problem/2606오늘은 백준의 단계별로 풀어보기 시리즈중 dfs와 bfs 문제 2606번을 풀었다.컴퓨터가 연결이 되어 있다는 점과 그 연결되어 있는 컴퓨터는 바이러스가 전염이되어 가는 과정을 넓이

문제링크 : https://www.acmicpc.net/problem/4963dfs와 bfs 두가지 방법 다 사용하여 풀어보았다.처음 dfs와 bfs문제를 풀기 시작했을땐 어떻게 접근해야하며 해결해야할지도저히 감이 오지 않았었는데, 다양한 문제들을 풀어보고 모

문제링크 : https://www.acmicpc.net/problem/2468dfs와 bfs문제는 이제 더이상 다른사람들의 코드를 보지 않아도 혼자 해결할 수 있는정도로 많이 보았다. 이번 문제는 처음부터 혼자 짜는 와중에 문제가 조금 애매모호한 감이 있어오래

문제링크 : https://www.acmicpc.net/problem/1003이번 문제는 단순한 피보나치 수열의 재귀함수를 이용한 문제이다.재귀함수의 단점인 값이 커지면 연산이 너무나도 많아지는걸해결하는 메모이제이션을 이용하여 푸는게 이 문제의 출제의 의도이다

문제링크 : https://www.acmicpc.net/problem/1463이번 문제는 처음 보자마자 while문을 이용하여 구현을 했다.그리디 문제를 풀때처럼 처음에 3이나 2로 나눠질 때까지 -1로 빼는 식으로 계산을 했더니수많은 반례들에 의해 난관에 부

문제링크 : https://www.acmicpc.net/problem/9095이번에도 다이나믹 프로그래밍을 이용하는 문제이다.dp문제는 규칙만 잘찾으면 코드가 매우 짧게 나온다는 걸 느꼈다.쉬운문제들은 규칙이 쉽게 보여 금방 풀리는 감이 없지않아 있는 것 같다

문제링크:https://www.acmicpc.net/problem/11053이번 문제는 가장 긴 증가하는 부분 수열 구하기이다.LIS(longest incleasing subsequence)라고 불리기도 하는데 dp로 풀 수 있는보편적인 문제유형 중 하나이다.

문제링크:https://www.acmicpc.net/problem/1010이번 문제는 고등학교때 배웠던 조합으로 풀 수 있는 간단한 문제였다.너무 간단한 문제라 설명은 생략하겠다.

문제링크 : https://www.acmicpc.net/problem/14002저번에 풀었던 lis문제와 비슷한 문제 유형이다.각 수마다 자신보다 앞에 있는 수이면서 작은 숫자들 중가장 큰 길이를 구해 그 길이에 +1 을 해주며 다른 배열에 그 값들을 추가해

문제링크 : https://www.acmicpc.net/problem/1436브루트포스 알고리즘을 공부하며 푼 문제이다.브루트포스는 단순히 그냥 가능한 경우의 수를 전부 때려박는 알고리즘이다.문제를 읽고, 복잡도를 보고 자신이 찾을 수 있는지 알고 풀어야한다.

문제링크 : https://www.acmicpc.net/problem/1916다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 처음엔 최단경로 알고리즘을 왜 다익스트라라고 부를까라고 궁금점이

문제링크 : https://www.acmicpc.net/problem/1238이번 문제는 이전에 풀었던 1916번 문제와는 다르게 왕복의 최단거리를 구하는 문제이다.처음에 제대로 읽지 않고 갈때와 올때의 거리가 다르다는 점을 유의하지 않고 그냥 풀었다가 결국다

문제링크 : https://www.acmicpc.net/problem/1504이번 문제는 방향성이 없는 그래프에서 두개의 정점을 지날 때의 최단 거리를 구하는 문제이다.v1, v2 두 정점을 지나서 n번 정점으로 가야하는데 처음에 무조건 순서대로 v1을 지나고

문제링크 : https://www.acmicpc.net/problem/13549이번 문제는 다양한 숨바꼭질 문제와는 다르게 가중치가 다르게 되어있는 문제이다.순간이동은 0초, 걸어서는 1초가 걸리는게 핵심이다.가중치가 모두 같은 1 이었을때는 평범하게 bfs나

문제링크 : https://www.acmicpc.net/problem/1261이번문제는 미로탐색 문제와 매우 비슷하다.조금 다른점은 가중치가 벽을 부순 횟수와 같은 것인다.최단거리로 이동을 하면서 그 사이에 벽이 있을 시 벽을 부수는데 그 값을 더해주는 알고리

문제링크 : https://www.acmicpc.net/problem/4485이번 문제는 (0,0)부터 (n-1,n-1)까지 찾아갈 때 가중치를 가장 적게 찾아가는 문제이다.다른 bfs,dfs문제를 많이 풀어보고 이 문제를 풀어보는게 좋을 것 같다.heapq를

문제링크 : https://www.acmicpc.net/problem/10172이번 문제는 백준문제를 처음 접하면 가장 먼저 도전하는 입출력 문제이다.파이썬에선 백 슬러시 뒤에 조합하는 문자에 따라 이스케이프 문자로 인식을 하게 되기 때문에,이번문제에선 pri

문제링크 : https://www.acmicpc.net/problem/9498

문제링크 : https://www.acmicpc.net/problem/2753문제에서 말하는대로 4로 나누었을 때 나머지가 0이 되고, 100으로 나누었을때 0이 아니면 1을 출력을 해준다.또는 400으로 나눴을 때 나머지가 0일때도 1을 출력해준다. 아니라면

문제링크 : https://www.acmicpc.net/problem/14681이번 문제도 if문을 이용한 간단한 문제이다.1사분면 - x>0, y>02사분면 - x<0, y>03사분면 - x<0, y<04사분면 - x>0, y<0위의 규

문제링크 : https://www.acmicpc.net/problem/2884이번문제도 if문을 이용하여 푸는 간단한 문제이다.map함수를 이용하여 띄어쓰기로 h와 m을 입력받는다. - split()으로 띄어쓰기 구분시간의 특성을 이용하여 m이 45보다 작을

문제링크 : https://www.acmicpc.net/problem/11021이번 문제는 for문을 이용하여 간단하게 풀 수 있다.처음에 t에 테스트 케이스를 받아 몇번의 출력을 할지 정한다.for 반복문에 range함수를 사용하여 입력값 a,b을 받는다.a

문제링크 : https://www.acmicpc.net/problem/15552이 문제에서 빠른 a+b를 하기 위해선 Python의 경우 sys.stdin.readline을 사용하라고 권장한다.import sys코드로 sys모듈을 불러오고 sys모듈안의 std

문제링크 : https://www.acmicpc.net/problem/2665이번 문제도 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있다.사실상 스토리만 다르고 1261번이랑 거의 같은 문제이다.링크텍스트여기에 자세한 설명은 해두었으니 참고하면 될 것 같다.

문제링크 : https://www.acmicpc.net/problem/18352이번 문제도 다익스트라 알고리즘을 이용하여 해결하였다.문제풀이1\. 출발지점에서 도착지점으로 가는 단방향 그래프 만들기2\. 그래프에서 출발점에서 도착점으로 연결된 점을 이동해주며

문제링크 : https://www.acmicpc.net/problem/10282이번 문제도 다익스트라 알고리즘으로 구현해주었다.a, b, s가 입력이 됐을 때, a가 b를 의존한다는 표현이 b → c 라는 점을 캐치하지 못해 시간이 조금 걸렸었던 문제이다.다

문제링크 : https://www.acmicpc.net/problem/9370처음엔 문제에 입력값이 너무 많아 이해하는데 시간이 조금 걸렸었다.문제를 처음부터 찬찬히 읽고 다 이해한 뒤에 s에서 g, h를 거쳐서 가는 최소값과 s에서 바로 가는 최소값이 같으면

문제링크 : https://www.acmicpc.net/problem/11404이번 문제는 플로이드-워셜 알고리즘 문제이다.플로이드 워셜은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘이다.하나의 정점에서 다른 정점으로 갈 수 있는 최소비용을 배열에 값을

문제링크 : https://www.acmicpc.net/problem/11657이번 문제는 가중치가 음수인 경우가 있어 다익스트라가 아니라 벨만포드 알고리즘으로 풀어야한다.벨만포드 알고리즘은 다익스트라에 비해 느리므로 가중치가 음수인경우에만 사용하는게 좋다.기

문제링크 : https://www.acmicpc.net/problem/1854이번 문제는 다익스트라 알고리즘으로 해결하는 문제이다.문제 이름 그대로 k번째 최단 경로를 구해주면 된다.처음엔 너무 쉽게 생각하고 뚝딱거리다가 몇번을 삽질하고 한참을 고민했었다.결국

문제링크 : https://www.acmicpc.net/problem/1956이번 문제도 플로이드 와샬 알고리즘으로 쉽게 풀 수 있다.마지막에 시작점과 도착점이 자기자신인 값 중 가장 작은 값만 구해주면 된다.

문제링크 : https://www.acmicpc.net/problem/11403이번 문제는 문제 그대로 가중치가 없는 방향 그래프에서 경로가 있는지 없는지 구하는 프로그램을 작성해야한다. 플로이드 와샬 알고리즘을 이용하면 쉽게 구할 수 있다. 시작점(i)부터

문제링크 : https://www.acmicpc.net/problem/1389이번 문제도 플로이드 와샬 알고리즘으로 풀었다.사람이라 생각하지 않고 앞에서 많이 풀어왔던 도시와 다리라고 생각하면 금방 이해가 된다.각각의 최단경로를 구한 다음, 경로를 다 합쳤을

문제링크 : https://www.acmicpc.net/problem/9205플로이드 와샬 알고리즘으로 풀었는데 문제에선 최단거리로 이동하라는 말이 없었으니 dfs나 bfs로 풀어도 된다.문제에서 맨해튼 거리는 첫번째 좌표를 (x1, y1)이라 하고, 두번째

문제링크 : https://www.acmicpc.net/problem/14502이번 문제는 정답 비율을 보고 만만하게 봤다가 크게 혼난 문제이다.바이러스를 탐색하는건 bfs를 이용하여 간단하게 해결하였지만, 벽을 세우는 부분에서 막혀 한참을 고민하다가결국 다른

문제링크 : https://www.acmicpc.net/problem/2248이번 문제에서 n자리의 2진수와 그 중 1인 비트가 m개 존재할 때의 점화식은(N, M) = (N-1, M) + (N-1, M-1) 가 된다.

문제링크 : https://www.acmicpc.net/problem/20500 이번 문제는 1과 5로 이루어진 n자리의 수 중에서 15의 배수를 구하는 문제이다. 문제를 보자마자 점화식을 찾아낸 뒤 dp 테이블을 활용하여 구하기 위해 규칙을 찾기 시작했다. 4자리

문제링크 : https://www.acmicpc.net/problem/10162이번 문제는 그리디 알고리즘으로 해결하였다.그리디(탐욕)알고리즘은 욕심쟁이 알고리즘이라고도 불리는데 여러 유형을 풀다보면 왜 욕심쟁이인지 알 수 있다. 뒤는 생각하지 않고 각 단계에

문제링크 : https://www.acmicpc.net/problem/12852이번 문제는 dp알고리즘을 이용해 간단하게 풀 수 있었다.먼저 저장하고 혹시 값이 더 크다면 작은 값으로 바꿔주면 되는 문제이다.조금 애를 먹었던게 순서도 같이 출력해야한다는 부분이

문제링크 : https://www.acmicpc.net/problem/1991트리문제는 처음 풀어봐서 공부를 더 해야겠다는 생각이 들었다. 처음엔 전위,중위,후위 순회가어떤 건지 몰라 다른 분들의 코드를 보고 풀어보면서 이해하였다.간단하게 생각하면전위 순회 :

문제링크 : https://www.acmicpc.net/problem/11725트리순회 문제 다음으로 바로 공부한 문제이다.루트가 1 번으로 주어졌으므로 bfs나 dfs를 이용해 1번부터 시작해서 노드들을 순회하면 되는 문제이다.

문제링크 : https://www.acmicpc.net/problem/1167이번 문제는 bfs알고리즘을 이용해 푼 풀이와 dijkstra를 이용한 두 가지 풀이가 있다.처음 코드는 서로 연결되어있는 그래프에서 bfs나 dfs로 아무 노드에서 가장 멀리 있는

문제링크 : https://www.acmicpc.net/problem/1967이번 문제는 1167번 문제와 거의 같은 문제이다. 풀이도 1167번 문제 풀이에 적어놨으니 참고하면 된다.bfs를 이용한 풀이dijkstra를 이용한 풀이

문제링크 : https://www.acmicpc.net/problem/5052이번 문제는 배열에 전화번호 목록을 입력받아온 뒤 정렬을 해서 첫번째꺼부터 마지막꺼까지 서로 다음 번호와 비교만해봐도 앞에 문자가 겹치는 지 알 수 있다. 즉, 바로 뒤에 있는 번호만

문제링크 : https://www.acmicpc.net/problem/9372이번 문제는 비행기로 이동 가능한 나라를 양방향 그래프로 저장한 후 bfs로 다음 나라로 이동할 때마다cnt를 증가시켜서 최종 결과를 출력하면 되는 간단한 문제이다.이건 풀고 나서 알

문제링크 : https://www.acmicpc.net/problem/5639이번 문제는 순회 문제인데 처음엔 전혀 감이 오질 않아 다른분의 코드를 보고 공부하였다.밑에 코드는 참조한 글여기서 설명과 코드를 보면서 공부한 코드이다.제출 후 더 빠르게 수정한 코