[백준/1987] 알파벳 | DFS와 백트래킹
·
PS/BOJ&Programmers
알파벳오랜만의 백준 포스팅!!코테에서 부족함을 절실히x99 느끼고 다시 알고리즘을 본격적으로 시작했다..🥲🤗 문제 바로 가기  알고리즘 말이 보드를 탐색하는 조건은 다음과 같다.① (1,1)부터 탐색한다.② 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 이동할 수 있다. 이 조건 아래에서 가능한 경로 중 최대한 큰 수를 구하는 것이 목표다.따라서, DFS를 통해 탐색하는 방법을 선택했다.  def dfs(y,x,cnt): visited[y][x] = True alphabet[ord(graph[y][x])-65] = True # print('시작점: ', graph[y][x]) # 현재 위치에서 네 방향의 위치 확인 for dy, dx in dr: ny, nx..
[백준/1547] 공 | 두 수의 전환
·
PS/BOJ&Programmers
공 알고리즘알고리즘을 공부해본 사람이라면 한 번쯤은 겪었을 법한 두 수의 전환을 이용한다.   이 문제에서 주의해야 할 점은 공의 번호와 인덱스를 달리 생각해야 한다는 것이다. 예를 들어, 1번 공과 3번 공의 위치를 바꿀 때 배열의 인덱스는 그대로고 1번 공과 3번 공의 위치만 즉, 인덱스 번호 바뀌는 것이다.   그래서 인덱스로만 다룰 순 없고 for문으로 공의 번호가 저장된 배열을 돌면서 입력으로 주어지는 x,y의 위치를 찾아야 한다. for _ in range(m): x,y=map(int,input().split()) # x 위치 먼저 찾기 for i in range(len(arr)): if arr[i]==x: # x가 있는 위치의 값을 tmp_x ..
[백준/5671] 호텔 방 번호 | 중복값 개수 세기(딕셔너리와 SET)
·
PS/BOJ&Programmers
5671 호텔 방 번호 5671번: 호텔 방 번호 선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004호와 같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지 www.acmicpc.net 알고리즘 범위에 해당하는 숫자들이 자릿수마다의 중복되는지 체크하면 된다. 같은 값이 있는지 확인하는 방법으로는 딕셔너리를 떠올렸고 아래와 같이 중복 체크를 해주었다. for item in hotel: d={'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0} flag=True for s in str(item): if s in d.keys(): d[s] += 1 f..
[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS
·
PS/BOJ&Programmers
바이러스 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력에서 직접 연결되어 있는 쌍이 주어진다. 더보기 1 2 2 3 1 5 5 2 5 6 4 7 1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다. 이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다. 양방향 그래프를 2차원 리스트로 정의 graph = [[] for _ in range(n+1)] for _ in range(m): x,y=map(int, input().split()) graph[x].append(y) graph[y]...
[백준/22232] 가희와 파일 탐색기
·
PS/BOJ&Programmers
가희와 파일 탐색기 22232번: 가희와 파일 탐색기 첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다. 2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열 www.acmicpc.net 알고리즘 정렬이 순서대로 이어져야 하므로 lambda를 활용하였다. 또한, 2 번째 조건은 까다로워서 정렬함수 말고 직접 교체해주었다. 전체 코드 import sys;input=sys.stdin.readline n,m=map(int, input().split()) jo_test = [input().rstrip() for _ in range(n)] ext = set(input().rstrip() for ..
[백준/1015] 수열 정렬
·
PS/BOJ&Programmers
수열 정렬 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다. 처음에 문제 이해 자체가 좀 어려웠는데, 예시를 통해서 비교적 쉽게 이해할 수 있었다. 일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N
[백준/11004] K번째 수 | Python 정렬 함수의 알고리즘
·
PS/BOJ&Programmers
K번째 수 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 N(1
[백준/1032] 명령 프롬프트 | 문자열 비교
·
PS/BOJ&Programmers
명령 프롬프트 알고리즘 문자열 비교 알고리즘이다. 이런 문제를 풀 때는 모든 보기를 다 비교해야 할지, 일부로도 해결이 가능한지 판단한다. 어차피 N의 범위가 적으니까 할 수 있는 건 다 해서 풀어낸다. 전체 코드 내가 작성한 코드 import sys; input=sys.stdin.readline n=int(input()) file=[input() for _ in range(n)] tmp=[] for i in range(n): for j in range(i+1, n): if file[i] != file[j]: a = file[i] b = file[j] for k in range(len(a)): for l in range(len(b)): if a[k] != b[k] : tmp.append(k) break ..
[백준/1009] 분산 처리 | 반복되는 숫자 어떻게 효율적으로 처리할까
·
PS/BOJ&Programmers
 분산 처리 알고리즘 승수의 마지막 자리 반복 0 0 1 1 2 2 4 8 6 3 3 9 7 1 4 4 6 5 5 6 6 7 7 9 3 1 8 8 4 2 6 9 9 1 수의 끝자리만 가져오는 두 가지 방법 문자열 활용 a = str(a) a = int(a[-1]) 나머지 활용(%10, %100, %1000, ....) a %= 10 # 끝 한 자리만 a %= 100 # 끝에서부터 2개 전체 코드 import sys; input=sys.stdin.readline t=int(input()) for _ in range(t): a,b = map(int,input().split()) a = str(a) a = int(a[-1]) if a == 1 or a == 5 or a == 6: print(a) # 4 번씩..
[백준/10158] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데
·
PS/BOJ&Programmers
10158 개미 알고리즘 t의 범위가 1 ≤ t ≤ 200,000,000이므로 완전탐색을하면 타임아웃이다. 그렇다면 어떤 점화식을 세워서 문제를 풀어야 한다는 건데 1. x와 y의 독립성 이 문제는 1초의 시간이 지날 때 x = (x+1) or (x-1)이 되고 y = (y+1) or (y-1)이 된다. 따라서 각각의 값이 독립적으로 움직인다는 결론에 도달할 수 있다. 2. 이동 횟수와 이동 거리의 관계 x좌표와 y좌표는 각각 t만큼 이동을 하게 되고, 이 이동 주기가 2*w, 2*h이다. 아래와 같은 그래프를 보면 이해가 쉽다. 따라서 이동 자체에 대한 점화식은 다음과 같다. (p+t) % 2*w (q+t) % 2*h 이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다. 거리는 수학적으로 뺄..
[백준/9251] LCS | 최장공통수열
·
PS/BOJ&Programmers
9251 LCS LCS 문제 해결 기법 두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다. 문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자. dp table은 memoization 방식으로 이어나간다. 알고리즘 이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,, table 설명을 위해 i=6, j=4일 때를 예를 들어보자면 일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 ..
[백준/2178] 미로 탐색 | BFS와 최단 경로
·
PS/BOJ&Programmers
BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아..
[백준/16283] Farm
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/16283 16283번: Farm 입력은 표준입력을 사용한다. 첫 번째 줄에 네 정수 a, b, n, w가 한 줄에 주어진다. 1 ≤ a ≤ 1,000, 1 ≤ b ≤ 1,000, 2 ≤ n ≤ 1,000, 2 ≤ w ≤ 1,000,000이다. www.acmicpc.net [알고리즘] 백준 사이트에서 알고리즘 문제를 풀고 나면 다른 사람이 쓴 코드를 항상 확인해보는데, kocc10님의 코드에 배울 점이 많아서 포스팅 해본다. [내가 쓴 코드] a, v, n, w = map(int, input().split()) ans = [] for i in range(n) : for j in range(n) : if a*i + v*j == w and i+j ==..
[백준/2961] 도영이가 만든 음식 | 브루트포스의 구조(조합) | 곱셈 누적 초기화는 1 | 디버깅을 열심히 하자. 내가 짠 코드를 파악하는 방법
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다. 신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 ..
[백준/9291] 스도쿠 채점 | n*n 행렬에서 m*m 행렬 추출하기
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/9291 9291번: 스도쿠 채점 각 테스트 케이스에 걸쳐 "Case x:"를 출력한 후, 공백 한 칸 뒤에 풀이가 올바르면 "CORRECT"를, 아니면 "INCORRECT"를 출력한다. x는 테스트 케이스 번호이며, 1부터 시작한다. www.acmicpc.net 새벽에 졸린 거 참아가며 풀었는데,, ㅋ 알고보니 입력값 중간에 엔터 처리 때문에 오늘까지 끌고왔다. 2차원 리스트에서 열만 추출하기 행은 어차피 앞쪽 인덱스만 처리해주면 행값만 추출하니까 어렵지 않게 추출할 수 있다. 근데 열은..?! [ ][i] 이런 처리가 안되니까, 따로 빼주어야 한다. 이때 이중 for문의 구조를 활용하면 되는데, 안쪽 for문 인덱스가 먼저 증가하니까 먼저 증가..
sebinChu
'백준' 태그의 글 목록
상단으로

티스토리툴바