CS
[BaekJoon] 백준 3190번 뱀
[BaekJoon] 백준 3190번 뱀 문제: www.acmicpc.net/problem/3190 내코드 - 그대로 구현하기만 하면 되는 간단한 문제였다. - 처음에는 내용 이해를 하고 어떻게 구현해야 할지 막막했는데 하나씩 짜다보면 풀리는 문제였다. - 뱀의 몸이 있는 위치를 deque에 넣어주고 빼줘서 뱀이 이동하는 것을 나타냈다. - 포인트는 문제에 적혀있는 이 세문장이라고 생각한다. 이 순서대로 코드를 작성하였다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. - 또 까다로웠던 부분은 왼쪽, ..
[BaekJoon] 백준 12100번 2048 (Easy)
[BaekJoon] 백준 12100번 2048 (Easy) 문제: www.acmicpc.net/problem/12100 내코드 - dfs와 시뮬레이션을 섞어놓은 문제 - dfs로 상하좌우 각각의 경우에 대해서 이동시키는 것을 각각 5번씩 반복했다. - 이동 시킬때 상하우는 모두 좌로 모양을 맞춰주기 위해 list의 모양을 바꿔주었다. - 모양을 바꿔준 후 0을 제외한 값들만 남기고 붙어있는 두 숫자가 같은 경우에 더해주었다. (ex) 2 2 4 1 1 -> 4 0 4 2 0 (이렇게 해주면 이미 한번 더해진 블럭의 경우 다시 더해지지 않는다!) - 이후에 다시 0을 제외해준 뒤, 배열의 크기 n 에 맞게 뒤에 0을 다 붙여주었다. - 여기까지 하고 다시 처음부터 상하좌우에 대한 이동을 반복한다. - 5번..
[BaekJoon] 백준 13460번 구슬 탈출 2
[BaekJoon] 백준 13460번 구슬 탈출 2 문제: www.acmicpc.net/problem/13460 내코드 - bfs 문제 - 지금까지 풀었던 bfs 문제들과 비슷하지만 구슬 두개를 움직여야 한다는 점에서 생각이 필요했다. - 마지막에 계속 막히던 부분(백준 68%.. 정도에서 틀림)이 있었는데 횟수의 문제였다. if point[2] > 10을 if point[2] > 9 로 바꿔주니까 통과함 from collections import deque arr = [] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] n, m = map(int, input().split()) # 지도 정보 저장 def init(): for i in range(n): tmp = list(str(in..
[BaekJoon] 백준 1759번 암호 만들기
[BaekJoon] 백준 1759번 암호 만들기 문제: www.acmicpc.net/problem/1759 내코드 이전 백트래킹 문제들과 푸는 방식은 비슷하지만 포인트는 크게 두가지 였다. 자음과 모음의 최소 포함 개수가 정해져 있었다는 것 사전 순으로 출력해야 한다는 것 consonant_n, vowel_n 변수를 따로 선언해줘서 자음 모음 개수를 저장해주고 마지막에 개수를 확인해 준뒤 출력해줬다. 또한 out변수에 append하기 전에 out 리스트의 마지막 문자보다 현재 입력하려고 하는 문자가 사전순으로 뒤에 있는지 확인해 준뒤 입력해줬다. 문제를 풀면서 맞게 풀었다고 생각했는데 틀렸다고 나왔다. 처음 입력받은 문자열 리스트를 sorted()로 정렬해주니 해결되었다. # BaekJoon1759.py..
[OS] Process 동기화 (3) Deadlock
[OS] Process 동기화 (3) Deadlock (교착상태) Deadlock란, 프로세스에 자원이 잘못 분배되었을 때 일어난다. 간단히 말하자면, 만약 한 프로세스가 자원 A를 가지면서 자원 B를 요구한다고 가정해보자. 이 상태에서 다른 프로세스가 자원 B를 가지고 있으면서 A를 요구하고 있는 상황이라면 이도저도 못하는 상태가 되어 버린다. 이를 deadlock이라고 한다. Deadlock에 빠지는 조건 4가지 교착상태에 빠지는 조건은 총 4가지가 있다. 이 4가지 조건을 모두 만족할때 교착상태에 빠지게 된다. Mutual Exclusion (상호배제) : 한번에 오직 하나의 프로세스가 하나의 자원만 사용 Hold and Wait (점유하고 대기): 자원을 할당받은 상태에서 다른 프로세스가 사용중인..
[OS] Process 동기화(2)
[OS] Process 동기화(2) 전통적 동기화 예제 Producer-Consumer Problem 생산자가 데이터를 생산 -> 소비자가 그 데이터를 소비하는 형태 예시: 컴파일러->어셈블러, 웹 서버->웹 클라이언트 생산한 데이터는 중간의 buffer라는 저장공간에 저장해두고 소비자는 여기서 필요한 만큼 가져감 동기화 문제: 생산자와 소비자가 동시에 접근하는 변수를 동시에 업데이트, 즉 임계구역에 동시에 접근 Readers-Writers Problem 임계구역에 접근하는 프로세스의 종류를 reader와 writer로 나눈다. reader는 임계구역에서 데이터를 바꾸지 않고 읽기만 하는 프로세스, writer는 임계구역에서 데이터를 바꾸는 프로세스를 말한다. 여기서 writer는 mutal exclus..
[BaekJoon] 백준 6603번 로또
[BaekJoon] 백준 6603번 문제이름 문제: www.acmicpc.net/problem/6603 내코드 이 문제는 백트래킹으로 풀었다. 주어진 숫자들에서 6개의 숫자를 선택해서 사전순으로 나열하고 출력하면 된다 out 변수에 선택된 6개의 숫자를 차곡차곡 넣어준다. visited 리스트에 해당 순서의 숫자가 선택되었는지, 안되었는지 true, false로 기록해준다. dfs와 비슷한 방식이다. out[0]을 1이라고 선택하면, out[1]을 2로 선택한 경우를 쭉 보고, out[1]을 3으로 선택한 경우를 쭉 확인하는 방식으로 간다. 각각의 경우를 확인하면 pop을 해서 다음 경우를 확인하게 된다. out의 길이가 6이 되면 출력을 해준다. # BaekJoon 6603.py 로또 def solve..
[BaekJoon] 백준 15651번 N과 M(3)
[BaekJoon] 백준 15651번 N과 M(3) 문제: www.acmicpc.net/problem/15651 내코드 이전 문제들과 비슷 단지 오름차순이여야 한다는 조건이 없고, 중복이 가능하기 때문에 해당 코드를 제거해 주면 된다. # BaekJoon 15651.py N과 M(3) # 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 n, m = map(int, input().split()) out = [] # 출력 내용 def solve(depth, N, M): if depth == M: # 길이가 m인 리스트가 완성되었다면 print(' '.join(map(str, out))) # 출력 return for i in range(n):..