Python

🎫code ) cnt = 0 for i in range(int(input())): word = input() word_lst = [word[0]] for k in range(1, len(word)): if word[k] != word[k - 1]: word_lst.append(word[k]) word_set = set(word_lst) if len(word_lst) == len(word_set): cnt += 1 print(cnt) 📌 description ) 문제출처 : www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두..

→2020.11.29

Algorithm/Baekjoon

[백준] 유기농배추 / 1012번 / 파이썬 / Python

🎫code ) for tc in range(1,int(input())+1): m, n, k = map(int,input().split()) arr = [[0]*m for _ in range(n)] stack = [] cnt = 0 dx = [-1,1,0,0] dy = [0,0,-1,1] for i in range(k): y, x = map(int,input().split()) arr[x][y] = 1 for i in range(m): for j in range(n): if arr[j][i] == 1: stack.append((j,i)) while stack: x, y = stack.pop() arr[x][y] = 2 for k in range(4): nx, ny = x+dx[k], y+dy[k] if 0

→2020.11.28

Algorithm/Baekjoon

[백준] LCS / 9251번 / 파이썬 / Python / 최장 공통 부분수열

🎫code ) s1 = input() s2 = input() matrix = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: matrix[i][j] = matrix[i - 1][j - 1] + 1 else: matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]) print(matrix[-1][-1]) 📌 description ) 문제출처 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence..

→2020.11.20

Algorithm/Baekjoon

[백준] 체스판 다시 칠하기 / 1018번 / 파이썬 / Python

🎫code ) import sys def chess(a, b, c): cnt = 0 for i in range(a, a + 8): for j in range(b, b + 8): if i == a and j == b: if c == 'W': chk = 'B' if bg[i][j] != c: cnt += 1 else: chk = 'W' if bg[i][j] != c: cnt += 1 continue if chk == 'W': if bg[i][j] != 'W': cnt += 1 chk = 'B' else: if bg[i][j] != 'B': cnt += 1 chk = 'W' if chk == 'W': chk = 'B' else: chk = 'W' return cnt input = sys.stdin.readli..

→2020.10.28

Algorithm/Baekjoon

[백준] 듣보잡 / 1764번 / 파이썬 / python

🎫code ) import sys input = sys.stdin.readline n, m = map(int, input().split(' ')) n_l = set() n_s = set() for _ in range(n): name = input().rstrip() n_l.add(name) for _ in range(m): name = input().rstrip() n_s.add(name) res = sorted(list(n_l & n_s)) print(len(res)) for i in res: print(i) 📌 description ) 문제출처 : www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 ..

→2020.10.21

Algorithm/Baekjoon

[백준] 후보 추천하기 / 1713번 / 파이썬 / Python / defaultdict

💡solutions ) 💬 defaultdict 사용 -> collections 모듈의 defaultdict는 딕셔너리와 거의 비슷하지만 key값이 없을 경우 미리 지정해 놓은 초기(default)값을 반환하는 특징이 있다. -> 그래서 조건문을 통해 get()메소드로 키값이 있는지 확인하지 않아도 되는 편리함이 있다. 💬 반복문에서 추천 리스트의 요소들을 하나씩 뽑아서 사진틀 리스트(photo)에 있는 지 먼저 확인하기 💬 비어있는 사진틀 유무에 따라 분기 처리 -> 비어있는 사진틀이 없다면 photo 리스트에 가장 적은 추천을 받은 번호의 학생을 찾기 -> 해당 번호의 학생 photo 리스트에서 삭제, 동시에 r_dic에서도 삭제하여 추천횟수 초기화(0) 🎫code ) from collections ..

→2020.10.21

Algorithm/Baekjoon

[백준] 회의실 배정 / 1031번 / 파이썬 / Python / 정렬 / 그리디

그리디 알고리즘(Greedy Algorithms)이란? 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 것을 결정하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 💡solutions ) 💬 sorted() 정렬 메소드를 사용했다-> 정렬기준은 종료시간, 시작시간 순으로 정렬 💬 이전 회의의(before) 종료시간을 rooms[0][1]로 잡고, 반복문을 통해 그 다음 회의의 시작시간과 비교하여 시작시간이 이전 회의의 종료시간보다 늦거나 같으면 가능회의 수를 (cnt)+=1 하고 before 값을 갱신해준다. 💬 처음 구현한 코드..

→2020.10.20

Algorithm/Baekjoon

[백준] 1541 / 잃어버린 괄호 / 파이썬 / Python / 문자열

이번 문제는 런타임에러가 계속 나서 고생을 좀 했습니다.. 😂 쉬운 문제 같았는데 계속 틀리더라구요! 결론적으로 문제에서 주어진 조건에 따른 반례를 고려하지 못해서 틀렸습니다. 예를 들어 '수는 0으로 시작할 수 있다.' 나 연산자 없이 숫자 하나만 입력받는 경우 등이 있습니다. 문제에서 우리가 알 수 있는 테스트케이스는 55-50+40 밖에 없으므로, 런타임에러가 나는 분들은 반례가 될 수 있는 것들을 찾아서 넣어보시길 추천드립니다! 💡solutions ) 💬 크게 세 부분으로 나눠서 로직 구현 👇 💬 주어진 식에 '-' 연산자 있는 경우 / '-'없이 '+' 연산자만 있는 경우 / 연산자 없이 숫자 하나만 입력받는 경우 💬 '-' 연산자가 있는 경우 : 최초의 마이너스 연산자를 기점으로 f, b으로 ..

→2020.10.19

Algorithm/Baekjoon

[백준] ATM / 수 정렬하기 / 파이썬 / Python / 정렬

💡solutions ) 💬 sorted()를 이용해 오름차순 정리한 정렬의 기본 문제 🎫code ) # 11399번 ATM 문제 n = int(input()) arr = sorted((map(int, input().split()))) res = 0 next = 0 for i in arr: res += i + next next += i print(res) # 2750번 수 정렬하기 문제 import sys input = sys.stdin.readline arr = [] for i in range(int(input())): n = int(input()) arr.append(n) arr = sorted(arr) for i in arr: print(i) 📌 description ) 문제출처 : www.acmic..

→2020.10.12

Algorithm/Baekjoon

[백준] 최단경로 / 1753번 / 파이썬 / Python / Dijkstra

💡solutions ) 💬 이번 문제는 최단 경로를 풀 때 가장 대표적인 다익스트라 알고리즘을 통해 해결했다. 💬 heap 자료구조 사용하여 heappop()을 했을 때 가장 최단 경로가 나오게 한다. 🎫code ) import heapq import sys input = sys.stdin.readline def dijkstra(v, s, adj): dist = [INF] * (v + 1) # 최단경로 리스트 dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) # 최소힙 이용 for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c h..

→2020.10.09

Algorithm/Baekjoon

0608_백준 1051번 : 숫자 정사각형/ 부르트포스 알고리즘/ Python

[코드 구현] n, m = map(int, input().split()) arr = [list(map(int, input())) for _ in range(n)] res = 0 for i in range(n): for j in range(m): for k in range(n if n < m else m): # 행과 열 중 더 작은 것을 기준으로 정사각형 탐색 if i+k < n and j+k < m: # 주어진 인덱스 벗어나지 않게 if arr[i][j] == arr[i][j+k] == arr[i+k][j] == arr[i+k][j+k]: # 꼭짓점의 숫자가 모두 같은 지 확인 if res < k: res = k print((res+1)*(res+1)) [문제 출처] 백준 1051번 숫자 정사각형 : h..

→2020.06.08

Algorithm/Baekjoon

0529_백준 15684번 : 사다리 조작/ 완전탐색(Brute-Force)/ Python

[문제 접근] - 브루트포스(완전탐색) 문제 - 사다리를 놓는 함수와 사다리를 놓은 후 모든 세로선이 자기 번호로 도착하는 지 확인하는 함수 두 가지로 프로그램을 짰다. [코드 구현] # 사다리에 가로선을 놓는 함수 def dfs(start, cnt): global res if cnt == min_cnt: if check(): res = cnt return for i in range(start, h): for j in range(n-1): # ij 위치에 사다리가 있지 않고, 전후로도 사다리가 없으면 if not ladder[i][j-1] + ladder[i][j] + ladder[i][j+1]: # 사다리 놓기 ladder[i][j] = 1 dfs(i, cnt+1) # 함수 재귀 끝나면 사다리 다시 빼..

→2020.05.29

티스토리툴바